- 在线时间
- 468 小时
- 最后登录
- 2025-7-19
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7493 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2828
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1160
- 主题
- 1175
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
无向图是由顶点和边组成的图,其中边没有方向性,即连接两个顶点的边可以从任意一个顶点出发。关联矩阵和邻接矩阵是两种常用的表示无向图的方法。
( X5 o$ l2 E" |( G4 W1 d8 v$ z4 O7 t7 c7 ~% P- Y
关联矩阵是一个二维矩阵,其中行代表顶点,列代表边,矩阵中的元素表示顶点与边的关系,通常用1表示顶点与边相连,0表示不相连。
* C. b8 J8 m- v/ J" s3 _! e% Z2 f% d: S4 E- |
邻接矩阵是一个二维矩阵,其中行和列都代表顶点,矩阵中的元素表示两个顶点之间是否有边相连,通常用1表示相连,0表示不相连。
$ b" Y! y6 a4 v, x7 g) m1 a$ ~* ]
关联矩阵和邻接矩阵可以通过相互转换来表示同一个无向图。转换算法如下:( q- y* L( z) h/ Q7 n8 P
$ q3 J* A$ A2 F6 [( }6 b1. 从关联矩阵到邻接矩阵的转换:
2 I% u( z% r! s" c* q5 _ - 创建一个n x n的全零矩阵,其中n为顶点的个数。
3 K0 Y, U) H2 e/ a4 Q1 u# H2 W( `9 J( ? - 遍历关联矩阵的每一列,找到与该边相关的两个顶点,将这两个顶点在邻接矩阵中的位置设为1。( X. J" ~4 K! z+ q
$ O. a! O* L7 D, R/ A3 [( p2. 从邻接矩阵到关联矩阵的转换:+ X% d. u9 \) i" k7 g) Y8 Z$ y7 u
- 创建一个n x m的全零矩阵,其中n为顶点的个数,m为边的个数。+ W1 o1 b) {3 S
- 遍历邻接矩阵的上三角部分(因为无向图的邻接矩阵是对称的),找到值为1的位置,表示两个顶点相连。
. U2 l2 T7 Z. I0 K$ J& c( { - 将这两个顶点所对应的边在关联矩阵中的位置设为1。" v! |! T/ }5 z; \- f; D& N
, Y6 e7 C5 H! p) B6 q, s
通过这样的转换算法,我们可以方便地在关联矩阵和邻接矩阵之间进行转换,从而更方便地对无向图进行分析和处理。
3 {" h# c3 w9 m! U接下来给大家分享一下代码% j' n Y/ s- s" I* X
, _. f7 z8 [1 H. L7 w9 F. q: ~
3 e4 D# H) ?1 u# c, l* H( T |
zan
|