Untitled
unknown
plain_text
2 years ago
3.1 kB
0
Indexable
Never
#include <iostream> #include "BFSandDFS.cpp" using namespace std; #define SIZE 10 class NodeVertex { char vertexName; int weight; NodeVertex *next; public: NodeVertex() { vertexName = '*'; weight = -1; next = NULL; } NodeVertex(char v, int w) { vertexName = v; weight = w; next = NULL; } friend class Graph; }; class Graph { int vertexCount, edgeCount; NodeVertex **head; public: Graph() { vertexCount = -1; edgeCount = -1; head = NULL; } Graph(int vC) { vertexCount = vC; edgeCount = -1; head = new NodeVertex *[vC]; for (int i = 0; i < vC; i++) { head[i] = NULL; } } void createGraph(); void display(); void BFS(char); void DFS(char); }; void Graph ::createGraph() { int weight; char name; for (int i = 0; i < vertexCount; i++) { cout << "Enter Name of vertex: "; cin >> name; head[i] = new NodeVertex; head[i]->vertexName = name; } int i = 0; while (i < vertexCount) { cout << "Enter the Adjacent Edge to " << head[i]->vertexName << ": "; cin >> name; if (name == '0') { i++; continue; } cout << "Enter the weight of edge: "; cin >> weight; NodeVertex *newNode = new NodeVertex(name, weight); NodeVertex *temp = head[i]; if (temp->next == NULL) { temp->next = newNode; } else { while (temp->next != NULL) temp = temp->next; temp->next = newNode; } } } void Graph ::display() { int i = 0; while (i < vertexCount) { NodeVertex *temp = head[i]; cout << head[i]->vertexName << "\t"; temp = temp->next; while (temp->next != NULL) { cout << "(" << temp->vertexName << "," << temp->weight << ")" << "\t"; temp = temp->next; } cout << "(" << temp->vertexName << "," << temp->weight << ")" << "\n"; i++; } } void Graph::DFS(char start) { stack s; int arr[vertexCount] = {0}; arr[int(start) - 97] = 1; s.push(start); while (!s.isEmpty()) { start = s.pop(); cout << start << "\t"; NodeVertex *temp = head[int(start) - 97]; while (temp->next != NULL) { if (arr[(temp->vertexName) - 97] == 0) { s.push(temp->vertexName); arr[int(temp->vertexName) - 97] = 1; } temp = temp->next; } if (arr[(temp->vertexName) - 97] == 0) { s.push(temp->vertexName); arr[int(temp->vertexName) - 97] = 1; } } } void Graph ::BFS(char start) { Queue q; int arr[vertexCount] = {0}; arr[int(start) - 97] = 1; q.push(start); while (!q.isEmpty()) { start = q.pop(); cout << start << "\t"; NodeVertex *temp = head[int(start) - 97]; while (temp->next != NULL) { if (arr[(temp->vertexName) - 97] == 0) { q.push(temp->vertexName); arr[int(temp->vertexName) - 97] = 1; } temp = temp->next; } if (arr[(temp->vertexName) - 97] == 0) { q.push(temp->vertexName); arr[int(temp->vertexName) - 97] = 1; } } } int main() { int vertexCount; char start; cout << "Enter total Number of Vertices: "; cin >> vertexCount; Graph g1(vertexCount); g1.createGraph(); g1.display(); cout << "\n\n"; cout << "Enter vertex you want to start from : "; cin >> start; g1.BFS(start); cout << "\n"; g1.DFS(start); }