企业官网建设流程全解析

郑州网站建设怎么样,产品设计培训中心,软件开发工具03173课后题,注册安全工程师通过率30天从零学Python 通信工程专业科班生#xff0c;用了几十年MATLAB#xff0c;为了过大厂机考#xff0c;不得不自学Python。 文章目录30天从零学Python重要补充四、检测有向环 - Kahn算法1. 有向环与拓扑排序1.1 Kahn 算法核心原理#xff08;通俗版#xff09;1.2 Kahn…30天从零学Python通信工程专业科班生用了几十年MATLAB为了过大厂机考不得不自学Python。文章目录30天从零学Python重要补充四、检测有向环 - Kahn算法1. 有向环与拓扑排序1.1 Kahn 算法核心原理通俗版1.2 Kahn 算法代码实现适配函数调用场景2. 主要坑点2.1 Kahn 算法坑点总结重要补充四、检测有向环 - Kahn算法本集重点补充用于检测有向环的 Kahn 算法拓扑排序的经典实现该算法能高效检测函数调用、任务依赖等场景中是否出现循环依赖比如 A 调用 B、B 调用 C、C 又调用 A是大厂机考中高频考点。1. 有向环与拓扑排序在函数调用场景中有向环就是循环调用比如函数 A 调用 BB 又调用 A这种情况会导致栈无限增长。拓扑排序是对有向无环图DAG的节点进行排序使得所有有向边从排序靠前的节点指向靠后的节点。Kahn 算法通过拓扑排序的过程能直观检测出图中是否存在环。1.1 Kahn 算法核心原理通俗版Kahn 算法像 “剥洋葱” 一样处理节点先统计每个节点的入度有多少个节点指向它对应 “有多少个函数调用当前函数”把所有 “入度为 0” 的节点无被调用的起始函数加入队列不断从队列取出节点删除该节点的所有出边即把它指向的节点入度减 1如果某个节点入度减到 0就加入队列最终如果处理的节点数 总节点数说明存在环剩下的节点形成闭环无法被 “剥完”图片说明假设有5个函数用节点12345表示箭头a指向b表示a调用b。在这里插入图片描述1.2 Kahn 算法代码实现适配函数调用场景fromcollectionsimportdequedefhas_cycle(func_calls): 检测函数调用关系中是否存在有向环 :param func_calls: 函数调用关系格式为 {(调用者): [(被调用者, 内存)], ...} :return: (是否有环, 拓扑排序结果) # 1. 统计所有函数节点all_funcsset()forcallerinfunc_calls:all_funcs.add(caller)forcallee,_infunc_calls[caller]:all_funcs.add(callee)all_funcslist(all_funcs)# 2. 初始化入度字典key:函数value:入度in_degree{func:0forfuncinall_funcs}forcallerinfunc_calls:forcallee,_infunc_calls[caller]:in_degree[callee]1# 被调用者入度1# 3. 初始化队列入度为0的节点起始函数queuedeque()forfuncinall_funcs:ifin_degree[func]0:queue.append(func)# 4. 执行Kahn算法processed0# 记录处理过的节点数topo_order[]# 拓扑排序结果whilequeue:currentqueue.popleft()topo_order.append(current)processed1# 遍历当前节点的所有被调用者入度减1ifcurrentinfunc_calls:forcallee,_infunc_calls[current]:in_degree[callee]-1ifin_degree[callee]0:queue.append(callee)# 5. 判断是否有环处理节点数 总节点数 → 有环has_cycle_flagprocessedlen(all_funcs)returnhas_cycle_flag,topo_order# 测试案例1无环正常函数调用if__name____main__:# 案例10→11281→2128无环call_map1{0:[(1,128)],1:[(2,128)]}cycle1,topo1has_cycle(call_map1)print(f案例1 - 是否有环{cycle1}拓扑排序{topo1})# 输出False[0,1,2]# 案例20→11→22→0有环call_map2{0:[(1,100)],1:[(2,200)],2:[(0,300)]}cycle2,topo2has_cycle(call_map2)print(f案例2 - 是否有环{cycle2}拓扑排序{topo2})# 输出True[]无入度为0的节点2. 主要坑点2.1 Kahn 算法坑点统计节点时容易遗漏必须包含 “调用者” 和 “被调用者” 所有函数否则会误判环入度初始化要覆盖所有节点即使是入度为 0 的起始函数也要初始化入度为 0队列处理时要遍历当前节点的所有出边避免漏减被调用者的入度。总结总结Kahn 算法是检测有向环的高效方法核心是 “入度统计 队列处理”适配函数调用循环依赖检测实现 Kahn算法时要确保覆盖所有节点、正确维护入度。