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

2744557306

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

9 `4 a# v: ~0 r/ G; {7 G, C0 n关联矩阵是一个二维矩阵，其中行代表顶点，列代表边，矩阵中的元素表示顶点与边的关系，通常用1表示顶点与边相连，0表示不相连。
$ S! M1 T" _8 p& s
' N' L# ~) {* E% f9 f邻接矩阵是一个二维矩阵，其中行和列都代表顶点，矩阵中的元素表示两个顶点之间是否有边相连，通常用1表示相连，0表示不相连。
1 ~  n# R6 S' i6 q& O7 o
+ g5 v6 z" N8 U- {# [, ^' Q0 l# ]关联矩阵和邻接矩阵可以通过相互转换来表示同一个无向图。转换算法如下：

( B0 V1 f  @0 J( Z1. 从关联矩阵到邻接矩阵的转换：
% }& h0 }- Q% G% z: x# r   - 创建一个n x n的全零矩阵，其中n为顶点的个数。
" S: g3 O: Z1 x* F   - 遍历关联矩阵的每一列，找到与该边相关的两个顶点，将这两个顶点在邻接矩阵中的位置设为1。
$ U8 ]! t8 v0 l9 B. H7 n. Y" n
! {9 ^& Q1 M5 Z4 K: i$ M) ~% Y2. 从邻接矩阵到关联矩阵的转换：
8 T$ }4 J5 R5 D& s+ w) A) D   - 创建一个n x m的全零矩阵，其中n为顶点的个数，m为边的个数。
' l$ x  J# Y+ i( O! j" c; M7 O   - 遍历邻接矩阵的上三角部分（因为无向图的邻接矩阵是对称的），找到值为1的位置，表示两个顶点相连。
   - 将这两个顶点所对应的边在关联矩阵中的位置设为1。

5 Z% I3 L% C: Q5 X通过这样的转换算法，我们可以方便地在关联矩阵和邻接矩阵之间进行转换，从而更方便地对无向图进行分析和处理。
* e' S4 ]9 r3 r/ o6 J3 L$ l6 t& c接下来给大家分享一下代码

! W1 J3 H4 E" \3 U2 g9 G8 h
  W) h: D. a! B5 J- j