# -*- 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
'''
search_queue deque(['A'])
search_queue deque(['B', 'C'])
search_queue deque(['C', 'D', 'E'])
search_queue deque(['D', 'E', 'F'])
search_queue deque(['E', 'F'])
search_queue deque(['F'])
b_order_1 ['A']
b_order_2 ['A', 'B']
b_order_3 ['A', 'B', 'C']
b_order_4 ['A', 'B', 'C', 'D']
b_order_5 ['A', 'B', 'C', 'D', 'E']
b_order_6 ['A', 'B', 'C', 'D', 'E', 'F']
'''
n = 0
while search_queue:
#print ('search_queue', search_queue)
n += 1
person = search_queue.popleft()
self.order.append(person)
#print ('b_order_' + str(n), self.order)
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
'''
search_queue = deque(['A'])
search_queue = deque(['B', 'C'])
search_queue = deque(['D', 'E', 'C'])
search_queue = deque(['E', 'C'])
search_queue = deque(['C'])
search_queue = deque(['F'])
'''
i = 0
while search_queue:
i += 1
#print ('search_queue =', search_queue)
person = search_queue.popleft()
self.order.append(person)
#print ('order_' + str(i), self.order)
if (not person in visited) and (person in self.neighbor.keys()):
tmp = self.neighbor[person]
tmp.reverse()
for index in tmp:
#print ('index =', index)
search_queue.appendleft(index)
#print ('inner_search_queue = ', search_queue)
#print ('******')
visited.append(person)
#self.order.append(person)
def clear(self):
self.order = []
def node_print(self):
#for index in self.order:
# print(index, end=' ')
print ('result order =', self.order)
if __name__ == '__main__':
g = Graph()
g.add_node(('A',['B', 'C']))
g.add_node(('B',['D','E']))
g.add_node(('C',['F']))
g.broadth_first('A')
print('broadth search first:')
g.node_print()
g.clear()
print ('*'*50)
print('depth search first:')
g.depth_first('A')
g.node_print()
g.clear()
网友评论