1. 图
定义:图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合.
简单点的说:图由节点和边组成。一个节点可能与众多节点直接相连,这些节点被称为邻居。
如二叉树就为一个简单的图:
更加详细的信息可参见:/polly333/p/4760275.html
2. 算法
1). 广度优先搜索:
广度优先搜索算法(Breadth First Search,BSF),思想是:
1.从图中某顶点v出发,首先访问定点v2.在访问了v之后依次访问v的各个未曾访问过的邻接点;3.然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问;4.直至图中所有已被访问的顶点的邻接点都被访问到;5.如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。
换句话说,广度优先搜索遍历图的过程是以v为起点,由近至远,依次访问和v有路径相通且路 径长度为1,2...的顶点。
如上图的BFS访问顺序为:
A->B->C->D->E->F
2). 深度优先搜索:
图的深度优先搜索(Depth First Search, DFS),和树的前序遍历非常类似。
它的思想:
1.从顶点v出发,首先访问该顶点;2.然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图;3.直至图中所有和v有路径相通的顶点都被访问到。4.若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止
如上图的BFS访问顺序为:
A->B->D->E->C->F
3. 代码
# -*- coding: utf-8 -*-#/usr/bin/pythonfrom collections import dequeimport sysclass Graph(object):def __init__(self, *args, **kwargs):self.order = []#visited order self.neighbor = {}def add_node(self, node):key,val = nodeif not isinstance(val, list):print('node value should be a list') #sys.exit('failed for wrong input')self.neighbor[key] = valdef broadth_first(self, root):if root != None:search_queue = deque()search_queue.append(root)visited = []else:print('root is None')return -1while 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 -1while 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: 以上代码有些许不完善,如果你有改进的方法,请留言,万分感谢!