2019-03-13

python实现图：
邻接表表示：

a,b,c,d,e,f,g,h=range(8)
N=[[b,c,d,e,f],#a
   [c,e],#b
   [d],#c
   [e],#d
   [f],#e
   [c,g,h],#f
   [f,h],#g
   [f,g]#h
   ]
N

邻接矩阵表示：

matrix = [[0, 1, 1, 1, 1, 1, 0, 0],  # a
             [0, 0, 1, 0, 1, 0, 0, 0],  # b
             [0, 0, 0, 1, 0, 0, 0, 0],  # c
             [0, 0, 0, 0, 1, 0, 0, 0],  # d
             [0, 0, 0, 0, 0, 1, 0, 0],  # e
             [0, 0, 1, 0, 0, 0, 1, 1],  # f
             [0, 0, 0, 0, 0, 1, 0, 1],  # g
             [0, 0, 0, 0, 0, 1, 1, 0]]  # h

深度优先，广度优先：

#!/usr/bin/python
# -*- coding: utf-8 -*-

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 = []
        def dfs(node):
            self.visited[node] = True
            order.append(node)
            for n in self.node_neighbors[node]:
                if not n in self.visited:
                    dfs(n)
        if root:
            dfs(root)

        for node in self.nodes():
            if not node in self.visited:
                dfs(node)
        
        return order
    
    

    def breadth_first_search(self,root=None):
        queue = []
        order = []
        def bfs():
            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)

        if root:
            queue.append(root)
            order.append(root)
            bfs()

        for node in self.nodes():
            if not node in self.visited:
                queue.append(node)
                order.append(node)
                bfs()
        
        return order


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

order1 = g.breadth_first_search(1)
print('广度优先遍历：',order1)
order2 = g.depth_first_search(1)
print('深度优先遍历：',order2)
# print(g.node_neighbors)