Python数据结构与算法之图的广度优先与深度优先搜索算法示例

水深无声 2023-02-12 12:21 68阅读 0赞

本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法。分享给大家供大家参考，具体如下：  
  
根据维基百科的伪代码实现：  
  
广度优先BFS：  
  
使用队列，集合  
  
标记初始结点已被发现，放入队列  
  
每次循环从队列弹出一个结点  
  
将该节点的所有相连结点放入队列，并标记已被发现  
  
通过队列，外汇返佣http://www.fx61.com/，将迷宫路口所有的门打开，从一个门进去继续打开里面的门，然后返回前一个门处  
  
"""  
  
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