本文主要是介绍图的连通性以及割点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先明白几个定理：
- 连通分量：无向图 G 的一个极大连通子图称为 G 的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。
- 强连通图：有向图 G=(V,E) 中，若对于V中任意两个不同的顶点 x 和 y ，都存在从x 到 y 以及从 y 到 x 的路径，则称 G 是强连通图(Strongly Connected Graph)。相应地有强连通分量(Strongly Connected Component)的概念。强连通图只有一个强连通分量，即是其自身；非强连通的有向图有多个强连通分量
1. 判断无向图的连通性。
用bfs或者dfs，遍历，如果能遍历完所有结点，则是连通图。
比如，要求无向图的割点的集合，最容易想到的方法就是依次测试每个结点判断其对图连通性的影响。
有更简单的方法。
2. 有向图的单连通性。对于任意的两个点，i,j，存在i到j或者j到i的路径
1. 最容易想到的算法是floyd算法。
floyd算法本来用以求图中任意两点间的最短路径，大体思路是：
依次以每个点k作为i--->j的中间节点，求d(i,j) = min(d(i,j),d(i,k)+d(k,j))
如果用floyd算法判断任意两个点的连通性？
可以直接用上面的算法，但是可以将加法和min操作转为位运算。
d(i,j) = d(i,j) | (d(i,k) & d(k,j))
2. 上面的算法时间复杂度是O(n^3)
http://hi.baidu.com/735612658gfy/item/e2e8c8d3362fa9f2b3f7777b
思路：判断一个有向图是不是强连通的可以直接用tarjan算法。
但是判断是不是单向联通的就麻烦了。
开始我想用floyd，后来又想到了一条路一条路的找，但是这两种方法的复杂度太高。
正解：对于一个DAG图，若是单向联通的我们可以有这么一个性质，就是存在一条路，这条路可以经过图中的每一个点。下面证明一下。
我们从图中选择一个入度为0的点a，和一个出度为0的点b，则剩下的点肯定都满足在a，b之间。
不妨找一点k ，则a~k~b，剩下的点也肯定在两个~之间的一个，以此类推。
我们先让这张图变成DAG，我们用tarjan算法缩点，这张图就变成了一个DAG图。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
stack<int>s;
struct hh{int u,v,next;}tp[6005],map[6006];int head[1050],mhead[1050],num,mnum,low[1050],lp[1050],now,f[1050];bool in[1050];int n,m,step,total;void add(int a,int b){tp[num].u=a;tp[num].v=b;tp[num].next=head[a]; head[a]=num++;}void madd(int a,int b){map[mnum].u=a; map[mnum].v=b;map[mnum].next=mhead[a]; mhead[a]=mnum++;}void init(){int a,b;num=0; mnum=0;step=total=1;while(!s.empty()) s.pop();for(int i=1;i<=n;i++){in[i]=0;low[i]=lp[i]=f[i]=0;}memset(head,-1,sizeof(head));memset(mhead,-1,sizeof(mhead));scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d",&a,&b);add(a,b);}}void tarjan(int u){int v;low[u]=lp[u]=step++;s.push(u); in[u]=1;for(int i=head[u];i!=-1;i=tp[i].next){v=tp[i].v;if(!low[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(in[v]){low[u]=min(low[u],lp[v]);}}if(low[u]==lp[u]){int haha;while(1){haha=s.top(); s.pop();f[haha]=total; in[haha]=0;if(haha==u)break;}total++;}}void suodian(){for(int i=0;i<num;i++){if(f[tp[i].u]!=f[tp[i].v])madd(f[tp[i].u],f[tp[i].v]);}}bool can[1004][1004];int b[1050];bool dfs(int u,int now){in[u]=1;if(now==total-1)return true;bool flag=0;for(int i=mhead[u];i!=-1;i=map[i].next){flag=dfs(map[i].v,now+1);if(flag)return true;}return false ;}void result(){memset(in,0,sizeof(in));for(int i=1;i<=n;i++){if(!in[i]){bool flag=dfs(i,1);{if(flag){cout<<"Yes"<<endl; return ;}}}}cout<<"No"<<endl;}int main(){int t;scanf("%d",&t);while(t--){init();for(int i=1;i<=n;i++)if(!low[i])tarjan(i);suodian();//重新建图result();}}
也可以用上面的算法求出有向图的单连通分支， 对入度为0点,递归搜寻各向前通路至每一不可再前行点时，可对应得出一单项连通分支
这篇关于图的连通性以及割点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
