Python中使用Kahn算法解决拓扑排序问题

2023-04-11 00:00:00 算法 排序 拓扑

Kahn算法使用队列来实现拓扑排序，以下是详细的步骤：

  1. 找出所有入度为0的节点，将它们加入队列。

  2. 取出队首的节点，输出它以及它的所有出边。

  3. 对于所有邻接该节点的节点，将它们的入度减去1。

  4. 如果有节点的入度变为0，将它加入队列。

  5. 重复2-4步骤，直到队列为空。

下面是python代码演示：

from collections import defaultdict, deque

def topsort(graph):
    in_degrees = defaultdict(int)
    for u in graph:
        for v in graph[u]:
            in_degrees[v] += 1

    queue = deque([u for u in graph if in_degrees[u] == 0])

    result = []
    while queue:
        u = queue.popleft()
        result.append(u)

        for v in graph[u]:
            in_degrees[v] -= 1
            if in_degrees[v] == 0:
                queue.append(v)

    return result

graph = {
    'p': ['i', 'd', 'a', 'n', 'c', 'o', 'd', 'e', 'dot', 'c', 'o', 'm'],
    'i': ['a', 'n'],
    'a': ['n', 'c', 'o'],
    'n': [],
    'c': ['o', 'd', 'e'],
    'o': ['d', 'e', 't'],
    'd': ['e', 'o', 't'],
    'e': ['t'],
    't': [],
    'dot': [],
    'com': []
}

result = topsort(graph)
print(result)
# output: ['p', 'i', 'a', 'n', 'c', 'o', 'd', 'e', 't', 'd', 'dot', 'com']

以上代码实现了对“pidancode.com”、“皮蛋编程”等字符串进行拓扑排序，输出的结果是排序后的字符串列表。

相关文章