圖的遍歷主要有深度優(yōu)先搜索 DFS(depth-first search) 和廣度優(yōu)先搜索BFS( breadth-first search) 兩種方式

g.png

深度優(yōu)先遍歷

深度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點(diǎn)v，并將其標(biāo)記為已訪問過；然后依次從v出發(fā)搜索v的每個(gè)鄰接點(diǎn)w。若w未曾訪問過，則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)均已被訪問為止。若此時(shí)圖中仍有未訪問的頂點(diǎn)，則另選一個(gè)尚未訪問的頂點(diǎn)為新的源點(diǎn)重復(fù)上述過程，直至圖中所有的頂點(diǎn)均已被訪問為止。

dfs.png

深度優(yōu)先遍歷結(jié)果是： A B E F C D G H I

深度優(yōu)先遍歷盡可能優(yōu)先往深層次進(jìn)行搜索

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點(diǎn)v，接著依次訪問v的所有鄰接點(diǎn)w1、w2......wt，然后依次訪問w1、w2......wt鄰接的所有未曾訪問過的頂點(diǎn)。以此類推，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)都已訪問到為止。此時(shí)從v開始的搜索過程結(jié)束。

bfs.png

廣度優(yōu)先遍歷結(jié)果是： A B C D E F G H I

廣度優(yōu)先遍歷按層次優(yōu)先搜索最近的結(jié)點(diǎn)，一層一層往外搜索。

圖的數(shù)據(jù)結(jié)構(gòu)主要有鄰接矩陣和鄰接表2種。在 python 中我們可以這樣表示上面的圖

#!/usr/bin/env python3
import collections
import queue

g = collections.OrderedDict()
g['A'] = ['B', 'C', 'D']
g['B'] = ['A', 'E']
g['C'] = ['A', 'F']
g['D'] = ['A', 'G', 'H']
g['E'] = ['B', 'F']
g['F'] = ['E', 'C']
g['G'] = ['D', 'H', 'I']
g['H'] = ['G', 'D']
g['I'] = ['G']

類似鄰接表，這里用了 OrderedDict ，因?yàn)楣１淼谋闅v輸出是不固定的

深度優(yōu)先遍歷

def DFSTraverse(g):
    visited = {}

    def DFS(v):
        print(v)
        visited[v] = True

        for adj in g[v]:
            if not visited.get(adj):
                DFS(adj)

    for v in g:
        if not visited.get(v):
            DFS(v)

DFSTraverse(g)

廣度優(yōu)先遍歷

def BFSTraverse(g):
    visited = {}
    q = queue.Queue()

    for v in g:
        if not visited.get(v):
            print(v)
            visited[v] = True  # 先訪問再入隊(duì)
            q.put(v)

        while not q.empty():
            e = q.get()

            for adj in g[e]:
                if not visited.get(adj):
                    print(adj)
                    visited[adj] = True
                    q.put(adj)

BFSTraverse(g)

廣度優(yōu)先遍歷借助了隊(duì)列來保證按層次搜索，上級(jí)層次的結(jié)點(diǎn)先入隊(duì)，結(jié)點(diǎn)出隊(duì)時(shí)它的相鄰子結(jié)點(diǎn)再依次入隊(duì)