1. 图

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



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

如二叉树就为一个简单的图:

常用算法2 - 广度优先搜索 & 深度优先搜索 (python实现)-LMLPHP

2. 算法

1). 广度优先搜索:

广度优先搜索算法(Breadth First Search,BSF),思想是:

换句话说,广度优先搜索遍历图的过程是以v为起点,由近至远,依次访问和v有路径相通且路 径长度为1,2...的顶点。



如上图的BFS访问顺序为:

2). 深度优先搜索:

图的深度优先搜索(Depth First Search, DFS),和树的前序遍历非常类似。

它的思想:

如上图的BFS访问顺序为:

3. 代码

# -*- coding: utf-8 -*-
#/usr/bin/python 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',['one', 'two','three']))
g.add_node(('one',['first','second','third']))
g.add_node(('two',['1','2','3'])) g.broadth_first('1') print('broadth search first:')
print(' ', end=' ')
g.node_print() g.clear() print('\n\ndepth search first:')
print(' ', end=' ')
g.depth_first('1') g.node_print()
print()

ps: 以上代码需要用python3.x运行,python2.x不支持print的关键字参数

PS2: 以上代码有些许不完善,如果你有改进的方法,请留言,万分感谢!

05-07 10:55