数据结构:图的邻接矩阵

来源：百度知道 编辑：UC知道 时间：2024/06/04 03:48:23
某包含3个顶点的有向图的邻接矩阵A如下:
1 1 0
0 0 1
1 0 0
表示:1->1, 1->2, 2->3, 3->1经过一边即可
如果要知道一顶点到另一顶点经过两边矩阵B,则B=AA,如下:
1 1 1
1 0 0
1 1 0
表示:顶点1->1, 2->1, 3->1, ...可经过二边.
同理要经过3边的矩阵C=AAA ...
我想问一下为什么会这样呢?我要知道原理,谢谢各位了.

那要理解矩阵的相乘,先拿两边举例
-----------------------------------------------
原矩阵如下:
a b c
a 1 1 0 1 1 0
b 0 0 1 0 0 1
c 1 0 0 1 0 0
-----------------------------------------------
上面第一行表示从a射出的所有边,a可以到a也可以到b,所以都是1,而第一列表示射回a的边,a,c都可以射回来.
-------------------------------------------------
因此两矩阵相乘,第一个元素aa=1*1+1*0+0*1=1;是第一行乘一第一列,正好是一出一进,两条边
-------------------------------------------------
而如果进出都为1就是1*1时才能有值,表示有一条这样的两边,1*0表示只出去了没回来,就没有值了.0*0,0*1就不用说了..
-------------------------------------------------而几个加起来之和就是所有从a出去再回a的两边的个数,所以相乘后的结果就是表示两边的个数之和,因此,3边4边就依次类推了...