- 在线时间
- 466 小时
- 最后登录
- 2025-7-4
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7411 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2803
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1160
- 主题
- 1175
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
无向图是由顶点和边组成的图,其中边没有方向性,即连接两个顶点的边可以从任意一个顶点出发。关联矩阵和邻接矩阵是两种常用的表示无向图的方法。; L r: J. |' ]5 E9 s
4 r, |; |# } \# G M& v6 A关联矩阵是一个二维矩阵,其中行代表顶点,列代表边,矩阵中的元素表示顶点与边的关系,通常用1表示顶点与边相连,0表示不相连。
1 R' z7 g, W8 E, _- s* w4 ` j3 p! k3 ]; P6 C) N
邻接矩阵是一个二维矩阵,其中行和列都代表顶点,矩阵中的元素表示两个顶点之间是否有边相连,通常用1表示相连,0表示不相连。$ Y, J- Q- u; B* J
, h% w9 {" Y. q/ H关联矩阵和邻接矩阵可以通过相互转换来表示同一个无向图。转换算法如下:
% _, V) Q' C/ N. q/ Q! P1 Q# L: W2 x6 S* ~: ~$ j$ N" C( j2 V
1. 从关联矩阵到邻接矩阵的转换:( [; n" h7 F. M, A* j: h2 ~2 }, e* B
- 创建一个n x n的全零矩阵,其中n为顶点的个数。
5 A6 X% B0 s8 ?9 D6 R! A - 遍历关联矩阵的每一列,找到与该边相关的两个顶点,将这两个顶点在邻接矩阵中的位置设为1。, \, @/ d ~6 T
@6 {) `- o) a. x4 @
2. 从邻接矩阵到关联矩阵的转换:
- A" Y- h6 ?; O* C - 创建一个n x m的全零矩阵,其中n为顶点的个数,m为边的个数。4 z1 ~8 G5 d6 ^1 }
- 遍历邻接矩阵的上三角部分(因为无向图的邻接矩阵是对称的),找到值为1的位置,表示两个顶点相连。4 @. Q) X; a7 q, @ S
- 将这两个顶点所对应的边在关联矩阵中的位置设为1。# |- U4 [& j+ Q- E) J. t
+ K* E2 _+ X$ [( `4 j- y$ D0 G# D; {通过这样的转换算法,我们可以方便地在关联矩阵和邻接矩阵之间进行转换,从而更方便地对无向图进行分析和处理。7 o( N( V' M6 m7 |7 U4 O
接下来给大家分享一下代码# z7 g7 G8 s* n$ f
1 C& S/ k, `. J; D
' Y7 C* q4 k6 C7 t6 T/ A/ i" m |
zan
|