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

本文实例讲述了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程序设计有所帮助。

以上是 Python数据结构与算法之图的广度优先与深度优先搜索算法示例 的全部内容, 来源链接: utcz.com/z/361684.html

回到顶部