c++ - To check if a graph is connected using BFS and print MST -
i have stored graph nodes 1,2,3,4,... in adjacency list. wrote code breadth first search (bfs). bfs works perfect don't know procedure find out if graph connected or disconnected , print minimum spanning tree of graph if connected? example of graph stored in adjacency list:
1 3 4 2 4 3 1 4 4 2 1 3 and code bfs:
int visit[999] = { 0 }; q.enqueue(0); while (!q.isempty()) { y = q.dequeue(); traverse = g[y]; while (traverse->link != 0) { if (visit[traverse->data-1] == 0) { visit[traverse->data-1] = 1; parent = traverse->data; q.enqueue(traverse->data-1); } traverse = traverse->link; } if (visit[traverse->data - 1] == 0) { visit[traverse->data - 1] = 1; parent = traverse->data; q.enqueue(traverse->data - 1); } }
so figured out , put reference others :)
int parent = 1; gcounter++; p = 0; int visit[999] = { 0 }; int c[999] = { 0 }; int k = 0; int z = 0; queue q; q.enqueue(0); while (!q.isempty()) { y = q.dequeue(); traverse = g[y]; while (traverse->link != 0) { if (visit[traverse->data-1] == 0) { if (y + 1 != traverse->data) { c[z] = y + 1;z++; c[z] = traverse->data; z++; } p++; visit[traverse->data-1] = 1; parent = traverse->data; q.enqueue(traverse->data-1); } traverse = traverse->link; } if (visit[traverse->data - 1] == 0) { if (y + 1 != traverse->data) { c[z] = y + 1; z++; c[z] = traverse->data; z++; } p++; visit[traverse->data - 1] = 1; parent = traverse->data; q.enqueue(traverse->data - 1); } } if (p < lcounter) //lcounter-> lines -> total number of nodes { writefile << "the graph disconnected" << endl; } else { writefile << "the graph connected , it's mst is: "; (z = 0; c[z+1] != 0; z++) { writefile << "(" << c[z] << "," << c[z + 1] << ") "; z++; } writefile << endl; }
Comments
Post a Comment