Untitled
unknown
plain_text
2 years ago
2.8 kB
2
Indexable
Never
#include <iostream> #include <queue> using namespace std; class graph { int G[100][100]; int IND[100]; int B[100]; int size; public: graph(int m) { size = m; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { G[i][j] = 0; } } } void insert(int x, int y) { if (G[y][x] == 0) { G[x][y] = 1; } else { cout << "\nNo cycles in graph" << endl; } } int indegree(int node) { int in_cnt = 0; for (int i = 0; i < size; i++) { if (G[i][node] == 1) { in_cnt++; } } return in_cnt++; } void display() { cout << endl; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { cout << G[i][j] << " "; } cout << endl; } } void top_sort() { queue<int> q; int j = 0; for (int i = 0; i < size; i++) { IND[i] = indegree(i); if (IND[i] == 0) { q.push(i); } } while (!q.empty()) { int k = q.front(); q.pop(); B[j++] = k; for (int i = 0; i < size; i++) { if (G[k][i] == 1) { G[k][i] = 0; IND[i] = IND[i] - 1; if (IND[i] == 0) { q.push(i); } } } } for (int i = 0; i < size; i++) { cout << B[i] << " | "; } cout << endl; } }; int main() { int size; cout << "\nEnter total vertex in graph: "; cin >> size; graph g(size); int choice; while (true) { cout << "\n1.To add points \n2.To display \n3.Topological Sort" << endl; cout << "Enter the choice: "; cin >> choice; if (choice == 1) { int cnt = 0; int td; cout << "\nHow many points you want to add: "; cin >> td; while (td != cnt) { int x, y; cout << "\nEnter the point as source and destination" << endl; cin >> x >> y; g.insert(x, y); cnt++; } } else if (choice == 2) { g.display(); } else if (choice == 3) { g.top_sort(); } } return 0; }