python 图

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 shortest


if __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)