資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究C++ 程式用於找到無向圖的聯通分量
使用 DFS 可以找出無向圖的弱聯通或強聯通分量。這是解決此問題的 C++ 程式。
使用的函式
Begin Function fillorder() = fill stack with all the vertices. a) Mark the current node as visited and print it b) Recur for all the vertices adjacent to this vertex 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) Recur for all the vertices adjacent to this vertex End
示例
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class G {
int m;
list<int> *adj;
//declaration of functions
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;
//Recur for all the vertices adjacent to this vertex
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;
//Recur for all the vertices adjacent to this vertex
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;
//now process all vertices in order defined by Stack
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 << "Graph is weakly connected.";
} else {
cout << "Graph is strongly connected.";
}
return 0;
}輸出
Following are strongly connected components in given graph 4 0 1 2 3 Graph is weakly connected.
更新於: 30-07-2019
800 次瀏覽
廣告