数据结构教学课件：第七讲3图

1、7.3 图的遍历深度优先遍历(DFS)方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍历：V1

2、V2 V4 V8 V3 V6 V7 V5广度优先遍历(BFS)方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V

3、7 V8V1V2V4V5V3V7V6V8例广度遍历：V1 V2 V3 V4 V6 V7 V8 V5无论是深度优先遍历，还是广度优先遍历，走遍n个景点，实际上走过几条路？如果遍历的图是连通的，当然是走过n-1条路。N个结点，n-1条边，让我们想到了什么？对连通图做一次DFS遍历，把走过的的点和走过的边留下，得到的称为生成树。脑子有点乱，我整理一下哦：对一个连通的图，进行深度，或者广度优先的遍历，得到的结果其实是一棵树。这棵树可以保证做到：n个点之间用最少的边，保持图的连通特性。假设，每个边上还带着权值。那这样可以吗？构造最小生成树方法方法一：普里姆(Prim)算法算法思想：设N=(V,E)是连通

4、网， 初始令U=u0,(u0V), TE= 在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0) 将边(u0,v0)并入集合TE，同时v0并入U 重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树u0V1,v2,v3UV普里姆(Prim)算法实现所用数据结构为邻接矩阵“从V1出发，找周边最小的边”-在哪里找？我看出来了：v1-v3 最小。按照规定，把v3发展进U集合。现在U集合周边谁最小？第3行代表V3周边所有边的边长。所以，U周边当前最小边是在第1行和第3行中间但是要想个办法不能再选“1”。据观察，周边最小的边是3-6.现在U1,3,6,有n个点呢，总不能就这么一直“观察”算法描述：1、要有一个一维数组，记录谁已经被选中过了，不能重复选。2、最开始把V1那一行单独拿出来，放在一个固定的一维数组lowcost里。3、以后找谁最小就在这个数组里找。4、找到谁最小，就在标志数组里做标志5，如果当前是j列最小，那么就要用第j行和Lowcost对应位置的数比较，用更小