Topological Sort处理字符串依赖节点时输出错误如何解决

问题根因 #

你写的原始代码默认节点是0到vertices-1的连续整数，完全不兼容字符串类型的节点，具体问题出在两处：

1. visited用的是列表结构，只能通过整数下标访问，你传入字符串节点的时候，visited[v] = True的操作本身就会直接报错，你没报错是因为遍历节点的时候根本没走到字符串节点的逻辑
2. 拓扑排序触发遍历的逻辑for i in range(self.V)，是直接遍历0、1、2、3四个整数作为节点，完全没有读取你存在self.graph里的sA、sB等实际节点，所以最后栈里存的都是整数，自然输出[3,2,1,0]

修复方案 #

把和节点访问、遍历相关的逻辑改成适配任意类型节点的实现即可，调整点如下：

• 用字典代替列表存储节点访问状态，支持字符串类型的键
• 收集所有实际存在的节点（包括只有入度没有出度的节点），遍历的时候直接遍历实际节点，不要用range(V)
• 最后输出的时候把栈里的元素用->拼接成你要的格式

修复后的完整代码如下：

from collections import defaultdict
class Graph:
    def __init__(self):
        self.graph = defaultdict(list) # 邻接表
        self.all_nodes = set() # 存储所有节点，避免遗漏只有入度的节点

    # 添加边的同时记录所有节点
    def addEdge(self,u,v):
        self.graph[u].append(v)
        self.all_nodes.add(u)
        self.all_nodes.add(v)

    def topologicalSortUtil(self,v,visited,stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.topologicalSortUtil(i,visited,stack)
        stack.insert(0,v)

    def topologicalSort(self):
        # 用字典存访问状态，适配任意类型的节点
        visited = {node:False for node in self.all_nodes}
        stack =[]
        # 遍历所有实际存在的节点
        for node in self.all_nodes:
            if not visited[node]:
                self.topologicalSortUtil(node,visited,stack)
        # 按要求格式输出
        print(' -> '.join(stack))   

g= Graph()
g.addEdge('sA', 'sB')
g.addEdge('sA', 'sC')
g.addEdge('sB', 'sD')
print("Following is a Topological Sort of the given graph")
g.topologicalSort()

运行后输出和你预期的一致：

sA -> sB -> sD -> sC

注：拓扑排序的结果不唯一，只要满足依赖顺序就符合要求，比如sA -> sC -> sB -> sD也是合法的输出。

内容的提问来源于stack exchange，提问作者asd