为了检查图的连通性,我们将尝试使用任何遍历算法遍历所有节点。完成遍历后,如果有任何未访问的节点,则该图未连接。
对于有向图,我们将从所有节点开始遍历以检查连通性。有时,一个边缘可以只有唯一的向外边缘,而没有向内边缘,因此该节点将不会再出现在任何其他起始节点上。
在这种情况下,遍历算法是递归DFS遍历。
Input: Adjacency matrix of a graph 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 Output: 图已连接。
遍历(u,已访问)
输入: 起始节点u和访问节点,以标记访问了哪个节点。
输出-遍历所有连接的顶点。
Begin mark u as visited for all vertex v, if it is adjacent with u, do if v is not visited, then traverse(v, visited) done End
isConnected(图)
输入: 图形。
输出:如果已连接图形,则为True。
Begin define visited array for all vertices u in the graph, do make all nodes unvisited traverse(u, visited) if any unvisited node is still remaining, then return false done return true End
#include<iostream> #define NODE 5 using namespace std; int graph[NODE][NODE] = { {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 1}, {1, 0, 0, 0, 0}, {0, 1, 0, 0, 0} }; void traverse(int u, bool visited[]) { visited[u] = true; //mark v as visited for(int v = 0; v<NODE; v++) { if(graph[u][v]) { if(!visited[v]) traverse(v, visited); } } } bool isConnected() { bool *vis = new bool[NODE]; //对于所有顶点u作为起点,检查所有节点是否可见 for(int u; u < NODE; u++) { for(int i = 0; i<NODE; i++) vis[i] = false; //initialize as no node is visited traverse(u, vis); for(int i = 0; i<NODE; i++) { if(!vis[i]) //if there is a node, not visited by traversal, graph is not connected return false; } } return true; } int main() { if(isConnected()) cout << "图已连接。"; else cout << "图表未连接。"; }
输出结果
图已连接。