数据结构导论第五章课件

第五章图5.1图的基本概念5.2图的存储结构5.3图的遍历5.4最小生成树5.5拓扑排序15.1图的基本概念图G由两个集合构成，记作G=<V,E>其中:V（vertex）是顶点的非空有限集合E（edge）是边的有限集合v1v2v5v4v32如果每条边都没有方向，则为无向图(vi,vj)和(vj,vi)表示同一条边如果每条边都有方向，则称有向图有向图中用箭头表示弧的方向，箭头从弧尾指向弧头v1v2v5v4v3v2v1v4v33G1={V,E}

V={v1,v2,v3,v4,v5}

E={(v1,v2),(v2,v3),(v2,v4),(v3,v5),(v2,v5)}G2={V,E}V={v1,v2,v3,v4,v5}，E={<v1,v2>,<v1,v3>,<v2,v3>,<v2,v4>,<v4,v1>}4完全图：无向完全图：任意两顶点间都有边的图。在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。有向完全图:任意两顶点之间都有方向互为相反的两条弧相连接的有向图。在一个含有n个顶点的有向完全图中，有n(n-1)条弧。5邻接点、相关边无向图中存在边(vi,vj)，则称vi和vj互为邻接点同时称边(vi,vj)依附于顶点vi,vj

(vi,vj)是与vi和vj相关联的边在有向图中，若存在弧<vi,vj>，也称相邻接，但要区分弧的头和尾6顶点的度在无向图中,顶点V的度=与V相关联的边的数目，记作D(V)在有向图中,顶点V的度=V的出度OD(V)+V的入度ID(V)OD(V)=以V为起点有向边数ID(V)=以V为终点有向边数7路径G中的顶点序列v1,v2,…,vk,若各边(vi,vi+1)E,则称该序列是从顶点v1到顶点vk的路径；8回路:若路径的起点和终点相同，则称回路。简单路径在一条路径中,若除起点和终点外,所有顶点各不相同,则该路径为简单路径；简单回路：由简单路径组成的回路称为简单回路；9子图设有两个图G=（V，E）G1=（V1，E1），若V1V，E1E，E1关联的顶点都在V1中，则称G1是G的子图；G1=(V1，E1);V1={v1,v2,v3,v4,v5}E1={(v1,v2),(v2,v3),(v3,v5),(v2,v4),(v2,v5)}G2=(V2，E2)V2={v2,v3,v5}E2={(v2,v3),(v2,v5),(v3,v5)}10

连通图在无向图G=<V,E>中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图11连通分量无向图G的极大连通子图称为G的连通分量12生成树包含无向图G所有顶点的的极小连通子图若T是G的生成树当且仅当T满足如下条件T是G的连通子图T包含G的所有顶点T中无回路13若连通图G的顶点个数为n，则G的生成树边数为n-1。如果G的一个子图G’的边数大于n-1，则G’中一定有环。相反，如果G’的边数小于n-1，则G’一定不连通。结论14边的权：在图的边或弧上表示数字，表示与该边相关的数据信息，这个数据信息就称该边的权（weight）。网（network）：边（或弧）上带权的图称为网。

V0

V4

V3

V1

V282465315习题1.（1）设有无向图G=(V,E)和G’=(V’,E’)，若G’是G的生成树，则下面不正确的说法是（）

G’为G的子图

G’为G的连通分量C.G’为G的极小连通子图且V’=VD.G’是G的无环子图答案：B165.2图的存储表示邻接矩阵表示法邻接表表示法171.邻接矩阵表示图G的邻接矩阵是满足如下条件：若G是网若G是图18V1V2V3V4V1V2V3V43596191，无向图的邻接矩阵是对称的2，存储无向图的邻接矩阵需要n(n+1)/2个单元，与边数无关，只与顶点数有关。3，无向图vi的度是第i行(列)中1的个数，边数是矩阵中1个数的一半4，有向图第i行1的个数是vi的出度第i列1的个数是vi的入度20习题1）求顶点v的度：2）判断两顶点是否邻接：3）检测图中的总边数：21邻接矩阵的定义结构typedefstructgraph{vertexvexs[vnum]；intarcs[vnum][vnum]；intvexnum，arcnum；}//顶点信息//边信息//顶点数，边数222.邻接表1.无向图的邻接表一种顺序和链式相结合的存储结构顶点数组与顶点邻接的顶点链表表头结点表结点232.有向图的邻接表（出边表）和逆邻接表（入边表）逆邻接表邻接表243.邻接表存储下图的有关操作1）求顶点v的度：2）判断两顶点是否邻接：3）检测图中的总边数：逆邻接表邻接表邻接表25邻接表的定义结构typedefstructarcnode{intadjvex；structarcnode*nextarc；}arcnode；typedefstructvexnode{intvertex；arcnode*firstarc；}vexnode；typedefstructgraph{vexnodeadjlist[vnum]；intvexnum，arcnum；}graph；26习题2.（2）已知无向图G的结点数为n，边数为e，其邻接表表示中的表结点数与表头结点数之和为——

