图的遍历方法有两种:深度优先遍历(DFS),广度优先遍历(BFS)

DFS

类似于前序遍历,
从图的某个顶点开始遍历,被访问过的顶点就做已访问的标记,
接着遍历顶点所有相邻且未访问的顶点中的任意一个顶点,
并且做上已访问的记号,
再以该点为新起点继续进行深度优先的搜索.

结合了递归和堆栈
必须加入一个变量,判断该点是否已经遍历完毕,否则会无限循环

step1 以顶点1为起点,将相邻的顶点2和顶点5压入堆栈

|5|2| | | |

step2 弹出顶点2, 将与顶点2相邻且未访问的顶点3和顶点4压入堆栈

|5|4|3| | |

step3 弹出顶点3, 将与顶点3相邻且未访问的顶点4和顶点5压入堆栈

|5|4|5|4| |

step4 弹出顶点4, 将与顶点4相邻且未访问的顶点5压入堆栈

|5|4|5|5| |

step5 弹出顶点5, 将与顶点5相邻且未访问的顶点5压入堆栈,发现与5相邻的顶点全部被访问过了,所以无需再压入堆栈

|5|4|5| | |

step6 将堆栈内的值弹出并判断是否已经遍历过了,直到堆栈内无节点可遍历为止

| | | | | |

故DFS的遍历顺序为 1 2 3 4 5

范例程序
class list_node:
    def __init__(self):
        self.val = 0
        self.next = None


head = [list_node()] * 9 # 声明一个节点类型的链表数组
run = [0] * 9
def dfs(current):
    run[current] = 1
    print("[%d]" % current, end="")
    ptr = head[current].next
    while ptr != None:
        if run [ptr.val] == 0: # 如果顶点尚未遍历
            dfs(ptr.val) # 就进行dfs的递归调用
        ptr = ptr.next
# 声明图的边线数组
data = [[1, 2], [2, 1],[1, 3], [3, 1], [2, 4],
[4, 2], [2, 5], [5, 2], [3, 6], [6, 3],
[3, 7], [7, 3],[4, 8], [8, 4], [5, 8],
[8, 5], [6, 8], [8, 6], [8, 6], [7, 8]]
for i in range(1, 9):
    run[i] = 0 # 把所有顶点设置为尚未遍历过
    head[i] = list_node()
    head[i].val = i # 给各个链表头设置初值
    head[i].next = None
    ptr = head[i] # 设置指针指向链表头
    for j in range(20): # 二十条边线
       if data[j][0] == i: # 如果起点和链表头相等,就把顶点加入链表
            newnode = list_node()
            newnode.val = data[j][1]
            newnode.next = None
           while True:
                ptr.next = newnode # 加入新节点
                ptr = ptr.next
                if ptr.next == None:
                    break


print("图的邻接表内容:")
for i in range(1, 9):
    ptr = head[i]
    print("顶点 %d" % i, end="")
    ptr = ptr.next
    while ptr != None:
        print("[%d]" % ptr.val, end="")
        ptr = ptr.next
    print()
print("深度优先遍历的顶点:")
dfs(1)
print()
#运行结果
# 图的邻接表内容:
# 顶点 1[2][3]
# 顶点 2[1][4][5]
# 顶点 3[1][6][7]
# 顶点 4[2][8]
# 顶点 5[2][8]
# 顶点 6[3][8]
# 顶点 7[3][8]
# 顶点 8[4][5][6][6]
# 深度优先遍历的顶点:
# [1][2][4][8][5][6][3][7]