Untitled
unknown
plain_text
2 years ago
17 kB
1
Indexable
Never
#include <iostream> #include <queue> using namespace std; class Node { private: int vertexNumber; Node *next; public: Node() { vertexNumber = 0; next = nullptr; } Node(int n) { vertexNumber = n; next = nullptr; } friend class Graph; }; class Graph { private: Node **adjList; bool *visitedList; int totalV; int totalE; void addEdge(int source, int destination) { Node *newnode = new Node(destination); newnode->next = adjList[source]; adjList[source] = newnode; } void clear() { for (int i = 0; i < totalV; i++) { visitedList[i] = false; } } public: Graph(int vertices, int edges) { totalE = edges; totalV = vertices; adjList = new Node *[vertices]; visitedList = new bool[vertices]; for (int i = 0; i < vertices; i++) { adjList[i] = nullptr; visitedList[i] = false; } } void createGraph() { int source, destination; for (int i = 0; i < totalE; i++) { cout << "Enter Source and Destination \n"; cout << "Source: "; cin >> source; cout << "Destination: "; cin >> destination; addEdge(source, destination); addEdge(destination, source); } } void display() { cout << "Graph is --> \n"; for (int i = 0; i < totalV; i++) { if (adjList[i] == NULL) { cout << "No connections for node " << i << " \n"; } else { cout << "Node connected to " << i << " --> "; Node *temp = adjList[i]; while (temp != NULL) { cout << temp->vertexNumber << " "; temp = temp->next; } cout << "\n"; } } } void dfs(int vertexNo) { cout << "At node " << vertexNo << "\n"; visitedList[vertexNo] = true; Node *temp = adjList[vertexNo]; while (temp) { if (!visitedList[temp->vertexNumber]) { dfs(temp->vertexNumber); } temp = temp->next; } return; } void bfs(int startnode) { clear(); queue<int> que; cout << "Bfs --> "; que.push(startnode); visitedList[startnode] = true; while (!que.empty()) { int temp = que.front(); cout << temp << " "; que.pop(); Node *current = adjList[temp]; while (current != nullptr) //checking for nodes connected to current node { if (!visitedList[current->vertexNumber]) { visitedList[current->vertexNumber] = true; que.push(current->vertexNumber); } current = current->next; } } cout << "\n"; clear(); return; } }; int main() { cout << "Enter number of nodes: "; int node = 0, edges = 0; cin >> node; cout << "Enter number of edges: "; cin >> edges; Graph G(node, edges); G.createGraph(); int choice = 0, choice2 = 0; while (choice != 3) { cout << "1.Display graph\n"; cout << "2.Traverse the graph\n"; cout << "3.Exit\n"; cout << "Enter Choice: "; cin >> choice; switch (choice) { case 1: G.display(); break; case 2: cout << "1.DFS\n"; cout << "2.BFS\n"; cin >> choice2; if (choice2 == 1) { cout << "Dfs on graph \n"; cout << "Enter the Start Node\n"; int startNode; cin >> startNode; G.dfs(startNode); cout << "\n"; } else { cout << "Bfs on graph \n"; cout << "Enter the Start Node\n"; int startNode; cin >> startNode; G.bfs(startNode); } break; default: break; } } #include <iostream> #include <queue> using namespace std; class Node { private: int vertexNumber; Node *next; public: Node() { vertexNumber = 0; next = nullptr; } Node(int n) { vertexNumber = n; next = nullptr; } friend class Graph; }; class Graph { private: Node **adjList; bool *visitedList; int totalV; int totalE; void addEdge(int source, int destination) { Node *newnode = new Node(destination); newnode->next = adjList[source]; adjList[source] = newnode; } void clear() { for (int i = 0; i < totalV; i++) { visitedList[i] = false; } } public: Graph(int vertices, int edges) { totalE = edges; totalV = vertices; adjList = new Node *[vertices]; visitedList = new bool[vertices]; for (int i = 0; i < vertices; i++) { adjList[i] = nullptr; visitedList[i] = false; } } void createGraph() { int source, destination; for (int i = 0; i < totalE; i++) { cout << "Enter Source and Destination \n"; cout << "Source: "; cin >> source; cout << "Destination: "; cin >> destination; addEdge(source, destination); addEdge(destination, source); } } void display() { cout << "Graph is --> \n"; for (int i = 0; i < totalV; i++) { if (adjList[i] == NULL) { cout << "No connections for node " << i << " \n"; } else { cout << "Node connected to " << i << " --> "; Node *temp = adjList[i]; while (temp != NULL) { cout << temp->vertexNumber << " "; temp = temp->next; } cout << "\n"; } } } void dfs(int vertexNo) { cout << "At node " << vertexNo << "\n"; visitedList[vertexNo] = true; Node *temp = adjList[vertexNo]; while (temp) { if (!visitedList[temp->vertexNumber]) { dfs(temp->vertexNumber); } temp = temp->next; } return; } void bfs(int startnode) { clear(); queue<int> que; cout << "Bfs --> "; que.push(startnode); visitedList[startnode] = true; while (!que.empty()) { int temp = que.front(); cout << temp << " "; que.pop(); Node *current = adjList[temp]; while (current != nullptr) //checking for nodes connected to current node { if (!visitedList[current->vertexNumber]) { visitedList[current->vertexNumber] = true; que.push(current->vertexNumber); } current = current->next; } } cout << "\n"; clear(); return; } }; int main() { cout << "Enter number of nodes: "; int node = 0, edges = 0; cin >> node; cout << "Enter number of edges: "; cin >> edges; Graph G(node, edges); G.createGraph(); int choice = 0, choice2 = 0; while (choice != 3) { cout << "1.Display graph\n"; cout << "2.Traverse the graph\n"; cout << "3.Exit\n"; cout << "Enter Choice: "; cin >> choice; switch (choice) { case 1: G.display(); break; case 2: cout << "1.DFS\n"; cout << "2.BFS\n"; cin >> choice2; if (choice2 == 1) { cout << "Dfs on graph \n"; cout << "Enter the Start Node\n"; int startNode; cin >> startNode; G.dfs(startNode); cout << "\n"; } else { cout << "Bfs on graph \n"; cout << "Enter the Start Node\n"; int startNode; cin >> startNode; G.bfs(startNode); } break; default: break; } }