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)