C ++程序在图中查找强连接的组件
使用DFS可以找到给定有向图的弱连接或强连接。这是此问题的C++程序。
使用的功能
Begin Function fillorder() = fill stack with all the vertices. a) Mark the current node as visited and print it b) 为与该顶点相邻的所有顶点递归 c) All vertices reachable from v are processed by now, push v to Stack End Begin Function DFS() : a) Mark the current node as visited and print it b) 为与该顶点相邻的所有顶点递归 End
示例
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class G {
int m;
list<int> *adj;
//功能声明
void fillOrder(int n, bool visited[], stack<int> &Stack);
void DFS(int n, bool visited[]);
public:
G(int N); //constructor
void addEd(int v, int w);
int print();
G getTranspose();
};
G::G(int m) {
this->m = m;
adj = new list<int> [m];
}
void G::DFS(int n, bool visited[]) {
visited[n] = true; // Mark the current node as visited and print it
cout << n << " ";
list<int>::iterator i;
//为与该顶点相邻的所有顶点递归
for (i = adj[n].begin(); i != adj[n].end(); ++i)
if (!visited[*i])
DFS(*i, visited);
}
G G::getTranspose() {
G g(m);
for (int n = 0; n< m; n++) {
list<int>::iterator i;
for (i = adj[n].begin(); i != adj[n].end(); ++i) {
g.adj[*i].push_back(n);
}
}
return g;
}
void G::addEd(int v, int w) {
adj[v].push_back(w); //add w to v's list
}
void G::fillOrder(int v, bool visited[], stack<int> &Stack) {
visited[v] = true; //Mark the current node as visited and print it
list<int>::iterator i;
//为与该顶点相邻的所有顶点递归
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
fillOrder(*i, visited, Stack);
Stack.push(v);
}
int G::print() { //print the solution
stack<int> Stack;
bool *visited = new bool[m];
for (int i = 0; i < m; i++)
visited[i] = false;
for (int i = 0; i < m; i++)
if (visited[i] == false)
fillOrder(i, visited, Stack);
G graph= getTranspose(); //Create a reversed graph
for (int i = 0; i < m; i++)//Mark all the vertices as not visited
visited[i] = false;
int count = 0;
//定义的顺序处理所有顶点
while (Stack.empty() == false) {
int v = Stack.top();
Stack.pop(); //pop vertex from stack
if (visited[v] == false) {
graph.DFS(v, visited);
cout << endl;
}
count++;
}
return count;
}
int main() {
G g(5);
g.addEd(2, 1);
g.addEd(3, 2);
g.addEd(1, 0);
g.addEd(0, 3);
g.addEd(3, 1);
cout << "Following are strongly connected components
in given graph \n";
if (g.print() > 1) {
cout << "图是弱连接。";
} else {
cout << "图已牢固连接。";
}
return 0;
}输出结果
Following are strongly connected components in given graph 4 0 1 2 3 图是弱连接。