判断一个图是否连通

男娘i 2022-04-23 03:26 248阅读 0赞

总的来说，可以用DFS（O（v^2））和BFS(O(v+e))的思想都能实现，只要从一个点出发，然后判断是否能遍历完所有的点。还有就是Tarjan算法和GABOW算法，这个没研究过，据说很好用。

实现办法一：用Warshall算法，时间复杂度为O（v^3），时间复杂度较大。

实现办法二：拓扑排序（多用于有向图）。

实现办法三：用BFS和visa\[\]标志数组，看看从一个点出发，是否能访问完所有的点。

实现办法四：用DFS，（思想和办法三相差无几，递归用while循环代替而已）核心代码如下：

用邻接链表表示的图

void dfs(int s)  
\{  
visit\[s\] = true;  
cnt++;  
node\* p = vnode\[s\];  
for (;p; p = p->next)  
\{  
if (!visit\[p->v\])

dfs(p->v);  
\}  
return;  
\}

cnt为全局变量，当cnt与总结点数相等时，就连通。

下面把办法二和办法三用完全代码实现一下：

【无向图和邻接矩阵表示】

\#include<iostream>  
\#include<queue>  
using namespace std;  
\#define MAX\_VERTEX\_NUM 20  
typedef struct  
\{  
int weight;  
\}Adj,AdjMatrix\[MAX\_VERTEX\_NUM\]\[MAX\_VERTEX\_NUM\];

typedef struct  
\{  
AdjMatrix arc;  
int vexnum;  
\}MGraph;

void CreateMGraph(MGraph &M)  
\{

cout<<"请输入结点的个数:";  
cin>>M.vexnum;  
cout<<"请输入该图的邻接矩阵:"<<endl;  
for(int i=1;i<=M.vexnum;i++)  
\{  
for(int j=1;j<=M.vexnum;j++)  
\{  
cin>>M.arc\[i\]\[j\].weight;  
\}  
\}  
\}

void print(MGraph m)  
\{  
for(int i=1;i<=m.vexnum;i++)  
\{  
for(int j=1;j<=m.vexnum;j++)  
\{  
cout<<m.arc\[i\]\[j\].weight<<" ";  
\}  
cout<<endl;  
\}  
\}

bool Connectivity\_Warshall(MGraph m)  
\{  
MGraph judgemat;  
judgemat.vexnum=m.vexnum;  
int i,j;  
for(i=1;i<=m.vexnum;i++)  
\{  
for(j=1;j<=m.vexnum;j++)  
\{  
if(m.arc\[i\]\[j\].weight)  
judgemat.arc\[i\]\[j\].weight=1; //初始化判断矩阵  
else  
judgemat.arc\[i\]\[j\].weight=0;  
\}  
judgemat.arc\[i\]\[i\].weight=1;  
\}

for(int x=1;x<=judgemat.vexnum;x++) //采用warshall算法判断图的连通性。注意下标。  
\{  
for(int y=1;y<=judgemat.vexnum;y++)  
\{  
if(judgemat.arc\[x\]\[y\].weight)  
\{  
for(int z=1;z<=judgemat.vexnum;z++)  
\{  
if(judgemat.arc\[z\]\[x\].weight)  
judgemat.arc\[z\]\[y\].weight=1;  
\}  
\}  
\}  
//print(judgemat);  
\}  
for(i=1;i<=judgemat.vexnum;i++)  
\{  
for(j=1;j<=judgemat.vexnum;j++)  
if(!judgemat.arc\[i\]\[j\].weight)//只要还没全为1就不连通。  
return false;  
\}  
return true;  
\}

/\*用了广度优先搜索的思想\*/  
bool Connectivity\_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\]\[i\].weight)  
if(!visa\[i\])  
\{  
q.push(i);  
visa\[i\]=true;//标志被访问过。  
\}  
\}  
\}  
if(count==m.vexnum)//如果压进栈的结点个数刚好等于总结点的个数，则连通。  
return true;  
return false;  
\}

int main()  
\{  
MGraph MAP;  
CreateMGraph(MAP);

cout<<"Use Warshall:"<<endl;  
if(Connectivity\_Warshall(MAP))  
cout<<"Connectivity!"<<endl;  
else  
cout<<"Not connectivity!"<<endl;

cout<<"Use BFS:"<<endl;  
if(Connectivity\_BFS(MAP))  
cout<<"Connectivity!"<<endl;  
else  
cout<<"Not Connectivity!"<<endl;

return 0;  
\}