HTML学堂码匠 2017-12-14
本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法。分享给大家供大家参考,具体如下:
根据维基百科的伪代码实现:
广度优先BFS:
使用队列,集合
标记初始结点已被发现,放入队列
每次循环从队列弹出一个结点
将该节点的所有相连结点放入队列,并标记已被发现
通过队列,将迷宫路口所有的门打开,从一个门进去继续打开里面的门,然后返回前一个门处
""" procedure BFS(G,v) is let Q be a queue Q.enqueue(v) label v as discovered while Q is not empty v ← Q.dequeue() procedure(v) for all edges from v to w in G.adjacentEdges(v) do if w is not labeled as discovered Q.enqueue(w) label w as discovered """ def procedure(v): pass def BFS(G,v0): """ 广度优先搜索 """ q, s = [], set() q.extend(v0) s.add(v0) while q: # 当队列q非空 v = q.pop(0) procedure(v) for w in G[v]: # 对图G中顶点v的所有邻近点w if w not in s: # 如果顶点 w 没被发现 q.extend(w) s.add(w) # 记录w已被发现
深度优先DFS
使用 栈,集合
初始结点入栈
每轮循环从栈中弹出一个结点,并标记已被发现
对每个弹出的结点,将其连接的所有结点放到队列中
通过栈的结构,一步步深入挖掘
"""" Pseudocode[edit] Input: A graph G and a vertex v of G Output: All vertices reachable from v labeled as discovered A recursive implementation of DFS:[5] 1 procedure DFS(G,v): 2 label v as discovered 3 for all edges from v to w in G.adjacentEdges(v) do 4 if vertex w is not labeled as discovered then 5 recursively call DFS(G,w) A non-recursive implementation of DFS:[6] 1 procedure DFS-iterative(G,v): 2 let S be a stack 3 S.push(v) 4 while S is not empty 5 v = S.pop() 6 if v is not labeled as discovered: 7 label v as discovered 8 for all edges from v to w in G.adjacentEdges(v) do 9 S.push(w) """ def DFS(G,v0): S = [] S.append(v0) label = set() while S: v = S.pop() if v not in label: label.add(v) procedure(v) for w in G[v]: S.append(w)
更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。