有向图强连通判断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)。
