给出一个连通图,判断这个图是否为强连通图、单向连通图、弱连通图。以有向图的邻接矩阵形式输入。输入:
输入有若干行
第一行为正整数N(0<N<=100),代表图中点的个数
接下来N行,每行有N个数据,每个数据以空格分隔,代表邻接矩阵。
注意:输入的都是连通图。
输出:
输出有一行,数字1,2,3
1代表强连通图
2代表单向连通图
3代表弱连通图
======================分割线=========================
判断强连通图用tarjan算法(byvoid大神的tarjan算法详解 一遍看不懂可以多看几遍)我把文中的c++实现代码加了注释,这样看起来会更容易些^.^
//输入的是邻接表 void tarjan(int i) { int j; DFN[i]=LOW[i]=++Dindex;//定义DFN(u)为节点u搜索的次序编号(时间戳),Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号 instack[i]=true;//是不是在栈中 Stap[++Stop]=i;//stop是栈中的次序编号 for (edge *e=V[i];e;e=e->next)//邻接表是用链表来实现的,e是与顶点v[i]邻接的节点 { j=e->t;节点的值 //下面的if else if是核心代码,求low[i]和dfn[i]并在回溯时当 DFN(u)=Low(u)时,以u为根的搜索子树上所有节点是一个强连通分量。特别注意的是由定义“Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号”得Low(u)=Min{ DFN(u),Low(v)((u,v)为树枝边,u为v的父节点),DFN(v)((u,v)为指向栈中节点的后向边(非横叉边))} if (!DFN[j]) { tarjan(j); if (LOW[j]<LOW[i]) LOW[i]=LOW[j]; } else if (instack[j] && DFN[j]<LOW[i]) LOW[i]=DFN[j]; } if (DFN[i]==LOW[i]) { Bcnt++;//强连通分量的次序号 do { j=Stap[Stop--]; instack[j]=false; Belong[j]=Bcnt;//顶点j属于第Bcnt个强连通分量 } while (j!=i); } } void solve() { int i; Stop=Bcnt=Dindex=0; memset(DFN,0,sizeof(DFN)); for (i=1;i<=N;i++) if (!DFN[i])//可能一次tarjan并不能把所有点都过一遍 tarjan(i); }
只会判定强连通图还不行,要判断是不是单向连通图,还要用到缩点,缩点顾名思义,就是把强连通分量看成一个普通的点,入度就是其他连通分量中的点指向自己中的点的个数,出度就是自身中的点指向其他强连通分量中的点的个数,具体实现可以把所有都遍历一下,
判断是不是单向连通图只需要判断,缩点后的图是不是入度为0的顶点只有一个,出度为0的顶点也只有一个
辅导费