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

2744557306

无向图是由顶点和边组成的图，其中边没有方向性，即连接两个顶点的边可以从任意一个顶点出发。关联矩阵和邻接矩阵是两种常用的表示无向图的方法。
2 }. B/ L0 Q) i; R9 ]. X1 v
关联矩阵是一个二维矩阵，其中行代表顶点，列代表边，矩阵中的元素表示顶点与边的关系，通常用1表示顶点与边相连，0表示不相连。

% A8 z) v. |- [2 ^* z8 r4 E邻接矩阵是一个二维矩阵，其中行和列都代表顶点，矩阵中的元素表示两个顶点之间是否有边相连，通常用1表示相连，0表示不相连。
9 m/ W# S0 R8 D2 \
0 p7 W# ]& ~8 c9 e8 G  O$ @% s关联矩阵和邻接矩阵可以通过相互转换来表示同一个无向图。转换算法如下：

; d, J$ j: K) P- E9 P1. 从关联矩阵到邻接矩阵的转换：
; `, T5 I/ y" B, u   - 创建一个n x n的全零矩阵，其中n为顶点的个数。
" O6 v" u7 u# K; W* _2 A% c   - 遍历关联矩阵的每一列，找到与该边相关的两个顶点，将这两个顶点在邻接矩阵中的位置设为1。
9 X6 @3 n0 ?; C' l) g# D
% O* D  j# y8 n/ ^- Z3 K3 e, c7 K2. 从邻接矩阵到关联矩阵的转换：
4 g1 p' J  T0 B& p2 X% K. P" w3 K   - 创建一个n x m的全零矩阵，其中n为顶点的个数，m为边的个数。
   - 遍历邻接矩阵的上三角部分（因为无向图的邻接矩阵是对称的），找到值为1的位置，表示两个顶点相连。
% z- u, ^0 p/ D   - 将这两个顶点所对应的边在关联矩阵中的位置设为1。
' w( ?/ M% I1 s* I7 i. N: {
通过这样的转换算法，我们可以方便地在关联矩阵和邻接矩阵之间进行转换，从而更方便地对无向图进行分析和处理。
接下来给大家分享一下代码
& j# t4 Q# n7 y2 Z  c8 o, @$ K+ j
- `6 H, t3 H/ [/ j3 w0 ^