从邻接表中获取图的拓扑排序

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:] when 运行 on 0 -> 13,16,20,22,4,5 takes the part 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，您可以只保留一个列表 vertices，比方说，它保持被访问顶点的顺序。所以而不是

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

你可以

vertices.append(s)

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

从邻接表中获取图的拓扑排序

Get topological ordering of graph from Adjacency list

python

graph

topological-sort