Python中图的邻接链表如何表示
时间: 2023-07-11 10:27:36 浏览: 76
Python中可以使用字典(dictionary)来表示邻接链表,其中字典的键(key)表示图的每个节点,对应的值(value)是一个列表(list),包含了与该节点相邻的所有节点。
举个例子,如果有一张无向图,其中节点0、1、2相邻,节点1、3相邻,节点2、4相邻,那么可以用如下代码表示邻接链表:
```
adj_list = {
0: [1, 2],
1: [0, 3],
2: [0, 4],
3: [1],
4: [2]
}
```
这里,节点0的邻居节点是1和2,因此adj_list[0]的值是[1, 2];节点1的邻居节点是0和3,因此adj_list[1]的值是[0, 3],以此类推。
相关问题
有向图的正邻接链表和逆邻接链表。
有向图的正邻接链表和逆邻接链表是用来表示有向图中节点之间关系的数据结构。
正邻接链表是指对于每个节点,记录其指向其他节点的边的信息。逆邻接链表是指对于每个节点,记录指向该节点的边的信息。
下面是一个示例来说明正邻接链表和逆邻接链表的概念:
假设有以下有向图:
```
1 -> 2
1 -> 3
2 -> 3
3 -> 4
```
对于节点1,其正邻接链表为:[2, 3],表示节点1指向节点2和节点3。
对于节点2,其正邻接链表为:,表示节点2指向节点3。
对于节点3,其正邻接链表为:,表示节点3指向节点4。
对于节点2,其逆邻接链表为:,表示指向节点2的边来自节点1。
对于节点3,其逆邻接链表为:[1, 2],表示指向节点3的边来自节点1和节点2。
对于节点4,其逆邻接链表为:,表示指向节点4的边来自节点3。
通过正邻接链表和逆邻接链表,我们可以方便地获取节点的出度和入度,以及节点之间的关系。
实现邻接链表和逆邻接链表两种求顶点入度的算法
实现邻接链表和逆邻接链表两种求顶点入度的算法:
邻接链表求顶点入度的算法:
1. 初始化一个长度为n的数组indegree,用于存储每个顶点的入度。
2. 遍历每个顶点的邻接表,将每个邻接点的入度加1。
3. 遍历indegree数组,输出指定顶点的入度。
逆邻接链表求顶点入度的算法:
1. 初始化一个长度为n的数组indegree,用于存储每个顶点的入度。
2. 遍历每个顶点的逆邻接表,将每个逆邻接点的入度加1。
3. 遍历indegree数组,输出指定顶点的入度。
示例代码如下:
```python
# 邻接链表求顶点入度
def get_indegree(graph, vertex):
n = len(graph)
indegree = [0] * n
for i in range(n):
for j in graph[i]:
if j == vertex:
indegree[i] += 1
return indegree[vertex]
# 逆邻接链表求顶点入度
def get_reverse_indegree(graph, vertex):
n = len(graph)
indegree = [0] * n
for i in range(n):
for j in graph[i]:
if i == vertex:
indegree[j] += 1
return indegree[vertex]
```