创建图的邻接矩阵输出图的邻接矩阵3. 根据邻接矩阵创建邻接表输出邻接表销毁邻接表
时间: 2024-06-05 17:04:47 浏览: 208
图的邻接矩阵和邻接表实现
邻接矩阵是一种用于表示图形的数据结构,其中每个节点都用一个行和一个列来表示。如果两个节点之间有一条边,则相应的矩阵元素为1,否则为0。邻接矩阵可以通过以下步骤创建:
1. 定义一个二维数组,数组的大小为节点数×节点数。
2. 根据节点之间的连接情况,在相应的数组元素中标记1或0。
例如,以下是一个包含4个节点和4条边的无向图的邻接矩阵:
```
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
```
根据邻接矩阵创建邻接表的过程如下:
1. 对于每个节点,创建一个链表。
2. 遍历邻接矩阵中的每个元素,如果该元素为1,则在相应的链表中添加一个节点,该节点表示与当前节点相连的另一个节点。
例如,以上邻接矩阵所对应的邻接表如下:
```
0 -> 1 -> 2
1 -> 0 -> 2
2 -> 0 -> 1 -> 3
3 -> 2
```
销毁邻接表的过程很简单,只需要依次遍历每个链表,并释放其节点即可。
阅读全文