Python中图的邻接链表如何表示

在Python中，可以使用字典来表示邻接链表。具体来说，字典的键表示图的节点，键对应的值则是一个列表，列表中存储了该节点所连接的其他节点。例如，下面的代码表示了一个简单的无向图的邻接链表：

graph = {'A': ['B', 'C'],
         'B': ['A', 'C', 'D'],
         'C': ['A', 'B', 'D'],
         'D': ['B', 'C']}

其中，节点 A 连接了节点 B 和节点 C，节点 B 连接了节点 A、C 和 D，以此类推。可以看到，使用邻接链表可以很方便地表示节点之间的连接关系，同时也可以很容易地实现遍历等操作。

相关问题

有向图的正邻接链表和逆邻接链表。

有向图的正邻接链表和逆邻接链表是用来表示有向图中节点之间关系的数据结构。

正邻接链表是指对于每个节点，记录其指向其他节点的边的信息。逆邻接链表是指对于每个节点，记录指向该节点的边的信息。

下面是一个示例来说明正邻接链表和逆邻接链表的概念：

假设有以下有向图：

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数组，输出指定顶点的入度。

示例代码如下：

# 邻接链表求顶点入度
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]