20.附录：图结构、深度优先搜索、广度优先搜索 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

附录：图结构、深度优先搜索和广度优先搜索 1.图结构时一种比线性结构和树形结构更为复杂的线性结构。线性结构中每个节点最多只有一个前驱节点和一个后继节点；树形结构中每个节点最多只有一个前驱节点，可以有多个后继节点；而图结构每个节点的前驱节点和后驱节点的个数都不是唯一的。 2.图结构根据节点之间的关系可以分为有向图、无向图、连通图和非连通图。 3.图结构处理——深度优先搜索和广度优先搜索 例题：公司安排小张到H市出差，从小张所在的A市到H市没有直达公交，需要中转若干个城市，但中转方式不唯一。如图所示，从A市到H市有多种方案，请编写代码找出中转次数最少的方案。 用二维数组来存储城市之间的中转方案图，城市A-H分别编号为0-7。用数值1来表示表格中左侧城市可到达上方城市。 城市 A(0) B(1) C(2) D(3) E(4) F(5) G(6) H(7) A(0) 0 1 0 1 0 0 0 0 B(1) 0 0 1 0 0 0 0 0 C(2) 0 0 0 0 0 1 0 0 D(3) 0 0 0 0 1 0 1 0 E(4) 0 0 1 0 0 1 0 0 F(5) 0 0 0 0 0 0 0 1 G(6) 0 0 0 0 0 0 0 1 H(7) 0 0 0 0 0 0 0 0 设计算法解决该问题时，常用方式有两种，第一种是广度优先搜索，另一种是深度优先搜索。 ①广度优先搜索（BFS）—找到最短路径 首先将起点入队，然后取出队首元素X，将X市可达的所有城市依次入队，不断重复次操作，直到遇到目的地或队列为空为止。代码实现如下 #获取中转方案二维列表a，代码略 maxn = 8 f=[False]*maxn que=[[]]*20;head=tail=0 #创建队列 que[tail]=[0,-1];tail+=1;f[0]=True #起点入队 end = 7 #H市编号为7 flag = False while head<tail: city = que[head][0] #队首出队 f[city]=False for j in range(maxn): if j != end and a[city][j]==1 and not f[j]: que[tail]=[j,head];tail+=1 #将city可达城市入队 f[j] = True #查重标记 elif j == end and a[city][j] == 1 and not f[j]: #用链表遍历反向输入经过的城市，代码略 flag = True if flag:break head+=1 else: print("无法到达目的地") 广度优先搜索是一种多路径并行的思想，最先到达终点的一定是最短路径。但由于多条路径经过的节点都存放在同一个队列中，需要输出最短路径经过的节点时，需要在节点入队时就存储前向指针，构建节点间的逻辑关系。 ②深度优先搜索(DFS)——找出全部路径 首先将起点入栈，然后取出栈顶元素X市，将X市可达的城市中的一个入栈，不断重复操作，直到遇到目的城市或栈为空为止。代码实现如下 maxn=8 end = 7 #H市编号为7 stack = [] flag = [False]*maxn stack.append(0);flag[0]=True j = -1;f = False while len(stack)>0: city = stack[-1] #取出栈顶城市 j+=1 while j<maxn: if a[city][j] == 1 and not flag[j]: break j=j+1 if j==maxn: #该城市没有相邻可通的城市 j = stack.pop();flag[j] = False else: if j==end: #到了目的城市，并为找另一条路做准备 #输出当前路径经过的全部站点，代码略 j = stack