离散数学实验五 计算两结点间长度为m的路的数目

一、实验目的
熟悉邻接矩阵和两结点间长度为m的路的数目的关系并编程计算。
二、实验内容

定义1  给定简单图G=，V={v1，v2，…，vn}，V中的结点按下标由小到大编序，则n阶方阵A=(aij)称为图G的邻接矩阵。其中 i，j=1，2，…，n。
定理1  设A为简单图G的邻接矩阵，则Am中的i行j列元素amij等于G中联结vi到vj的长度为m的链(或路)的数目。
本实验要求从键盘输入图的邻接矩阵和一正整数m，计算结点两两之间长度为m的路的数目。考虑有向图和无向图。用C语言或MATLAB实现。

三、实验源程序及结果截图
1.实验源程序：

#include int main()
{int i,j,k,l,n,m;//输入关系矩阵，只能输入0或1，若不是0或1，提示输入错误并结束程序 printf("请输入关系矩阵阶数n：\n");scanf("%d",&n);int a[n][n],b[n][n],c[n][n];printf("请输入关系矩阵真值（0或1）：\n");for(i=0;i<n;i++){for(j=0;j<n;j++){scanf("%d",&a[i][j]);}}for(i=0;i<n;i++){for(j=0;j<n;j++){if(a[i][j]!=0&&a[i][j]!=1){printf("输入错误！");return 0;}}}printf("请输入路的长度：\n");scanf("%d",&m);//求路的长度的矩阵 for(i=0;i<n;i++){for(j=0;j<n;j++){b[i][j]=a[i][j];}}for(l=0;l<m-1;l++){for(i=0;i<n;i++){for(j=0;j<n;j++){c[i][j]=0;for(k=0;k<n;k++){c[i][j]+=a[i][k]*b[k][j];}}}for(i=0;i<n;i++){for(j=0;j<n;j++){a[i][j]=c[i][j];}}	}printf("结点两两之间长度为%d的路的数目矩阵为：\n",m);printf("(矩阵第i行第j列表示结点i到结点j长度为%d的路的数目)\n\n",m); for(i=0;i<n;i++){for(j=0;j<n;j++){printf("%d ",a[i][j]);}printf("\n");}return 0; 
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！