第八章 (new).ppt

第八章 图 第八章 图 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 §8.1 图的基本概念等 ADT Graph一组顶点集合{vi}和一组边{ej}集合以及如带权图时每边还构成权{wi}集加上下操作： 查找：LocateVex(G, u) GetVex(G, v)  FirstAdjVex(G, v)  NextAdjVex(G, v, w) 插入：InsertVex(G, v) InsertArc(G, v, w) 删除：DeleteVex(G, v) DeleteArc(G, v, w) 遍历：DFSTraverse(G, v, Visit()) BFSTraverse(G, v, Visit()) §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.2 图的存储结构 §8.3 图的遍历 和树的遍历类似，可以从图的某个顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这个过程称为图的遍历。 图的遍历比树的遍历复杂。 树的遍历始于根结点，图中没有根结点。 图中可能存在回路。 常用的图遍历方法 深度优先遍历 广度优先遍历 §8.3 图的遍历—深度优先遍历法 算法： 1) 访问图中某个指定顶点V0； 2) 从V0出发，访问与V0邻接的顶点V1后，再从V1出发，访问与V1邻接且未被访问过的顶点V2。重复上述过程，直到不存在未访问过的邻接点为止。 3) 回退到尚未访问过的顶点,从该顶点出发，重复1)、2)，直到全部被访问过的邻接点都被访问为止。 §8.3 图的遍历—深度优先遍历法 §8.3 图的遍历—深度优先遍历法 §8.3 图的遍历—深度优先遍历法 §8.3 图的遍历—深度优先遍历法 §8.3 图的遍历—深度优先遍历法 §8.3 图的遍历—深度优先遍历法 §8.3 图的遍历 先访问第1个顶点所有邻接点后，再访问下一个顶点所有未被访问的邻接点。 算法 1) 访问某个指定顶点V0； 2) 从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依此从W1,W2,…,Wk出发访问各自未被访问的邻接点。 3) 重复2)，直到全部顶点都被访问。 §8.3 图的遍历 §8.3 图的遍历 广度优先遍历G6所走过的序列： V1? V3 ? V2 ? V4 ? V5 ? V6 所走过的边： （V1，V3），（V1，V2），（V1，V4），（V3，V5），（V4，V6） 遍历生成树 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，若边集E(G’)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G’是原图G的生成树（Spanning tree）。 生成树有如下特点：任意两个顶点之间有且仅有一条路径；如果再增加一条边就会出现环路；如果去掉一条边此子图就会变成非连通图。 一个有n 个顶点的完全图，一共存在n(n-2)种不同的生成树。 §8.4 最小生成树 对于带权的连通图（连通网）G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（Minimum Spanning Tree）。 具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路） 。 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 §8.4 最小生成树 §8.5 最短路径 §8.5 最短路径 §8.5 最短路径