有向圖強連通判斷C/C++
2019-11-06 07:12:56
供稿：網友
有向圖強連通判斷
在有向圖G中，如果兩個頂點間至少存在一條路徑，稱兩個頂點強連通(strongly connected)。 如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。 非強連通圖有向圖的極大強連通子圖，稱為強連通分量(strongly connected components)。 走個形式，先拋個定義出來，不需要死記定義，給個圖能判斷出是否為強連通圖即可。 有向圖強連通判斷比無向圖復雜些，無向圖只需任意找個定點開始DFS或BFS，再遍歷一次visit[]數組，存在沒被遍歷的點，即代表不是強連通。 而有向圖因存在方向，例如A->B，而B->A要通過B->C->A甚至更遠的路徑再能找到A。 本算法比較“鴰貔”，算法復雜度為O(V*(V+E))。算法思想很簡單，調用DFS搜索V(頂點的個數)次，判斷是否可達即可。直接甩算法：#include <iostream>#include <malloc.h>using namespace std;#define VRType int#define VertexType int#define MAX_VERTEX_NUM 30typedef struct ArcNode{ int adjvex; VRType info; struct ArcNode *nextarc;}ArcNode;typedef struct VNode{ VertexType data; struct ArcNode *firstarc;}AdjList[MAX_VERTEX_NUM];typedef struct{ AdjList vertices[MAX_VERTEX_NUM]; int vexnum, arcnum;}ALGraph;void CreatALGraph(ALGraph *&G){ int a, b, i; ArcNode *arc; G = (ALGraph *) malloc (sizeof(ALGraph)); cin>>G->vexnum>>G->arcnum; for(i = 0; i< G->vexnum; i++){ G->vertices[i]->data = i; G->vertices[i]->firstarc = NULL; } for(i = 1; i<= G->arcnum; i++){ cin>>a>>b; arc = (ArcNode *) malloc (sizeof(ArcNode)); arc->nextarc = NULL; arc->adjvex = b; arc->nextarc = G->vertices[a]->firstarc; G->vertices[a]->firstarc = arc; }}int visit[MAX_VERTEX_NUM] = {0};void DFS(ALGraph *G, VertexType u, VertexType v, int &flag){ ArcNode *arc; if(u == v){ flag = 1; return; } for(int i = 0; i< G->vexnum; i++) if(G->vertices[i]->data == u) break; int k = i; visit[k] = 1; arc = G->vertices[k]->firstarc; while(arc){ if(!visit[arc->adjvex]) DFS(G, arc->adjvex, v, flag); arc = arc->nextarc; }}void Judge(ALGraph *G, int &flag){ for(int i = 0; i< G->vexnum; i++) for(int j = 0; j< G->vexnum; j++){ flag = 0; DFS(G, i, j, flag); if(!flag) return; for(int k = 0; k< G->vexnum; k++) visit[k] = 0; }}int main(){ int flag; ALGraph *g; CreatALGraph(g); Judge(g, flag); if(flag) cout<<"yes"; else cout<<"no"; return 0;} 過陣子附上Tarjan算法和Kosaraju算法，這兩種算法的不需要遍歷那么多次，復雜度僅有O(V+E)。
