无向图关联矩阵和邻接矩阵的相互转换算法

2744557306

无向图是由顶点和边组成的图，其中边没有方向性，即连接两个顶点的边可以从任意一个顶点出发。关联矩阵和邻接矩阵是两种常用的表示无向图的方法。

' C3 G* a- t8 }# D/ W8 C关联矩阵是一个二维矩阵，其中行代表顶点，列代表边，矩阵中的元素表示顶点与边的关系，通常用1表示顶点与边相连，0表示不相连。
2 [8 d. S7 D# R) Q( _2 g
邻接矩阵是一个二维矩阵，其中行和列都代表顶点，矩阵中的元素表示两个顶点之间是否有边相连，通常用1表示相连，0表示不相连。
0 Y6 x$ b$ ?7 L! i
5 E7 `) u5 S! Q2 W" o+ R* X0 a关联矩阵和邻接矩阵可以通过相互转换来表示同一个无向图。转换算法如下：
  ~! C( \0 k, |7 L3 D9 m# u  n
+ Y  R: @  A& R# G" K( [0 F1. 从关联矩阵到邻接矩阵的转换：
$ g% y4 D7 h) ?2 `1 P3 ^# x   - 创建一个n x n的全零矩阵，其中n为顶点的个数。
. C2 a. F& V' S- g  {& u  _0 }   - 遍历关联矩阵的每一列，找到与该边相关的两个顶点，将这两个顶点在邻接矩阵中的位置设为1。
, d/ x7 ~! H! B
2. 从邻接矩阵到关联矩阵的转换：
9 c4 A% h% ^, ^, ]4 b   - 创建一个n x m的全零矩阵，其中n为顶点的个数，m为边的个数。
( K$ D9 }$ g( X. P$ N   - 遍历邻接矩阵的上三角部分（因为无向图的邻接矩阵是对称的），找到值为1的位置，表示两个顶点相连。
   - 将这两个顶点所对应的边在关联矩阵中的位置设为1。
3 a. J$ F: k6 w8 P* L
通过这样的转换算法，我们可以方便地在关联矩阵和邻接矩阵之间进行转换，从而更方便地对无向图进行分析和处理。
8 t7 t. c* c5 h, y& T: ~1 w接下来给大家分享一下代码

3 y, ^1 D5 l) O& I+ K: Q$ Z6 S. M