本文共 4862 字，大约阅读时间需要 16 分钟。

先来分析一下数学问题：

先构造一个图：

                  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计算机综合

链接：

已知含有 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=======================

转载地址：https://liuchenyang0515.blog.csdn.net/article/details/82974315 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！