以邻接矩阵的形式创建一个无向图;以邻接表的形式创建一个无向图
时间: 2023-11-10 07:13:12 浏览: 106
将一个无向图的邻接表转换为邻接矩阵算法.doc.doc
5星 · 资源好评率100%
1. 以邻接矩阵的形式创建一个无向图:
假设我们有一个无向图,其中节点数为5,边数为7,其图示如下:
```
1 --- 2
/ | \
3--4 5
```
邻接矩阵的形式如下:
```
1 2 3 4 5
1 0 1 1 1 0
2 1 0 0 0 1
3 1 0 0 1 0
4 1 0 1 0 0
5 0 1 0 0 0
```
其中,矩阵的行和列分别代表图中的节点编号,矩阵中的元素表示两个节点之间是否有边相连。如果节点 i 和节点 j 之间有边相连,则矩阵中的第 i 行第 j 列和第 j 行第 i 列均为 1;否则,两个位置都为 0。
2. 以邻接表的形式创建一个无向图:
同样以上述无向图为例,邻接表的形式如下:
```
1 -> 2 -> 3 -> 4
2 -> 1 -> 5
3 -> 1 -> 4
4 -> 1 -> 3
5 -> 2
```
其中,每个节点都对应着一个链表,链表中的每个元素表示与该节点相邻的节点编号。例如,1 对应的链表中依次为 2、3、4,即节点 1 与节点 2、3、4 相邻。对于无向图中的每条边,我们需要在两个节点的链表中分别添加对方的节点编号。
阅读全文