试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。
【解答】算法如下：[br][/br]int visited[MAXSIZE];[br][/br]int finished[MAXSIZE];[br][/br]int count; //count在第一次深度优先遍历中用于指示finished数组的填充位置[br][/br]void Get_SGraph(OLGraph G)//求十字链表结构储存的有向图G的强连通分量[br][/br]{[br][/br] count=0;[br][/br] for(v=0;v=0;i--) //第二次逆向的深度优先遍历[br][/br] {[br][/br] v=finished(i);[br][/br] if(!visited[v])[br][/br] {[br][/br] printf("\n"); //不同的强连通分量在不同的行输出[br][/br] DFS2(G，v);[br][/br] }[br][/br] }//for[br][/br]}//Get_SGraph[br][/br] void DFS1(OLGraph G，int v)//第一次深度优先遍历的算法[br][/br] {[br][/br] visited[v]=1;[br][/br] for(p=G.xlist[v].firstout;p;p=p->tlink)[br][/br] { w=p->headvex;[br][/br] if(!visited[w]) DFS1(G，w);[br][/br] }//for[br][/br] finished[++count]=v; //在第一次遍历中建立finished数组[br][/br]}//DFS1[br][/br]void DFS2(OLGraph G，int v)//第二次逆向的深度优先遍历的算法[br][/br]{[br][/br] visited[v]=1;[br][/br] printf("%d"，v); //在第二次遍历中输出结点序号[br][/br] for(p=G.xlist[v].firstin;p;p=p->hlink)[br][/br] {[br][/br] w=p->tailvex;[br][/br] if(!visited[w]) DFS2(G，w);[br][/br] }//for[br][/br]}//DFS2求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同，也为O(n+e)。
本题目来自[网课答案]本页地址：https://www.wkda.cn/ask/tpzjatzmjezajzo.html
举一反三
内容
- 0
下面（ ）方法可用于求无向图的连通分量。 A: 遍历 B: 拓扑排序 C: Dijkstra算法 D: Prim算法
- 1
对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。
- 2
设计一个算法，求出无向图G的连通分量个数。
- 3
【简答题】假设图 G 采用邻接矩阵存储。给出图的广度优先遍历算法,并分析算法的时间复杂度
- 4
强连通分量是有向图中的极大强连通子图。( )