python - 从邻接表中获取图的拓扑顺序

Question

拥有一个包含Graph G邻接列表的文件，例如:

0 -> 13,16,20,22,4,5
1 -> 12,13,16,17,19,22,23,24,25,3,4
10 -> 13,14,17,20,23,24
11 -> 12,19,20,22,23
12 -> 15,20,24
13 -> 20,21,22
15 -> 23
17 -> 25
19 -> 20,25
2 -> 16,19,3,7
20 -> 22,23
21 -> 22,23,24
22 -> 25
24 -> 25
3 -> 15,21,4
4 -> 10,12,14,15,16,17,18,19,21,23,5
5 -> 11,16,17,20,23,8,9
6 -> 12,14,18,22
7 -> 14,17,22
8 -> 21,24
9 -> 12,14

我想得到它的拓扑排序，Graph G是一个有向无环图。

首先我想解析txt文件并将所有内容放入字典中。但是我遇到了一些问题，首先在读取文件时我丢失了一些东西，我错过了 -> 之后的第一个元素:

f = open('topo.txt', 'r')
    line_list = f.readlines()
    G = {int(line.split('->')[0]): [int(val) for val in line.split(',')[1:] if val] for line in line_list if line}

我会得到:

('G:', {0: [16, 20, 22, 4, 5], 1: [13, 16, 17, 19, 22, 23, 24, 25, 3, 4], 2: [19, 3, 7], 3: [21, 4], 4: [12, 14, 15, 16, 17, 18, 19, 21, 23, 5], 5: [16, 17, 20, 23, 8, 9], 6: [14, 18, 22], 7: [17, 22], 8: [24], 9: [14], 10: [14, 17, 20, 23, 24], 11: [19, 20, 22, 23], 12: [20, 24], 13: [21, 22], 15: [], 17: [], 19: [25], 20: [23], 21: [23, 24], 22: [], 24: []})
[16, 20, 22, 4, 5]

对于每一行，我都缺少一个元素，例如 0 是:[13, 16, 20, 22, 4, 5] 不是 [16, 20, 22, 4, 5] 它错过了 13

然后当使用函数dfs时出现错误:

for v in G[s]: # for every edge (s, v) KeyError: 16

"""Performs a depth first search in graph G starting from vertex s
    Input: G - the input graph in the adjacency list representation via a dictionary
    s - the starting vertex
    explored - a set of explored vertices
    distance - a dictionary representing the topological order of the vertices
    current_label - the current order of the topological order, disguised as a mutable list"""
def dfs(G, s, explored, distance, current_label):
    explored.add(s)
    #print G[s]
    for v in G[s]: # for every edge (s, v)
        if v not in explored:
            dfs(G, v, explored, distance, current_label)
    distance[current_label[0]] = s
    current_label[0] -= 1

"""Performs and outputs a topological sort of graph G using dfs
    Input: G - the input graph in the adjacency list representation via a dictionary
    distance - a dictionary representing the topological order of the vertices"""
def topological_sort(G, distance):
    explored = set()
    current_label = [len(G)]
    for v in G.keys():
        if v not in explored:
            dfs(G, v, explored, distance, current_label)

def main():
    f = open('topo.txt', 'r')
    line_list = f.readlines()
    G = {int(line.split('->')[0]): [int(val) for val in line.split(',')[1:] if val] for line in line_list if line}
    print("G:", G)
    distance = dict()
    topological_sort(G, distance)
    topo = iter(sorted(distance.items()))
    print("A topological order of G is:")
    for _, vertex in topo:
        print( vertex + " ")
    print()

if __name__ == '__main__':
    main()

正确的代码是什么样的？输出应该是

1, 0, 2, 6, 3, 7, 4, 5, 18, 10, 11, 16, 8, 9, 13, 17, 19, 12, 14, 21, 15, 20, 24, 23, 22, 25

Answer 1

line.split(',')[1:] 在 0 -> 13,16,20,22,4,5 上运行时采用部分 16,20,22,4,5 这不是你想要的。它应该是 line.split('->')[1].split(',')。我个人会更明确地编写此内容以避免双重 .split('->') 调用:

def parse_graph(lines):
    G = dict()
    for line in lines:
        left, right = line.split('->')
        G[int(left)] = [int(val) for val in right.split(',')]
    return G
...
G = parse_graph(line_list)

接下来，由于并非每个顶点都在 G 中作为键，因此您应该在 dfs 中添加以下行:

#dfs
...
if s in G: #add this
    for v in G[s]: # for every edge (s, v)
        if v not in explored:
            dfs(G, v, explored, distance, current_label, l)
...

#

最后，将 print( vertex + "") 更改为 print( str(vertex), end=' ')。剩下的好像还好。

您可能需要考虑的另一件事是，不必跟踪两个参数current_label、距离，您可以只保留一个列表顶点 >，可以说，它保留了访问过的顶点的顺序。所以改为

distance[current_label[0]] = s
current_label[0] -= 1

你可以有

vertices.append(s)

效果是一样的。然而，最后，您应该打印 reversed(vertices) 这将是您的拓扑顺序。