离散数学实践作业——判断有向图是不是强连通图

离散数学实践作业——判断有向图是不是强连通图Myblog思路:n个顶点,所以要做n次矩阵乘法(因为求回路,如果是求通路的话,就是n-1次。),(所有的矩阵都放在一个二维数组里了~)所有的矩阵都放在同一个mapp数组了,如图:看图可以解释清楚,复杂度有点大哦~~~~~~~但是不想写那些头疼的算法了……最后求可达矩阵,只需要遍历A1的所有点,然后根据A1里点的坐标比如(i,j)对应A2A3(i+k*n,j)k…

My blog

思路:

n个顶点,所以要做n次矩阵乘法 (因为求回路,如果是求通路的话,就是n-1次。),(所有的矩阵都放在一个二维数组里了~)

所有的矩阵都放在同一个mapp数组了,如图:看图可以解释清楚,

1

复杂度有点大哦~~~~~~~ 但是 不想写那些头疼的算法了……

最后求可达矩阵,只需要遍历A1的所有点,然后根据A1里点的坐标比如(i,j) 对应A2 A3(i+k*n,j)k:[0,n] 的坐标 看里面的数据是不是>0 如果是则p[i][[j]=1

最后遍历p ,如果全都是1 则判断为可达矩阵,否则不是。

代码:

/*利用邻接矩阵判断有向图是否为强连通图*/
/*思路,求可达矩阵*/
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <stack>
#define Max 1001
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int mapp[Max][Max],p[Max][Max];
int n,m;
int main() {
	memset(mapp,0,sizeof(mapp));//大矩阵
	memset(p,0,sizeof(p));//可达矩阵 
	//顶点是从1开始标号的。
	cout<<"输入顶点的个数和弧的个数:"<<endl;
	cin>>n>>m;
	cout<<"输入各个弧的起点和终点:"<<endl;
	while(m--) {
		int u,v;
		cin>>u>>v;
		mapp[u][v]++;
	}
	//邻接矩阵构造成功,检验
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=n;j++)
//		cout<<mapp[i][j]<<" ";
//		cout<<endl;
//	}
	//矩阵相乘
	//n个顶点,所以要做n次矩阵乘法 ,(所有的矩阵都放在一个二维数组里了~) 
	/*
	1 1 2
	1 2 3
	1 3 4
	1 4 5
	...
	1 n-2 n-1
	*/
	//正确 
	for(int l=1;l<=n;l++)
	{
		for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			//每一行与每一列相乘的答案 
			for(int k=1; k<=n; k++) {
				mapp[i+l*n][j]+=mapp[i][k]*mapp[k+(l-1)*n][j];
				}
			}
		}
	 } 
	
//	//检验 正确 
//	for(int i=1;i<=n*n;i++)
//	{
//		for(int j=1;j<=n;j++)
//		{
//			cout<<mapp[i][j]<<" ";
//		}cout<<endl;
//	}
	//可达矩阵 
	for(int i=1;i<=n;i++)
	{
		p[i][i]=1; 
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=0;k<=n;k++)
			{
//				cout<<"!!~~"<<mapp[i+k*n][j]<<endl;
				if(mapp[i+k*n][j])
				{
//					cout<<"!!! "<<i+k*n<<" "<<j<<endl;
						p[i][j]=1;
					}
			 } 
		}
	 } 
	 int flag=0;
	 //可达矩阵 
	 cout<<"可达矩阵:"<<endl; 
	 for(int i=1;i<=n;i++)
	 {
	 	for(int j=1;j<=n;j++)
	 	{
		 	cout<<p[i][j]<<" ";
		 	if(p[i][j]==0)flag=1;
		 	else continue;
		 }
		 cout<<endl;

	 }
	 if(flag) cout<<"No"<<endl; 
	 else cout<<"Yes"<<endl; //是强连通图 
	return 0;
}
/*
4 7
1 1
1 2 
1 2
1 3
2 3
3 4
4 3
*/

 

今天的文章离散数学实践作业——判断有向图是不是强连通图分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/30670.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注