#include <iostream>
//有向图的强连通分量
//翻转边集 深度优先遍历
using namespace std;
typedef struct{
int vexs[10];
int edges[10][10];
int n;
int e;
}MGraph;
void CreateGraphM(MGraph *G){
int N1,N2;
int i,j,k;
printf("Enter the number of vertexs and edges: \n");
scanf("%d %d",&G->n,&G->e);
k=G->n;
for(i=0;i<k;i++)
scanf("%d",&G->vexs[i]);
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0;
cout<<"EDGES: "<<endl;
for(k=0;k<G->e;k++){
cin>>N1>>N2;
G->edges[N1-1][N2-1]=1;
}
return;
}
typedef struct{
int visited[10];
int finishing_time[10];
int discovery_time[10];
int times;
}DFS_DATA;
MGraph TransGraph(MGraph *G){
int i;
int j;
MGraph TMP;
TMP.n = G->n;
TMP.e = G->e;
for(i=0;i<G->n;i++)
TMP.vexs[i]=G->vexs[i];
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
TMP.edges[i][j]=0;
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
if(G->edges[i][j]==1){
TMP.edges[j][i]=1;
}
return TMP;
}
void DFSM(MGraph *G,int index,DFS_DATA *DATA){
DATA->times++;
DATA->discovery_time[index]=DATA->times;
DATA->visited[index]=1;
cout<<G->vexs[index]<<" ";
for(int i=0;i<G->n;i++)
if(G->edges[index][i]==1 && DATA->visited[i]==0){
DFSM(G,i,DATA);
}
DATA->finishing_time[index]=DATA->times;
DATA->times++;
}
void Strongly_Components(MGraph *G){
DFS_DATA *DATA = new DFS_DATA;
MGraph TMP;
int NUMBER=1;
for(int i=0;i<G->n;i++){
DATA->visited[i]=0;
}
for(int i=0;i<G->n;i++){
DATA->finishing_time[i]=0;
DATA->discovery_time[i]=0;
}
DATA->times=0;
TMP=TransGraph(G);
for(int i=0;i<G->n;i++)
if(DATA->visited[i]==0){
cout<<"Strong Component "<<NUMBER<<": ";
DFSM(&TMP,i,DATA);
NUMBER++;
cout<<endl;
}
return;
}
int main()
{
MGraph *G = new MGraph;
CreateGraphM(G);
Strongly_Components(G);
delete G;
return 0;
}
这算法很简单 就是先翻转G 就是所有边的方向倒转
然后用DFS看图能分成几个部分, 这几个部分就是强连通分量
分享到:
相关推荐
在键盘上输入有向图,对任意给定的图(顶点数和边数自定),建立它的邻接表并输出。然后判断该图是否强连通。如果是强连通图,求出该图的所有强连通分量并输出字符
试完成求有向图的强连同分量的算法,并分析算法的时间复杂度
十字链表可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中,对应于有向图中每一条弧有一个结点,对应于每一个顶点也有一个结点。然后建立有向图,然后利用深度优先遍历求解强连通分量
求有向图的强连通分量(scc)Tarjan算法.docx
有向图的强连通分量课程设计报告
求强连通分量 有向图 求强连通分量 有向图 求强连通分量 有向图 求强连通分量 有向图
要求采用邻接矩阵作为无向图的存储结构,邻接表作为有向图的存储结构,完成无向图和有向图的建立,并对建立好的图进行深度和广度优先遍历。具体实现要求: 1. 通过键盘输入图的顶点和边信息,分别构造一个无向图的...
求用连接表存储的有向图的强连通分量的算法
详细地介绍了如何计算强连通分量,图文并茂地阐述了tarjan算法的流程和原理,两者均有模板。
假设我们有一个有向图,其顶点和边如下所示: 顶点:0,1,2,3,4,5,6,7 边:(0→1,(1→2),(2→0),(2→3),(3→4),(4→5),(5→3),(5→6),(6→4),(6→7) 接下来,我将编写一个Python程序,该程序使用Kosaraju...
而有向图G的极大强连通子图S,即添加任意顶点都会导致S失去强连通的属性,则称S为G的强连通分量。 其中有经典的塔尖(Tarjan)算法: 思路不难理解,因为任何一个强连通分量,必定是对原图的深度优先搜索树的子树...
// dfn表示每个结点的搜索次序,scc表示每个结点所属的强连通分量编号,sz表示每个强连通分量所含结点个数// cnt表示搜索次序,scc表示强连通分量编号
强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组节点,这些节点之间互相可达。在有向图中,如果从节点A到节点B存在一条有向路径,并且从节点B到节点A也存在一条有...
深度优先遍历以邻接表表示的图G,输出连通分量的个数和各连通分量的顶点集
)图作为输入,并以拓扑顺序返回其强连通分量作为输出 循环依赖 在各种情况下,依赖关系可能是循环的,并且必须同时执行一组相互依赖的操作。同时执行成本高昂的情况并不少见。使用 Tarjan 算法,可以确定执行相互...
3.有向图的连通分量:在有向图G中,若对于V(G)中任意两个不同的顶点vi和vj,都存在从vi到vj以及从vj到vi的路径,则称G是强连通图。有向图G的极大强连通子图称为G的强连通分量。显然,强连通图只有一个强连通分量,即...
分析了 Gabow 算法和 Kosaraju 算法;
求一个有向图n个点 m 条边,是否是强连通分量,如果是输出Yes, 不是输出No. 数据范围 n < 10000, m < 100000 思路: Tarjan模板题 补习: AC code: /* Tarjan求有向图的强连通分量, */ #include #...