class Graph(object):    def __init__(self,*args,**kwargs):        self.node_neighbors = {}        self.visited = {}    def add_nodes(self,nodelist):        for node in nodelist:            self.add_node(node)    def add_node(self,node):        if not node in self.nodes():            self.node_neighbors[node] = []    def add_edge(self,edge):        u,v = edge        if(v not in self.node_neighbors[u]) and ( u not in self.node_neighbors[v]):            self.node_neighbors[u].append(v)            if(u!=v):                self.node_neighbors[v].append(u)    def nodes(self):        return self.node_neighbors.keys()    # 深度优先    def depth_first_search(self,root=None):        order = []                if root:            self.dfs(root, order)        for node in self.nodes():            if not node in self.visited:                self.dfs(node, order)        print(order)        return order            def dfs(self, node, order):        self.visited[node] = True        order.append(node)        for n in self.node_neighbors[node]:            if not n in self.visited:                self.dfs(n)    # 广度优先    def breadth_first_search(self, root=None):        queue = []        order = []        if root:            queue.append(root)            order.append(root)            self.bfs(queue, order)        for node in self.nodes():            if not node in self.visited:                queue.append(node)                order.append(node)                self.bfs(queue, order)        print(order)        return order            def bfs(self, queue, order):        while len(queue)> 0:            node  = queue.pop(0)                        self.visited[node] = True            for n in self.node_neighbors[node]:                if (not n in self.visited) and (not n in queue):                    queue.append(n)                    order.append(n)                        # 找一条路径    def find_path(graph, start, end, path=[]):        path = path + [start]        if start == end:            return path        if not graph.has_key(start):            return None        for node in graph[start]:            if node not in path:                newpath = find_path(graph, node, end, path)                if newpath: return newpath        return None            # 找所有路径    def find_all_paths(graph, start, end, path=[]):        path = path + [start]        if start == end:            return [path]        if not graph.has_key(start):            return []        paths = []        for node in graph[start]:            if node not in path:                newpaths = find_all_paths(graph, node, end, path)                for newpath in newpaths:                    paths.append(newpath)        return paths            # 找最短路径    def find_shortest_path(graph, start, end, path=[]):        path = path + [start]        if start == end:            return path        if not graph.has_key(start):            return None        shortest = None        for node in graph[start]:            if node not in path:                newpath = find_shortest_path(graph, node, end, path)                if newpath:                    if not shortest or len(newpath) < len(shortest):                        shortest = newpath        return shortestif __name__ == '__main__':    g = Graph()    g.add_nodes([i+1 for i in range(8)])    g.add_edge((1, 2))    g.add_edge((1, 3))    g.add_edge((2, 4))    g.add_edge((2, 5))    g.add_edge((4, 8))    g.add_edge((5, 8))    g.add_edge((3, 6))    g.add_edge((3, 7))    g.add_edge((6, 7))    print("nodes:", g.nodes())    order = g.breadth_first_search(1)    order = g.depth_first_search(1)