《数据结构教学课件：Chapter Seven Graph》由会员分享，可在线阅读，更多相关《数据结构教学课件：Chapter Seven Graph（74页珍藏版）》请在金锄头文库上搜索。
1、数据结构Chapter Seven Graph引n图的基本概念n图的存储表示n图的遍历与连通性 n最小生成树n最短路径 n活动网络 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中 ： V = x | x 某个数据对象 是顶点的有穷非空集合； E = (x, y) | x, y V 或 E = | x, y V & Path (x, y) 是顶点之间关系的有穷集合，也叫做边(edge)集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的。1、图的概念：定义1、图的概念：常用术语n有向图与无向图 ： 在有向图中，顶点
2、对是有序的。在无向图中，顶点对(x, y)是无序的。n完全图： 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。n邻接顶点： 如果 (u, v) 是 E(G) 中的一条边，则称u 与 v 互为邻接顶点。1、图的概念：常用术语n权： 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。n子图： 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 E E, 则称 图G 是 图G 的子图。n顶点的度： 一个顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中, 顶点的度等于该顶点的
3、入度与出度之和。1、图的概念：常用术语n顶点 v 的入度：是以 v 为终点的有向边的条数, 记作 ID(v)；n 顶点 v 的出度：是以 v 为始点的有向边的条数, 记作 OD(v)。n路径： 在图 G(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, , vpm，到达顶点vj。则称顶点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应是属于E的边。n路径长度 ：n非带权图的路径长度是指此路径上边的条数。n带权图的路径长度是指路径上各边的权之和。
4、1、图的概念：常用术语n简单路径：若路径上各顶点 v1,v2,.,vm 均不互相重复, 则称这样的路径为简单路径。n回路： 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环。n连通图与连通分量：在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量。1、图的概念：常用术语n强连通图与强连通分量：在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。n生成树： 一个
5、连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。但有向图则可能得到它的由若干有向树组成的生成森林。n本章不予讨论的图例213213有向完全图无向完全图356例245136图与子图1、图的概念：示例例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：0例157324G26顶点5的度：3顶点2的度：41、图的概念：示例例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，
6、7，6，5，2，1简单回路：1，2，3，11、图的概念：示例连通图例245136强连通图356非连通图连通分量例2451361、图的概念：示例2、图的基本操作nCreatGraph(G)输入图G的顶点和边，建立图G的存储。nDestroyGraph(G)释放图G占用的存储空间。nGetVex(G，v)在图G中找到顶点v，并返回顶点v的相关信息。nPutVex(G，v，value)在图G中找到顶点v，并将value值赋给顶点v。nInsertVex(G，v)在图G中增添新顶点v。nDeleteVex(G，v)在图G中，删除顶点v以及所有和顶点v相关联的边或弧。nInsertArc(G，v，w)在
7、图G中增添一条从顶点v到顶点w的边或弧。2、图的基本操作nDeleteArc(G，v，w)在图G中删除一条从顶点v到顶点w的边或弧。nDFSTraverse(G，v)在图G中，从顶点v出发深度优先遍历图G。nBFSTtaverse(G，v)在图G中，从顶点v出发广度优先遍历图G。nLocateVex(G，u)在图G中找到顶点u，返回该顶点在图中位置。nFirstAdjVex(G，v)在图G中，返回v的第一个邻接点。若顶点在G中没有邻接顶点，则返回“空”。nNextAdjVex(G，v，w)在图G中，返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。2、图的基本操作n
8、 说明：n一个图中，顶点是无序的，但当采用某一种确定的存储方式存储后，存储结构中顶点的存储次序构成了顶点之间的相对次序，这里用顶点在图中的位置表示该顶点的存储顺序；同样的道理，对一个顶点的所有邻接点，采用该顶点的第i个邻接点表示与该顶点相邻接的某个顶点的存储顺序。总之，存储方式导致顺序，导致定位。3、图的存储结构n图的存储结构有如下常用4种：(1) 邻接矩阵(2) 邻接表(3) 十字链表(4) 邻接多重表3、图的存储结构n图的存储结构:邻接矩阵思想：(1) 用一维数组存储图中顶点 (2) 用矩阵表示图中各顶点之间的邻接关系 ，所以该矩阵称为邻接矩阵。1表示有连接边，0表示无连接边。(3) 网络
9、图中，邻接矩阵中有边的数值为权值，无边的填3、图的存储结构n图的存储结构:邻接矩阵例：3、图的存储结构n图的存储结构:邻接矩阵例：有向图3、图的存储结构n图的存储结构:邻接矩阵分析：n无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。n在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。n在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。3、图的存储结构n图的存储结构:邻接矩阵缺点：n确定图中包含边的数目困难。3、图的存储结构n图的存储结构:邻接矩阵数据结构： #define MaxVertexNum 100 /
10、*最大顶点数设为100*/ typedef char VertexType; /*顶点类型设为字符型*/ typedef int EdgeType; /*边的权值设为整型*/ typedef struct VertexType vexsMaxVertexNum; /*顶点表*/ /*邻接矩阵，即边表*/ EdeType edgesMaxVertexNumMaxVertexNum; int n,e; /*顶点数和边数*/ Mgragh; /*Maragh是以邻接矩阵存储的图类型*/3、图的存储结构n图的存储结构:邻接表思想：(1) 用一维数组存储图中顶点 ，数据元素有指针域(2) 对应一条边，建
11、立一个节点，称为边节点；边节点形成链表3、图的存储结构n图的存储结构:邻接表例：无向图3、图的存储结构n图的存储结构:邻接表例：有向图n在有向图的邻接表中，第 i 个边链表链接的边都是顶点 i 发出的边。也叫做出边表。n在有向图的逆邻接表中，第 i 个边链表链接的边都是进入顶点 i 的边。也叫做入边表。3、图的存储结构n图的存储结构:邻接表例：有向网图3、图的存储结构n图的存储结构:邻接表节点结构3、图的存储结构n图的存储结构:邻接表数据结构：边结构 define MaxVerNum 100 /*最大顶点数为100*/ typedef struct node /*边表结点*/ int adjv
12、ex; /*邻接点域*/ struct node * next; /*指向下一个邻接点的指针域*/ /*若要表示网图，则还需增一个数据域info*/ EdgeNode; 3、图的存储结构n图的存储结构:邻接表数据结构：节点结构typedef struct vnode /*顶点表结点*/ VertexType vertex; /*顶点域*/ EdgeNode * firstedge; /*边表头指针*/ VertexNode; /*AdjList是邻接表类型*/typedef VertexNode AdjListMaxVertexNum; typedef struct AdjList adjli
13、st; /*邻接表*/ int n,e; /*顶点数和边数*/ ALGraph; /*ALGraph是以邻接表存储的图类型*/3、图的存储结构n图的存储结构:十字链表思想：(1) 用一维数组存储图中顶点 ，数据元素有两个指针域，一个用于指示出度，另一个用于指示一个入度(2) 边的边节点，包含该边的两个顶点；同时包含两指针区域，分别指向同一个出点和同一个入点(3) 是邻接多重表的有向图表示3、图的存储结构n图的存储结构:十字链表节点结构：在弧结点中有五个域：其中尾域(tailvex)和头(headvex)分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指向弧头相同的下一条弧，链域tlin
14、k指向弧尾相同的下一条弧，info域指向该弧的相关信息。3、图的存储结构n图的存储结构:十字链表例：有向图弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。它们的头结点即为顶点结点，它由三个域组成：其中vertex域存储和顶点相关的信息，如顶点的名称等；firstin和firstout为两个链域，分别指向以该顶点为弧头或弧尾的第一个弧结点 3、图的存储结构n图的存储结构:邻接多重表思想：(1) 用一维数组存储图中顶点 ，数据元素有一个指针域。(2) 边的边节点，包含该边的两个顶点；同时包含两指针区域，分别指向同一个出点和同一个入点(3) 主要用于无向图。3、图的存储结构n图的存储结构:邻接
15、多重表节点结构：3、图的存储结构n图的存储结构:邻接多重表例：无向图3、图的遍历n 图遍历的分析n定义：图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。n如何访问所有的连通分量？n如何选择一个顶点的多个邻接点？n图的遍历算法，有深度遍历(DFS)和广度遍历(BFS)两种。n如何走出回路？3、图的遍历n遍历算法思路：设置访问标记数组，visitedn；利用堆栈实现DFS，利用队列实现BFS。DFS遍历序列：v1v2 v4 v8 v5 v3 v6 v7BFS遍历序列：v1v2 v3 v4 v5 v6 v7 v83、图的遍历nDFS遍历算法 （dfs.cpp） /*从第v个顶
16、点出发递归地深度优先遍历图G*/void DFS(Graph G,int v )/*访问第v个顶点*/visitedv=TRUE;VisitFunc(v); for(w=FisrAdjVex(G,v);w; w=NextAdjVex(G,v,w) /*对v的尚未访问的邻接顶点w递归调用DFS*/ if (!visitedw) DFS(G,w); 3、图的遍历nDFS遍历算法示例abchdekfg812345670F F F F F F F F F0 1 2 3 4 5 6 7 8T T T T T T T T Tach d kfe bgachkfedbg访问标志访问标志: :访问次序访问次序:
17、 :例如例如:achdkfe3、图的遍历nBFS遍历算法 （bfs.cpp）/*按广度优先非递归遍历图G*/void BFSTraverse(Graph G, Status(*Visit)(int v) for (v=0;vG,vexnum;+v) visitedv=FALSE ; InitQueue(Q); /*置空队列Q*/if (!visitedv) /*v尚未访问*/ EnQucue(Q,v); /*v入队列*/ while (!QueueEmpty(Q) DeQueue(Q,u); /*队头元素出队并置为u*/ visitedu=TRUE; visit(u); /*访问u*/ for
18、(w=FistAdjVex(G,u); w; w=NextAdjVex(G,u,w) /*u的尚未访问的邻接顶点w入队列Q*/ if (!visitedw) EnQueue(Q,w); ? v4,v5会导致v8重复入队3、图的遍历nBFS遍历算法示例（bfs.cpp）3、图的连通n 无向图的连通性思路：n在循环调用DFS时，增加计数n如果计数为0，则为连通，否则为非连通3、图的连通n 有向图的连通性思路：n先对出边表操作，循环调用DFS，并计数，令为N。在每次调用DFS结束后，建立当前VISITED顶点集合。此时可以得到N个顶点集合。n再对入边表操作，循环调用DFS，并计数，令为M。在每次调用
19、DFS结束后，建立当前VISITED顶点集合。此时可以得到M个顶点集合。n比较两次结果，即可得出结论。4、图的生成树和生成森林 n 定义n当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。n若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。n在算法中，需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。4、图的生成树和生成森林 n 定义n对于非连通的无向图
20、，所有连通分量的生成树组成了非连通图的生成森林。4、图的生成树和生成森林 n 算法n对图进行DFS(BFS)遍历n每次循环调用DFS时，表明有一个新的树根节点产生。n在DFS中，找到一个节点连入本次树根节点。4、图的生成树和生成森林 n 算法/*建立无向图G的深度优先生成森林的孩子兄弟链表T*/void DESForest(Graph G, CSTree *T) T=NULL; for (v=0;vG.vexnum;+v) visitedv=FALSE; for(v=0;vnextsibling=p; q=p; /*q指示当前生成树的根*/ DFSTree(G,v,&p); /*建立以p为根的
21、生成树*/生成树采用孩子兄弟表示：(P129)CSTree : data , child, nextsibling4、图的生成树和生成森林 n 算法/*从第v个顶点出发深度优先遍历图G，建立以*T为根的生成树*/void DFSTree(Graph G,int v ,CSTree *T) visitedv=TRUE; first=TRUE; for(w=FirstAdjVex(G,v); w; w=NextAdjVex(G,v,w) if(!visitedw) p=(CSTree)malloc(sizeof)CSNode); /*分配孩子结点*/ *p=GetVex(G,w),NULL,NUL
22、L; /*w是v的第一个未被访问的邻接顶点，作为根的左孩子结点*/ if (first) T-lchild=p; first=FALSE; /*w是其它未被访问的邻接顶点，作为上一邻接顶点的右兄弟*/ else q-nextsibling=p; q=p;/*从第w个顶点出发深度优先遍历图G，建立生成子树*q*/ DFSTree(G,w,&q); 本算法开始始终建立第一个子孩子，然后再建立兄弟，建立兄弟时候first为false,从底部向上建立5、最小生成树 n 定义n无向连通图生成树不是唯一的5、最小生成树 n 定义n按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。
23、n如果无向连通图是网，则必然有一个生成树的各边上的权值之和最小，此时这个生成树称为最小生成树。n构造最小生成树的准则:必须只使用该网络中的边来构造最小生成树；必须使用且仅使用 n-1 条边来联结网络中的 n 个顶点；不能使用产生回路的边。5、最小生成树 n 算法依据：MST性质n在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。UV-U5、最小生成树 n普里姆(Prim)算法算法描述：从连通网络 N = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边
24、(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。采用邻接矩阵作为图的存储表示。5、最小生成树 n普里姆(Prim)算法演示：abcdegf195141827168213127aedcbaaa19141814例如例如:e12ee8168d3dd7213c5 5 19 m m 14 m 1819 5 7 12 m m m 5 3 m m m m 7 3 8 21 m14 12 m 8 m 16 m m m 21 m
25、2718 m m m 16 27abcdefg5、最小生成树 n普里姆(Prim)算法实现(prim.cpp)1、建立矩阵存储图中边的权。 4、初始选任一起点closevertex将矩阵中对应行的权数值lowcostmin得下一点closevertex将矩阵中对应行的权数值lowcostmin得下一点2、建立数组lowcost记录每一顶点到达其他顶点的权数值，用于比较求出最小权数值。 3、建立数组closevertx记录每一顶点最小权值的另一点。 5、每增加一新点，lowcost将会改变，因为新点可能导致到某些点的权数值变小。而closevertx和lowcost记录了全部搜索过程。5、最小生
26、成树 n克鲁斯卡尔 (Kruskal)算法算法描述：设有一个有 n 个顶点的连通网络 N = V, E ：(1)最初先构造一个只有 n 个顶点，没有边的非连通图 T = V, , 图中每个顶点自成一个连通分量。(2)当在 E 中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。(3)如此重复下去，直到所有顶点在同一个连通分量上为止。5、最小生成树 n克鲁斯卡尔 (Kruskal)算法演示：abcdegf195141827168213127aedcbgf148531621例如例如: :71218195、最小生成树
27、n克鲁斯卡尔 (Kruskal)算法实现 (Kruskal.cpp)1、建立所有边的数组，结构如下： typedef struct elemtype v1; elemtype v2; int cost; EdgeType; 并将该数组按照cost升序2、建立father数组，记录填加边的顶点号，如果相互连通，则为同一数字；如果新加边的两个顶点father数组记录相同，为回路，该边被舍弃；否则填加，直到找到n-1个边为止。5、最小生成树 n比较两种算法普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(elog2e + elog2n + n)稠密图稀疏图算法名适应范围*最小堆和并查集算法6、两点之间
28、的最短路径问题n两点之间的最短路径问题n最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小 。(1)、求从某个源点到其余各点的最短路径 Dijkstra算法(2)、每一对顶点之间的最短路径 Floyd算法n通常包括两个问题6、两点之间的最短路径问题n单源最短路径问题 (Dijkstra算法)n问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。n为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一
29、条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。nDijkstra算法示例1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:205164320856230137173296、两点之间的最短路径问题n单源最短路径问题 (Dijkstra算法)算法实现：n引入一个辅助数组dist。它的每一个分量disti表示当前找到的从源点v0到终点vi 的最短路径的长度。初始状态：n若从源点v0到顶点vi有边，则disti
30、为该边上的权值；n若从源点v0到顶点vi 没有边，则disti为+ 。n一般情况下，假设 S 是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从v0 出发，中间只经过S中的顶点便可到达的那些顶点vx (vx V-S )的路径中的一条。n每次求得一条最短路径之后，其终点vk 加入集合S，然后对所有的vi V-S，修改其disti值。6、两点之间的最短路径问题n单源最短路径问题 (Dijkstra算法)算法实现： （ Dijkstra.cpp & Dijkstra.gif） 初始化： S v0 ; distj Edge0j, j = 1, 2, , n-1; / n为图中顶点个数 求
31、出最短路径的长度： distk min disti , i V- S ; S S U k ; 修改： disti min disti, distk + Edgeki , 对于每一个 i V- S ; 判断： 若S = V, 则算法结束，否则转。6、两点之间的最短路径问题nDijkstra算法与Prim 算法的比较nDijkstra算法与Prim 算法都是先指定某个初始集合S，并令第一点到该S中；而将其他点放入V-S集合。n根据最小生成树得MST性质来取下一点，即从V-S集合移到S集合。n移动原则不同：nPrim： S集合中任何一点当前与外部最小权值边的点成为新的加入点。nDijkstra： S
32、集合中除起点外任何一点A与S外部点的权值和从起点到A点距离的和的最小数值。6、两点之间的最短路径问题n所有顶点之间的最短路径问题的提出：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，要求求出vi 与vj之间的最短路径和最短路径长度。方法一：对所有点都运行一次Dijkstra算法方法二： Floyd算法6、两点之间的最短路径问题nFloyd算法的基本思想：定义一个n阶方阵序列： A(-1), A(0), , A(n-1).其中： A(-1) ij = Edgeij； A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,1, n
33、-1 ，i 为外层，j为 内层循环A(0) ij是从顶点vi 到vj , 中间顶点是v0的最短路径的长度, A(k) ij是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度, A(n-1)ij是从顶点vi 到vj 的最短路径长度。6、两点之间的最短路径问题nFloyd算法的实现： (floyd.cpp)1、和 Dijkstra类似，只不过Floyd算全部节点，故此设置矩阵辅助数组：edgeMAXNODEMAXNODE :表示权值；pathMAXNODEMAXNODE :记录路径；2、从任何一个节点开始，令为V1；则意味着：从其它矩阵行中第一列的数值代表其他点到V1的距离 L；从矩阵第一行表示从点V1到其他点的距离J；则：其他点通过点v1到其他非自身点的距离为L+J，如果L+J小于现有行上的距离，则修改edge，同时修改path。6、两点之间的最短路径问题nFloyd算法的演示：6、两点之间的最短路径问题nFloyd算法的演示：6、两点之间的最短路径问题nFloyd算法的演示：6、两点之间的最短路径问题nFloyd算法的演示：
