image

深度优先 DFS

遍历方式：

0（从0开始，有两条路，先走1）->0，1（1有两条路）->0，1，2（1有两条路，先走2）->0,1（2没路了，退回1）->0，1，3（走1的另一条路3）->0，1，3，9（3只有一条路）->0，1，3（9没路了，退回3）->0，1（3没有没走过的路了，退回1）0，1（1没有没走过的路了，退回0）

->0，4（走0的另一条路）->以此类推......

从数字变化来看，这是一个栈（先进后出），所以深度优先遍历可以通过一个栈来实现。本文通过递归实现（递归本身也是栈）。

广度优先 BFS

遍历方式：

0,1,4（先走0的相邻的两条路）->0,1,4,2,3（走到1的时候把第二层的数据拿到）->0,1,4,2,3,8,5（走到4的时候把第二层的数据拿到）

从数字变化来看，这是一个队列（先进先出），所以借助队列来实现图的遍历。

代码实现

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

from collections import deque


class Graph:
    def __init__(self, graph=None):
        self.graph = graph

    def dfs(self, start, visted):
        if start in visted:
            return

        visted.append(start)

        for i in self.graph.get(start, []):
            self.dfs(i, visted)
        return visted

    def bfs(self, start, visted, queue):
        queue.appendleft(start)
        while queue:
            front = queue.pop()
            if front in visted:
                continue

            visted.append(front)

            for i in self.graph.get(front, []):
                queue.appendleft(i)
        return visted


def main():
    # 初始化图
    graph = {0: [1, 4],
             1: [0, 2, 3],
             2: [1],
             3: [1, 9],
             4: [0, 5, 8],
             5: [4, 6, 7],
             6: [5],
             7: [5],
             8: [4],
             9: [3]
             }
    graph_obj = Graph(graph)

    start = 0
    visted = []
    # 深度优先
    print sorted(graph_obj.dfs(start, visted))

    g_queue = deque()
    # 广度优先
    print sorted(graph_obj.bfs(start, visted, g_queue))

if __name__ == '__main__':
    main()