判断图连通性的三种方法

时间：2025-02-19 07:02:31

       在看哥尼斯堡七桥问题的时候，谈到欧拉回路的问题，不免又想到了图的连通性。想到以后说不定会遇到相关问题，就做下连通性判断算法总结实现。如果一个图是连通的，那么从一个节点开始访问，采用深度优先或者广度优先对它进行遍历，那么必定能够访问完所有的节点。还有一种方法，就是使用图的邻接矩阵的传递闭包。下面是三种方法的实现代码。

#include<iostream>
#include<queue>
#include <>

using namespace std;

#define MAX_VNUM 10

typedef struct
{
 int weight;
}Adj,AdjMatrix[MAX_VNUM][MAX_VNUM];

typedef struct
{
 AdjMatrix adjM;
 int vNum;
}adjGraph;

//创建一个图,节点从0开始,注意传入引用
void CreateGraph(adjGraph &G)
{
 cout<<"输入节点个数："<<endl;
 cin>>;
 cout<<"输入图的邻接矩阵："<<endl;
 for (int i=0;i<;i++)
 {
  for (int j=0;j<;j++)
  {
   cin>>[i][j].weight;
  }
 }
}

//输出一个图
void print(adjGraph G)
{
 for(int i=0;i<;i++)
 {
  for(int j=0;j<;j++)
  {
   cout<<[i][j].weight<<" ";
  }
  cout<<endl;//将换行流写入输出流，清空输出缓冲区
 }
}


//warshall算法判断图的连通性
bool connectivityWarshall(adjGraph G)
{
 adjGraph temp;//临时判断矩阵
  = ;

 //初始化临时判断矩阵
 for (int i =0;i<;i++)
 {
  for(int j=0;j<;j++)
  {
   if ([i][j].weight)
    [i][j].weight = 1;
   else
    [i][j].weight = 0;

  }
  [i][i].weight = 1;
 }

 //矩阵乘法算法Warshall,R(a)
 for (int a =0;a<;a++)
 {
  for (int b=0;b<;b++)
  {
   if([a][b].weight)
   {
    for (int c = 0;c<;c++)
    {
     if ([c][a].weight)
      [c][b].weight = 1;
    }
   }
  }
 }

 //进行判断
 for (int i=0;i<;i++)
 {
  for (int j=0;j<;j++)
  {
   if (![i][j].weight)
    return false;
  }
 }

 return true;
}


//广度优先搜索判断连通性
bool connectivityBFS(adjGraph G)
{
 queue<int> q; //明白队列用途？
 bool visit[MAX_VNUM]; //访问数组
 int count = 0;

 memset(visit,0,sizeof(visit));

 (0); //0节点入队列

 while(!())
 {
  int v = ();
  visit[v] = true;
  ();
  count++;

  //与联通且没有被访问过节点入队列
  for (int i =0;i<;i++)
  {
   if ([v][i].weight)
   {
    if(!visit[i])
    {
     (i);
    }
   }
  }
 }

 if (count == ) return true;
 else return false;

}

//深度优先搜索判断图的连通性,传递数组会改变值,visit需初始化
void dfs_visit(adjGraph G,int firstNode,bool visit[])
{
 visit[firstNode] = 1;

 for(int i=0; i<;i++)
 {
  if([firstNode][i].weight & !visit[i])
   dfs_visit(G,i,visit);
 }
}

bool connectivityDFS(adjGraph G)
{
 bool visit[MAX_VNUM]; //访问数组
 memset(visit,0,sizeof(visit));
 dfs_visit(G,0,visit); //从0节点开始访问

 for(int i=0;i<;i++)
 {
  if (visit[i] == false) return false;
 }

 return true;
}

int main()
{
 adjGraph G;
 CreateGraph(G);
 //print(G);

 if (connectivityWarshall(G)) cout<<"连通"<<endl;
 else cout<<"不连通"<<endl;
 system("pause");
 return 0;
}


相关文章