python数据结构之图深度优先和广度优先实例详解
本文实例讲述了python数据结构之图深度优先和广度优先用法。分享给大家供大家参考。具体如下：
首先有一个概念：回溯
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
深度优先算法：
（1）访问初始顶点v并标记顶点v已访问。
（2）查找顶点v的第一个邻接顶点w。
（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。
（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。
（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。
广度优先算法：
（1）顶点v入队列。
（2）当队列非空时则继续执行，否则算法结束。
（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
（4）查找顶点v的第一个邻接顶点col。
（5）若v的邻接顶点col未被访问过的，则col入队列。
（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。
代码：
#!/usr/bin/python
#-*-coding:utf-8-*-
classGraph(object):
def__init__(self,*args,**kwargs):
self.node_neighbors={}
self.visited={}
defadd_nodes(self,nodelist):
fornodeinnodelist:
self.add_node(node)
defadd_node(self,node):
ifnotnodeinself.nodes():
self.node_neighbors[node]=[]
defadd_edge(self,edge):
u,v=edge
if(vnotinself.node_neighbors[u])and(unotinself.node_neighbors[v]):
self.node_neighbors[u].append(v)
if(u!=v):
self.node_neighbors[v].append(u)
defnodes(self):
returnself.node_neighbors.keys()
defdepth_first_search(self,root=None):
order=[]
defdfs(node):
self.visited[node]=True
order.append(node)
forninself.node_neighbors[node]:
ifnotninself.visited:
dfs(n)
ifroot:
dfs(root)
fornodeinself.nodes():
ifnotnodeinself.visited:
dfs(node)
printorder
returnorder
defbreadth_first_search(self,root=None):
queue=[]
order=[]
defbfs():
whilelen(queue)>0:
node=queue.pop(0)
self.visited[node]=True
forninself.node_neighbors[node]:
if(notninself.visited)and(notninqueue):
queue.append(n)
order.append(n)
ifroot:
queue.append(root)
order.append(root)
bfs()
fornodeinself.nodes():
ifnotnodeinself.visited:
queue.append(node)
order.append(node)
bfs()
printorder
returnorder
if__name__=='__main__':
g=Graph()
g.add_nodes([i+1foriinrange(8)])
g.add_edge((1,2))
g.add_edge((1,3))
g.add_edge((2,4))
g.add_edge((2,5))
g.add_edge((4,8))
g.add_edge((5,8))
g.add_edge((3,6))
g.add_edge((3,7))
g.add_edge((6,7))
print"nodes:",g.nodes()
order=g.breadth_first_search(1)
order=g.depth_first_search(1)
结果：
nodes:[1,2,3,4,5,6,7,8]
广度优先：
[1,2,3,4,5,6,7,8]
深度优先：
[1,2,4,8,5,3,6,7]
希望本文所述对大家的Python程序设计有所帮助。