广度优先搜索&深度优先搜索

# -*- 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()