【30天从零学Python】重要补充四、检测有向环 - Kahn算法

30天从零学Python

通信工程专业科班生，用了几十年MATLAB，为了过大厂机考，不得不自学Python。

重要补充四、检测有向环 - Kahn算法

本集重点补充用于检测有向环的 Kahn 算法（拓扑排序的经典实现），该算法能高效检测函数调用、任务依赖等场景中是否出现循环依赖（比如 A 调用 B、B 调用 C、C 又调用 A），是大厂机考中高频考点。

1. 有向环与拓扑排序

• 在函数调用场景中，有向环就是循环调用（比如函数 A 调用 B，B 又调用 A），这种情况会导致栈无限增长。
• 拓扑排序是对有向无环图（DAG）的节点进行排序，使得所有有向边从排序靠前的节点指向靠后的节点。Kahn 算法通过拓扑排序的过程，能直观检测出图中是否存在环。

1.1 Kahn 算法核心原理（通俗版）

Kahn 算法像 “剥洋葱” 一样处理节点：

1. 先统计每个节点的入度（有多少个节点指向它，对应 “有多少个函数调用当前函数”）；
2. 把所有 “入度为 0” 的节点（无被调用的起始函数）加入队列；
3. 不断从队列取出节点，删除该节点的所有出边（即把它指向的节点入度减 1）；如果某个节点入度减到 0，就加入队列；
4. 最终如果处理的节点数 <总节点数，说明存在环（剩下的节点形成闭环，无法被 “剥完”）
   图片说明：
   假设有5个函数，用节点1，2，3，4，5表示，箭头a指向b表示a调用b。
   在这里插入图片描述
   

1.2 Kahn 算法代码实现（适配函数调用场景）

fromcollectionsimportdequedefhas_cycle(func_calls):""" 检测函数调用关系中是否存在有向环 :param func_calls: 函数调用关系，格式为 {(调用者): [(被调用者, 内存)], ...} :return: (是否有环, 拓扑排序结果) """# 1. 统计所有函数节点all_funcs=set()forcallerinfunc_calls:all_funcs.add(caller)forcallee,_infunc_calls[caller]:all_funcs.add(callee)all_funcs=list(all_funcs)# 2. 初始化入度字典（key:函数，value:入度）in_degree={func:0forfuncinall_funcs}forcallerinfunc_calls:forcallee,_infunc_calls[caller]:in_degree[callee]+=1# 被调用者入度+1# 3. 初始化队列：入度为0的节点（起始函数）queue=deque()forfuncinall_funcs:ifin_degree[func]==0:queue.append(func)# 4. 执行Kahn算法processed=0# 记录处理过的节点数topo_order=[]# 拓扑排序结果whilequeue:current=queue.popleft()topo_order.append(current)processed+=1# 遍历当前节点的所有被调用者，入度减1ifcurrentinfunc_calls:forcallee,_infunc_calls[current]:in_degree[callee]-=1ifin_degree[callee]==0:queue.append(callee)# 5. 判断是否有环：处理节点数 < 总节点数 → 有环has_cycle_flag=processed<len(all_funcs)returnhas_cycle_flag,topo_order# 测试案例1：无环（正常函数调用）if__name__=="__main__":# 案例1：0→1（128），1→2（128）（无环）call_map1={0:[(1,128)],1:[(2,128)]}cycle1,topo1=has_cycle(call_map1)print(f"案例1 - 是否有环：{cycle1}，拓扑排序：{topo1}")# 输出：False，[0,1,2]# 案例2：0→1，1→2，2→0（有环）call_map2={0:[(1,100)],1:[(2,200)],2:[(0,300)]}cycle2,topo2=has_cycle(call_map2)print(f"案例2 - 是否有环：{cycle2}，拓扑排序：{topo2}")# 输出：True，[]（无入度为0的节点）

2. 主要坑点

2.1 Kahn 算法坑点

1. 统计节点时容易遗漏：必须包含 “调用者” 和 “被调用者” 所有函数，否则会误判环；
2. 入度初始化要覆盖所有节点：即使是入度为 0 的起始函数，也要初始化入度为 0；
3. 队列处理时要遍历当前节点的所有出边：避免漏减被调用者的入度。

总结

总结

1. Kahn 算法是检测有向环的高效方法，核心是 “入度统计 + 队列处理”，适配函数调用循环依赖检测；
2. 实现 Kahn算法时要确保覆盖所有节点、正确维护入度。