第16讲 图的遍历与最小生成树.ppt

第16讲图的遍历与 最小生成树
主讲人:陈红丽
开始
执行上课礼
1
图的遍历
图的遍历是从图中某一顶点出发,对图中所有顶点访问一次且仅访问一次。
图的遍历操作要解决的关键问题
因图中可能存在回路,某些顶点可能会被重复访问,如何避免遍历因回路而陷入死循环。
解决方案:附设访问标志数组visited[n]
图中一个顶点可和其它多个顶点相连,当这样的顶点访问过后,如何选取下一个要访问的顶点?
解决方案:深度优先遍历和广度优先遍历。
执行上课礼,不迟到、不早退、不旷课
2
课上不吃早点、不玩手机、不睡觉
深度优先遍历过程是递归的,在遍历过程中,若某个顶点的所有邻接顶点均被访问过,则需要回溯。
V1
V2
V4
V5
V8
V3
V6
V7
V1
V5
V2
V4
V2
V8
V1
V7
V3
V3
V6
V3
V2
V4
V1
V6
V5
V8
V7
与二叉树的先序遍历相类似
深度优先遍历
执行上课礼,不迟到、不早退、不旷课
3
课上不吃早点、不玩手机、不睡觉
深度优先遍历
从图中某顶点v出发
1)访问顶点 v,置访问标记 visited[v] = 1;
2)依次从 v 的未被访问的邻接点出发,继续对图进行深度优先遍历,直到和v有路径相通的顶点都被访问过;
3)如果图中还有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问过为止。
执行上课礼,不迟到、不早退、不旷课
4
课上不吃早点、不玩手机、不睡觉
根据图G的邻接矩阵,从顶点V4出发,写出深度优先遍历序列。
0 1 1 0 0 0 0 0
0 0 1 1 0 0 0
1 0 0 0 0 1 1 0
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 0 0 0 1 0
0 0 1 0 0 1 0 0
0 0 0 1 1 0 0 0
V1 V2 V3 V4 V5 V6 V7 V8
V1
V2
V3
V4
V5
V6
V7
V8
V6,
深度优先遍历序列:
V1,V2,V4,V8,V5,V3,V6,V7
或V1,V2,V5,V8,V4,V3,V7,V6
或V2,V5,V8, V4, V1,V3,V7,V6
…….
V1
V2
V4
V5
V3
V7
V6
V8
图G的逻辑结构
图G的邻接矩阵??
V4,
V2,
V1,
V3,
V7,
V5,
V8
执行上课礼,不迟到、不早退、不旷课
5
课上不吃早点、不玩手机、不睡觉
已知某图G的邻接表如下所示,分别写出从顶点0和顶点3出发的DFS序列。
以顶点0为起点的DFS序列:0,1,4,3,2
以顶点3为起点的DFS序列:3,1,4,2,0
执行上课礼,不迟到、不早退、不旷课
6
课上不吃早点、不玩手机、不睡觉
从图中某个顶点vi出发:
1)访问顶点vi,并置访问标志
2)访问vi的所有未被访问的邻接点w1,w2,…,wk;
3)依次从这些邻接点(在步骤2)中访问的顶点)出发,访问它们的所有未被访问的邻接点;依此类推,直到图中所有访问过的顶点的邻接点都被访问
4)如若此时图中尚有顶点未被访问,则需另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。
广度优先遍历
与二叉树的层次遍历相似
V3
V2
V4
V1
V6
V5
V8
V7
执行上课礼,不迟到、不早退、不旷课
7
课上不吃早点、不玩手机、不睡觉
0 1 1 0 0 0 0 0
0 0 1 1 0 0 0
1 0 0 0 0 1 1 0
0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1
0 0 1 0 0 0 1 0
0 0 1 0 0 1 0 0
0 0 0 1 1 0 0 0
V1 V2 V3 V4 V5 V6 V7 V8
V1
V2
V3
V4
V5
V6
V7
V8
V1
V2
V4
V5
V3
V7
V6
V8
根据图G的邻接矩阵,从顶点V4出发,写出广度优先遍历序列。
V4,V2,V8,V1, V5,V3,V6,V7
执行上课礼,不迟到、不早退、不旷课
8
课上不吃早点、不玩手机、不睡觉
已知邻接表,求以顶点0和顶点3为起点的广度优先遍历序列。
以顶点0为起点的BFS序列:0,1,3,4,2
以顶点3为起点的BFS序列:3,1,0,4,2
执行上课礼,不迟到、不早退、不旷课
9
课上不吃早点、不玩手机、不睡觉
遍历的应用
利用图的遍历运算求解图的连通性问题
无向图是否连通、有几个连通分量,求解无向图的所有连通分量