第八章 图(重点).doc
7页
第八章 图（重点章节）考点一：相关概念 有向图、无向图： 完全无向图：对于无向图，若图中顶点数为n ，用e表示边的数目，则e Î[0，n(n-1)/2] 具有n(n-1)/2条边的无向图称为完全无向图完全有向图：对于有向图，若图中顶点数为n ，用e表示弧的数目，则eÎ[0，n(n-1)] 具有n(n-1)条边的有向图称为完全有向图 注：G为 图 集合，V为 边 集合，E为 边关系 集合权：权可以表示从一个顶点到另一个顶点的距离或耗费邻接顶点： 对于无向图G=(V，E)，若边(v,w)包含于集合E，则称顶点v和w 互为邻接顶点，即v和w相邻接 对于有向图G=(V ，E)，若有向弧(v,w)包含于集合E，则称顶点v “邻接到”顶点w，顶点w “邻接自”顶点v ，弧
对有向图G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj路径长度：路径上边或有向边(弧)的数目称为该路径的长度回路：第一个顶点和最后一个顶点相同的路径称为回路(环)连通图、图的连通分量：对无向图G=(V，E)，若"vi ，vj ÎV，vi和vj都是连通的，则称图G是连通图，否则称为非连通图若G是非连通图，则极大的连通子图称为G的连通分量 强连通图、图的强连通分量：对有向图G=(V，E)，若"vi ，vj ÎV，都有以vi为起点， vj 为终点以及以vj为起点，vi为终点的有向路径，称图G是强连通图，否则称为非强连通图若G是非强连通图，则极大的强连通子图称为G的强连通分量生成树：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树，如图7-2所示 关于无向图的生成树的几个结论：◆ 一棵有n个顶点的生成树有且仅有n-1条边；◆ 如果一个图有n个顶点和小于n-1条边，则是非连通图；◆ 如果多于n-1条边，则一定有环；◆ 有n-1条边的图不一定是生成树考点二：对于有向图的入度、出度度： 对于无向图G=(V，E)， 存在"vi包含于集合 V ，图G中依附于vi的边的数目称为顶点vi的 度 。
对有向图G=(V，E)，若 vi 包含于集合 V ，图G中以vi作为起点的有向边(弧)的数目称为顶点vi的 出度 以vi作为终点的有向边(弧)的数目称为顶点vi的 入度 顶点vi的出度与入度之和称为vi的 度 考点三：图的邻接矩阵表示基本思想：对于有n个顶点的图，用一维数组vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息该二维数组称为邻接矩阵在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息考点四：有向图对称、无向图对称(1) 无向图的无权图的邻接矩阵（即无向图对称） 无向无权图G=(V，E)有n(n≧1)个顶点，其邻接矩阵是n阶对称方阵，如图7-5所示其元素的定义如下：无向图邻接矩阵的特性 ◆ 邻接矩阵是对称方阵； ◆ 对于顶点vi，其度数是第i行的非0元素的个数； ◆ 无向图的边数是上(或下)三角形矩阵中非0元素个数2）有向图的无权图的邻接矩阵（即有向图的对称） 若有向无权图G=(V，E)有n(n≧1)个顶点，则其邻接矩阵是n阶对称方阵，如图7-7所示。
元素定义如下：有向图邻接矩阵的特性◆ 对于顶点vi，第i行的非0元素的个数是其出度OD(vi)；第i列的非0元素的个数是其入度ID(vi) ◆ 邻接矩阵中非0元素的个数就是图的弧的数目考点五：图的两种遍历方式（深度、广度）1.深度优先搜索(Depth First Search--DFS)遍历类似树的先序遍历，是树的先序遍历的推广算法思想设初始状态时图中的所有顶点未被访问，则：⑴ ：从图中某个顶点vi出发，访问vi；然后找到vi的一个邻接顶点vi1 ；⑵：从vi1出发，深度优先搜索访问和vi1相邻接且未被访问的所有顶点；⑶：转⑴ ，直到和vi相邻接的所有顶点都被访问为止 ⑷ ：继续选取图中未被访问顶点vj作为起始顶点，转(1)，直到图中所有顶点都被访问为止 图7-17是无向图的深度优先搜索遍历示例(红色箭头)某种DFS次序是：v1→ v3 → v2 → v4 → v52.广度优先搜索(Breadth First Search--BFS)遍历类似树的按层次遍历的过程算法思想 设初始状态时图中的所有顶点未被访问，则：⑴ ：从图中某个顶点vi出发，访问vi；⑵：访问vi的所有相邻接且未被访问的所有顶点vi1，vi2，…，vim；⑶：以vi1，vi2， …，vim的次序，以vij(1≦j≦m)依此作为vi ，转⑴； ⑷ ：继续选取图中未被访问顶点vk作为起始顶点，转⑴，直到图中所有顶点都被访问为止。
图7-18是有向图的广度优先搜索遍历示例(红色箭头)上述图的BFS次序是：v1→ v2 → v4 → v3 → v5注意：用广度优先搜索算法遍历图与深度优先搜索算法遍历图的唯一区别是：邻接点搜索次序不同例题：已知二维数组表示的图的邻接矩阵如下图所示试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树考点六：最小生成树（两种方法）P371 图8.17 图8.18最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树1.普里姆(Prim)算法算法思想⑴ 若从顶点v0出发构造，U={v0}，TE={}；⑵ 先找权值最小的边(u，v)，其中u∈U且v∈V-U，并且子图不构成环，则U= U∪{v}，TE=TE∪{(u，v)} ；⑶ 重复⑵ ，直到U=V为止则TE中必有n-1条边， T=(U，TE)就是最小生成树 如图7-21所提示2. 克鲁斯卡尔(Kruskal)算法算法思想 设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是其最小生成树初值：U=V，TE={} 对G中的边按权值大小从小到大依次选取。
⑴ 选取权值最小的边(vi，vj)，若边(vi，vj)加入到TE后形成回路，则舍弃该边(边(vi，vj) ；否则，将该边并入到TE中，即TE=TE∪{(vi，vj)} ⑵ 重复⑴ ，直到TE中包含有n-1条边为止 如图7-22所提示考点七：最短路径（图8.20Dijkstra算法掌握求解过程）例题：试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态解：最短路径为：（a,c,f,e,d,g,b）考点八：AVO网络（由图—>AVO）拓扑排序 （图8.27）拓扑排序(Topological Sort) ：由某个集合上的一个偏序得到该集合上的一个全序的操作算法思想① 在AOV网中选择一个没有前驱的顶点且输出； ② 在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边) ；③ 重复①、②，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)例题：（ A ）1. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（ D ）2. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（ A ）3. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）4. 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。
5. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 6. 图的深度优先遍历序列 不是 惟一的7. 若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔(Kruskal) 算法来求解8. 若要求一个稠密图G的最小生成树，最好用 普里姆(Prim) 算法来求解9. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。
