第八章 图的数据结构与算法
图的遍历方法有两种:深度优先遍历(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]