python算法实现深度优先和广度优先

首先有一个概念：回溯

　　回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

深度优先算法(Depth First Search, DFS)：

（1）访问初始顶点v并标记顶点v已访问。
（2）查找顶点v的第一个邻接顶点w。
（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找 v的另外一个未访问过的邻接点。
（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。
（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。

如图的DFS访问顺序为：

A->B->D->E->C->F

广度优先算法(Broadth First Search，BSF)：

（1）顶点v入队列。
（2）当队列非空时则继续执行，否则算法结束。
（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
（4）查找顶点v的第一个邻接顶点col。
（5）若v的邻接顶点col未被访问过的，则col入队列。
（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）

如图的BFS访问顺序为：

A->B->C->D->E->F

图

定义 ：图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合.

简单点的说：图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。

from collections import deque

import sys

class Graph(object):

def __init__(self, *args, **kwargs):

self.order = [] # visited order

self.neighbor = {}

def add_node(self, node):

key, val = node

if not isinstance(val, list):

print('node value should be a list')

# sys.exit('failed for wrong input')

self.neighbor[key] = val

def broadth_first(self, root):

if root != None:

search_queue = deque()

search_queue.append(root)

visited = []

else:

print('root is None')

return -1

while search_queue:

person = search_queue.popleft()

self.order.append(person)

if (not person in visited) and (person in self.neighbor.keys()):

search_queue += self.neighbor[person]

visited.append(person)

def depth_first(self, root):

if root != None:

search_queue = deque()

search_queue.append(root)

visited = []

else:

print('root is None')

return -1

while search_queue:

person = search_queue.popleft()

self.order.append(person)

if (not person in visited) and (person in self.neighbor.keys()):

tmp = self.neighbor[person]

tmp.reverse()

for index in tmp:

search_queue.appendleft(index)

visited.append(person)

# self.order.append(person)

def clear(self):

self.order = []

def node_print(self):

for index in self.order:

print(index, end=' ')

if __name__ == '__main__':

g = Graph()

g.add_node(('1_key', ['one_key', '2', '3']))

g.add_node(('one_key', ['first_key', 'two', 'three']))

g.add_node(('first_key', ['1', 'second', 'third']))

g.broadth_first('1_key')

print('broadth search first:')

print(' ', end=' ')

g.node_print()

g.clear()

print('\n\ndepth search first:')

print(' ', end=' ')

g.depth_first('1_key')

g.node_print()

print()

输入如下：

broadth search first:

1_key one_key 2 3 first_key two three 1 second third

depth search first:

1_key one_key first_key 1 second third two three 2 3