判断图连通性的几种方法

oyangningtao · 发表于 2022-1-22 11:56:35

一、DFS

某一点出发开始DFS，到最后，只需要判断最后total的值是否是全部的节点就可以，如果小于总节点数，则证明是不连通的，如果相等，则证明是连通的。

int visited[NUM];

int total = 0;

int e[NUM][NUM];//边连接信息，邻接矩阵

void dfs(int i)

{

int j = 0;

visited = 1;

total++;

for(j=1; j<=n; j++)

{

if(e[j]==1 && !visited[j])//i和j有关系相邻，并且j顶点没有被访问过

{

dfs(j);

}

/*判断图是否连通*/

dfs(1);

if(total != n)

{

/*有节点不能访问*/

cout<<"NO";

}

二、BFS
如果从某一个节点广度搜完，有未访问到的节点，那么该图一定是不连通的。
/*用了广度优先搜索的思想*/
bool BFS(MGraph m)
{
   queue<int> q;
   bool visa[MAX_VERTEX_NUM];//之前先初始化为false
   int count=0;
   memset(visa,0,sizeof(visa));

   q.push(1);
   while(!q.empty())
   {
      int v=q.front();
      visa[v]=true;
      q.pop();
      count++;
      for(int i=1;i<=m.vexnum;i++)//把与v连通并且没有被访问过的结点压进队列里面。
      {
            if(m.arc[v].weight)
            if(!visa)
            {
               q.push(i);
               visa=true;//标志被访问过。
            }
      }
   }
if(count==m.vexnum)//如果压进栈的结点个数刚好等于总结点的个数，则连通。
      return true;
return false;
}

oyangningtao · 发表于 2022-1-22 11:56:55

三、并查集

并查集一般用来判断图的连通性，还可以判断图中是否有回路。

如果并查集最后只有一个连通分量，证明此图连通，否则此图不连通。

int set[1000005];

int find(int x){

return x==set[x]?x

set[x]=find(set[x])); //递归查找集合的代表元素，含路径压缩。

}

int main()

{

int n,m,i,x,y;

scanf("%d%d",&n,&m);

for(i=1;i<1000005;++i)       //初始化集合，数组值等于下标的点为根节点。

   set[i]=i;

for(i=0;i<m;++i){

   int a,b;

      scanf("%d%d",&a,&b);

   int fx=find(a),fy=find(b);

   set[fx]=fy;                   //合并有边相连的各个连通分量

}

int cnt=0;

for(i=1;i<=n;++i)       //统计集合个数，即为连通分量个数，为一时图联通。

   if(set[i]==i)

         ++cnt;

if(cnt==1)

      printf("yes\n");

else printf("no\n");

return 0;

}