在图中,从某顶点到另一顶点长度为n的路径有多少条?(矩阵乘法的应用) |
您所在的位置:网站首页 › 邻接矩阵计算通路数 › 在图中,从某顶点到另一顶点长度为n的路径有多少条?(矩阵乘法的应用) |
先来分析一下数学问题: 先构造一个图:
0 1 0 1 2 1 2 1 矩阵 A = 1 0 1 1 矩阵A^2 = 1 3 1 2 0 1 0 1 2 1 2 1 1 1 1 0 1 2 1 3
现在我们来进行矩阵乘法,这是A^2的第一行 a[1][1] = a[1][1]*a[1][1] + a[1][2]*a[2][1] + a[1][3]*a[3][1] + a[1][4]*a[4][1] = 2 a[1][2] = a[1][1]*a[1][2] + a[1][2]*a[2][2] + a[1][3]*a[3][2] + a[1][4]*a[4][2] = 1 a[1][3] = a[1][1]*a[1][3] + a[1][2]*a[2][3] + a[1][3]*a[3][3] + a[1][4]*a[4][3] = 2 a[1][4] = a[1][1]*a[1][4] + a[1][2]*a[2][4] + a[1][3]*a[3][4] + a[1][4]*a[4][4] =1 我们来分析第一个式子, a[1][1] = 0,所以a[1][1]*a[1][1] = 0; a[1][2] = 1,a[2][1] = 1,所以a[1][2]*a[2][1] = 1; a[1][3] = 0,所以a[1][3]*a[3][1] = 0; a[1][4] = 1,a[4][1] = 1,所以a[1][4]*a[4][1] = 1; 整个式子相加为2,不知道大家看到这里有没有发现什么。 因为矩阵乘法的原因,两个相乘时,第一个的纵坐标等于第二个的横坐标,例如a[1][2]*a[2][1]就相当于从1“走”到2,再从2“走”到1,而且只有当两者都为1,即存在这两条的时候这个乘积才会为1,那么就表示从1出发到达2的路径+1(往返也算一条路径)。 其实矩阵A的含义可以这样解释,a[i][j]表示的是,从点i出发走一步到点j有多少条路径,不用多说要么为1,要么为0。而乘上一个矩阵A就相当于步数+1。现在我们来分析A^2这个矩阵的含义,a[i][i]表示的是,从点i出发走2步到达点j有多少条路径。那么是否可以表示为A^3,A^4,...,A^n这样的形式呢。 我们看一下A^3中的两次次运算 a^3[1][1] = a^2[1][1]*a[1][1] + a^2[1][2]*a[2][1] + a^2[1][3]*a[3][1] + a^2[1][4]*a[4][1] = 2*0 + 1*1 + 2*0 +1*1 = 2 a^3[1][2] = a^2[1][1]*a[1][2] + a^2[1][2]*a[2][2] + a^2[1][3]*a[3][2] + a^2[1][4]*a[4][2] = 2*1 + 1*0 + 2*1 + 1*1 = 5 这个其实就是在走两步的基础上再走一步。
最后,总结下A^n中,A[i][j]表示的是从i出发走到点j走n步(哪怕来回往返走动也算一条路径),有多少种走法。 比如A^2中,A[0][0]=2表示从0到0走2步有2条路径 第一条:从0到1,再从1到0 第二条:从0到3,再从3到0 A[0][2]=2表示从0走到2位置走2步有2条路径 第一条:从0到1,再从1到2 第二条:从0到3,再从3到2
相关题目: Problem Description 题目给出一个有n个节点的有向图,求该有向图中长度为k的路径条数。方便起见,节点编号为1,2,…,n,用邻接矩阵表示该有向图。该有向图的节点数不少于2并且不超过500. Input 多组输入,每组输入第一行是有向图中节点的数量即邻接矩阵的行列数n。接下来n行n列为该图的邻接矩阵。接下来一行是一个整数k.k小于30. Output 输出一个整数,即为图中长度为k的路径的条数。 Sample Input 3 0 1 0 0 0 1 0 0 0 2 Sample Output 1 import java.util.Scanner; public class Main { static int[][] a; static int[][] b; static int[][] c; public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); a = new int[n][n]; b = new int[n][n]; c = new int[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { a[i][j] = cin.nextInt(); b[i][j] = a[i][j]; } } int m = cin.nextInt(); // 次方 cin.close(); int temp = m; while (--temp > 0) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { a[i][j] = c[i][j]; } } } // a矩阵即为所求,矩阵的m次方代表m步,扫一遍矩阵,对应数字代表路的条数,累加即可得出长度为m的总路径条数 int count = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { count += a[i][j]; } } System.out.println(count); } }
相关题目: 题目来源:2015年408计算机综合 链接:https://www.nowcoder.com/questionTerminal/c46c907ea7e44bbd9ee1ddf299654f0b 已知含有 5 个顶点的图 G 如下图所示。 请回答下列问题: 1)写出图 G 的邻接矩阵 A(行、列下标从 0 开始)。 2)求 A^2,矩阵 A^2 中位于 0 行 3 列元素值的含义是什么? 3)若已知具有 n(n≥2)个顶点的图的邻接矩阵为 B,则 B^m(2≤m≤n)中非零元素的含义是什么?
分析: 1) 2) A^2中,a[0][3]=3,位于 0 行 3 列元素值的含义是从顶点0到顶点3长度为2的路径一共有3条。 3) B^m(2≤m≤n)中位于 i 行 j 列(0≤i,j≤n-1)的非零元素的含义是:图中从顶点 i 到顶点 j长度为 m 的路径条数。
接下来我们用代码计算具体值: import java.util.Scanner; public class Main { static int[][] a; static int[][] b; static int[][] c; public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); a = new int[n][n]; b = new int[n][n]; c = new int[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { a[i][j] = cin.nextInt(); b[i][j] = a[i][j]; } } int m = cin.nextInt(); // 次方 int d1 = cin.nextInt(); int d2 = cin.nextInt(); // 最后需要求第d1行第d2列的元素值 cin.close(); int temp = m; while (--temp > 0) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { a[i][j] = c[i][j]; } } } // a矩阵即为所求,矩阵的m次方代表m步,扫一遍矩阵,对应数字代表路的条数,累加即可得出长度为m的总路径条数 int count = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { count += a[i][j]; } } System.out.println("第" + d1 + "行第" + d2 + "列的值为:" + a[d1][d2]); System.out.println("所以从顶点" + d1 + "到顶点" + d2 + "长度为" + m + "的路径为" + a[d1][d2] + "条"); System.out.println("所有顶点中,长度为" + m + "的路径条数一共是" + count + "条"); } }
将上述问答题的矩阵带入程序 运行结果如下:
===========================Talk is cheap, show me the code======================= |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |