有向图的邻接表Python表示形式

使用邻接表表示有向图，并且使用回溯法查找有向图中的路径
对于有向图的邻接表表示形式，可以使用字典数据结构来表示

import sys
class Solution:
    def __init__(self):
        # self.graph = {'A':['B','C'],
        #               'B':['C','D'],
        #               'C':['D'],
        #               # 'D':['C'],
        #               'E':['F'],
        #               'F':['C']
        # }
        self.graph = {
            '1':['3','4'],
            '2':['5','4'],
            '3':['6'],
            '4':['3','7','6'],
            '5':['7','4'],
            '7':['6']
        }
    def find_path(self,start,end,path=[]):
        path = path+[start]
        if start==end:
            return path
        if not self.graph.has_key(start):
            return None
        for node in self.graph[start]:
            if node not in path:
                newpath = self.find_path(node,end,path)
                if newpath:
                    return newpath
        return None

    def find_paths(self,start,end,path=[]):
        path = path+[start]
        # path.append(start)
        paths=[]
        if start==end:
            return [path]
        if not self.graph.has_key(start):
            return None
        paths = []
        for node in self.graph[start]:
            if node not in path:
                newpath = self.find_paths(node,end,path)
                if newpath:
                    paths=paths + newpath
        return paths

    def find_shortest_path(self,start,end,path=[]):
        path = path+[start]
        # path.append(start)
        paths=[]
        if start==end:
            return path
        if not self.graph.has_key(start):
            return None
        shortest = None
        for node in self.graph[start]:
            if node not in path:
                newpath = self.find_shortest_path(node,end,path)
                if newpath:
                    if not shortest or len(shortest)>len(newpath):
                        shortest = newpath
        return shortest

    def dfs(self):
        stack = []
        visited = set()
        for key in self.graph:
            # sys.stdout.write(key+'\n')
            if key not in visited:
                sys.stdout.write(key+" ")
                stack.append(key)
                visited.add(key)
            while len(stack)>0:
                tmp = stack[len(stack)-1]
                if not self.graph.has_key(tmp):
                    if len(stack)>0:
                        stack.pop()
                        continue
                for value in self.graph[tmp]:
                    if value not in visited:
                        sys.stdout.write(value+" ")
                        stack.append(value)
                        visited.add(value)
                    else:
                        if len(stack)>0:
                            stack.pop()
                            continue

    def bfs(self):
        from collections import deque
        queue = deque()
        visited=set()
        for key in self.graph.keys():
            if key not in visited:
                queue.append(key)
                visited.add(key)
            while len(queue)>0:
                tmp = queue.popleft()
                sys.stdout.write(tmp+'\t')
                if not self.graph.has_key(tmp):
                    break
                for value in self.graph[tmp]:
                    if value not in visited:
                        queue.append(value)
                        visited.add(value)


    def has_circle(self):
        from collections import deque
        visited = set()
        for key in self.graph.keys():
            if key not in visited:
                queue = deque(key)
                visited.add(key)
                while len(queue)>0:
                    tmp = queue.popleft()
                    if self.graph.has_key(tmp):
                        for value in self.graph[tmp]:
                            if key==value:
                                print "There is circle"
                                return
                            if value not in visited:
                                visited.add(value)
                                queue.append(value)
        print "There is not circle"
        return
if __name__=="__main__":
    s=Solution()
    sys.stdout.write("Breadth first search:"+'\n')
    s.bfs()
    sys.stdout.write('\n')
    sys.stdout.write("Depth first search:"+'\n')
    s.dfs()
    sys.stdout.write('\n')
    sys.stdout.write("find a path:" + '\n')
    print s.find_path('1','6')
    sys.stdout.write("find all paths:" + '\n')
    print s.find_paths('1','6')
    sys.stdout.write("find the shortest path:" + '\n')
    print s.find_shortest_path('1','6')
    sys.stdout.write("judge circle:" + '\n')
    s.has_circle()