答案：n+2e表结点数表头结点数271.邻接表表示法是借助________来反映顶点间的邻接关系，其中的结点称为表结点。习题答案：单链表283.对于无向图的邻接矩阵，顶点vi的度是_____。对于有向图的邻接矩阵，顶点vi的出度OD（vi）为______，顶点vi的入度ID(vi)是_______。习题答案：矩阵第i行（列）非零元素的个数；矩阵第i行非零元素的个数；矩阵第i列非零元素的个数；295.3图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。有两种遍历方法：深度优先遍历（DFS：DepthFirstSearch）广度优先遍历（BFS：BreadthFirstSearch）30一、深度优先遍历（DFS）从图中某顶点v出发：1）访问顶点v；

2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；由于没有规定访问邻接点的顺序，DFS序列不唯一abchdekfgachkfedbg31voiddfs(intv){访问v;visit[v]=1;找到g中v的第一个邻接点w;while(w存在){if(visit[w]==0) dfs(w);令w=g图中v的下一个邻接点}}深度优先遍历算法32图中某未访问过的顶点vi出发：1）访问顶点vi；2）访问vi的所有未被访问的邻接点w1,w2,…wk；3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；二、广度优先遍历（BFS）Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w433问题：如何保证邻接点的出发顺序？解决：利用队列。1）从图中某未访问过的顶点vi出发：2）访问顶点vi；3）访问vi的所有未被访问的邻接点w1,w2,…wk；4）将w1,w2,…wk入队；5）取队头顶点，从该顶点出发，访问它的所有未被访问的邻接点；即重复2－5，直到图中所有访问过的顶点的邻接点都被访问34voidbfs(intv){初始化队列Q；访问v；visited[v]=1；v入队；当队非空时，{出队v找到v的第一个邻接点w当w存在{若w未被访问，访问w，visited[w]=1；w入队；}w=g中v的下一个邻接点；}}351．一有向图G的邻接表存储结构如图所示。现按深度优先遍历算法，从顶点V1出发，所得到的顶点序列可能是（）①V1,V3,V2,V4,V5②V1,V3,V4,V2,V5③V1,V2,V3,V4,V5④V1,V3,V4,V5,V2习题答案：③④36图的连通分量abcdegfaedcbgfabcdegfaedcbgf37连通分量深度优先生成树广度优先生成树aaeeddccbbggffabcdegfaedcbgf38连通分量深度优先生成树广度优先生成树abcdegfabcdegfaedcbgf39图的连通分量对图进行dfs和bfs，每次调用得到一个连通分量思考题目：如何运用dfs和bfs判断图是否为连通图？abcdegfaedcbgf401.对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。判断题×41生成树包含无向图G所有顶点的极小连通子图称为G的生成树若T是G的生成树当且仅当T满足如下条件T是G的连通子图T包含G的所有顶点T中无回路abcdegfaedcbgfabcdegfaedcbgf42若连通图G顶点个数为n，则G的生成树的边数为n-1。如果G的一个子图G’的边数大于n-1，则G’中一定有环。相反，如果G’的边数小于n-1，则G’一定不连通。结论abcdegfaedcbgfabcdegfaedcbgf435.4最小生成树假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题：44假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？abcdegf195141827168213ae12dcbgf7148531621假设用顶点表示城市，边表示城市间的通信线路，边上的权表示费用45abcdegf195141827168213ae12dcbgf7148531621abcdegf51827821ae12dcbgf852146abcdegf195141827168213ae12dcbgf7148531621abcdegf514168213aedcbg小生成树

若有一个连通的无向图G，有n个顶点，并且它的边是有权值的。在G上构造生成树G’,最小生成树n-1条边的权值之和最小的G’。算法二：（克鲁斯卡尔算法）算法一：（普里姆算法）48用普里姆算法构造最小生成树取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。49abcdegf例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=6750v2v1v3v7v6v5v464547351具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：52abcdegf195141827168213ae12dcbgf7148531621712181953545.5拓扑排序55C1高等数学C2程序设计基础C3离散数学C1,C2

C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8

课程代号课程名称先修课程5657拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下