Python数据结构与算法之图的广度优先与深度优先搜索算法示例
本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法。分享给大家供大家参考，具体如下：
根据维基百科的伪代码实现：
广度优先BFS：
使用队列，集合
标记初始结点已被发现，放入队列
每次循环从队列弹出一个结点
将该节点的所有相连结点放入队列，并标记已被发现
通过队列，将迷宫路口所有的门打开，从一个门进去继续打开里面的门，然后返回前一个门处
""" procedureBFS(G,v)is letQbeaqueue Q.enqueue(v) labelvasdiscovered whileQisnotempty v←Q.dequeue() procedure(v) foralledgesfromvtowinG.adjacentEdges(v)do ifwisnotlabeledasdiscovered Q.enqueue(w) labelwasdiscovered """ defprocedure(v): pass defBFS(G,v0): """广度优先搜索""" q,s=[],set() q.extend(v0) s.add(v0) whileq:#当队列q非空 v=q.pop(0) procedure(v) forwinG[v]:#对图G中顶点v的所有邻近点w ifwnotins:#如果顶点w没被发现 q.extend(w) s.add(w)#记录w已被发现
深度优先DFS
使用栈，集合
初始结点入栈
每轮循环从栈中弹出一个结点，并标记已被发现
对每个弹出的结点，将其连接的所有结点放到队列中
通过栈的结构，一步步深入挖掘
"""" Pseudocode[edit] Input:AgraphGandavertexvofG Output:Allverticesreachablefromvlabeledasdiscovered ArecursiveimplementationofDFS:[5] 1procedureDFS(G,v): 2labelvasdiscovered 3foralledgesfromvtowinG.adjacentEdges(v)do 4ifvertexwisnotlabeledasdiscoveredthen 5recursivelycallDFS(G,w) Anon-recursiveimplementationofDFS:[6] 1procedureDFS-iterative(G,v): 2letSbeastack 3S.push(v) 4whileSisnotempty 5v=S.pop() 6ifvisnotlabeledasdiscovered: 7labelvasdiscovered 8foralledgesfromvtowinG.adjacentEdges(v)do 9S.push(w) """ defDFS(G,v0): S=[] S.append(v0) label=set() whileS: v=S.pop() ifvnotinlabel: label.add(v) procedure(v) forwinG[v]: S.append(w)
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。