数据结构之图Python版.pptx

《数据结构之图Python版.pptx》由会员分享，可在线阅读，更多相关《数据结构之图Python版.pptx（52页珍藏版）》请在三一办公上搜索。

1、数据结构之图,1,目录,一、图的定义和术语二、图的存储结构和实现三、图的基本算法及应用,2,第一部分,图的定义和术语,3,哥尼斯堡七桥问题,CB A D,4,一、图的定义,定义：图是由顶点的有穷非空集合和顶点之间边的集合组成.通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。简单图：在图中，若不存在顶点到其自身的边，且同一对顶点之间没有重复出现的边，则称这样的图为简单图。本文讨论的都是简单图,5,二、图的术语,顶点 边 权 网 邻接点 依附 稀疏图 稠密图 子图 有向图 无向图度：入度 出度 度完全图：有向完全图 完全图路径连通 生成树 生成森林,

2、6,二、图的术语,路径：对于图G=(V,E)，如果存在顶点序列，.，并且其中（，），（，），.，（，）E；则说明从顶点 到 之间存在路径，并称顶点序列是从顶点 到 的一条路径。若G是有向图，则路径也是有方向的。路径长度：非带权图中为路径上边的个数；带权图为路径上各边的权之和。回路：第一个顶点和最后一个顶点相同的路径称为回路或环。简单回路：除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路称为简单回路。简单路径：内部不包含回路的路径称为简单路径。,7,二、图的术语,连通：如果在无向图G中存在从Vi到Vj的路径，则说从Vi到Vj连通 无向图：如果无向图G中任意两个顶点vi和vj之间都连通，

3、则称G为连通(无向)图 有向图：如果有向图G中任意两个顶点vi和vj,从vi到vj连通并且从vj到vi也连通，则称G为强连通(有向)图连通分量：无向图：无向图中的极大连通子图，称为连通分量 有向图：有向图中的极大强连通子图，称为强连通分量,8,二、图的术语,生成树：n个顶点的连通(无向图)图G的生成树是包含G中全部顶点的一个极小连通子图性质1：树是一个连通而无环的无向图性质2：具有n个节点的树的边数为n-1性质3：任何一个连通无向图G=(V,E)，若满足丨E丨=丨V丨-1，则其为树,9,二、图的术语,生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非

4、连通图的生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边,10,第二部分,图的存储结构和实现,11,图的抽象数据类型,实现：,12,一、邻接矩阵(数组)表示法,基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。假设图G=(V,E)有n个顶点,则邻接矩阵是一个nn的方阵,定义为:（1）非带权图(2)网图,13,一、邻接矩阵(数组)表示法,无向图的邻接矩阵,14,一、邻接矩阵(数组)表示法,实现：,15,二、邻接表表示法,邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于

5、有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。顶点表 边表vertex：数据域，存放顶点信息。firstedge：指针域，指向边表中第一个结点。adjvex：邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。,16,vertex,firstedge,adjvex,next,二、邻接表表示法,有向图 邻接表 逆邻接表,17,vertex,firstedge,adjvex,next,01234,0123,二、邻接表表示法,实现：,18,三、十字链表示法,有向图的邻接表的改进形式(只用于有向图)：可将邻接表和逆邻接表用一个表实现。顶点表 边表

6、vertex：数据域，存放顶点信息；firstin：入边表头指针；firstout：出边表头指针；tailvex：弧的起点在顶点表中的下标；headvex：弧的终点在顶点表中的下标；headlink：入边表指针域；taillink：出边表指针域。,19,firstout,tailvex,headvex,headlink,vertex,firstin,taillink,info,三、十字链表示法,20,四、邻接多重表示法,无向图的邻接表的改进形式：可避免在邻接表 中表结点数为边的二倍，而且对边进行操作时(比如删除，插入等)要对两个顶点操作，比较麻烦 顶点表 边表iVex和jVex：是与某条边依附

7、的两个顶点在顶点表中的下标。iLink：指向依附顶点iVex的下一条边。jLink：指向依附顶点jVex的下一条边。,21,vertex,firstedge,jvex,ivex,ilink,jlink,info,四、邻接多重表示法,22,0,3,1,2,4,第三部分,图的基本算法及应用,23,一、图的遍历,定义：按某种方式系统的访问图中的每个顶点而且仅访问一次的过程，也称为图的周游。因为图中的顶点代表一个实际问题中的格局或状态，边表示两个顶点之间的某种联系(某种规则、操作、算子、通道或者关系)，从而可以将图的遍历转化为一次穷尽的状态空间搜索问题。一般的状态空间搜索方法有枚举、深度/广度优先搜索

8、、启发式搜索等等,24,一、图的遍历-深度优先搜索,算法思想：（1）访问初始顶点v并标记顶点v已访问。（2）查找顶点v的第一个邻接顶点w。（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。例：如图深度优先搜索结果为：v1-v2-v4-v8-v5-v3-v6-v7根据生成树的性质可知，对于连通图G的深度优先遍历结果得到的是一棵深度优先生成树,25,一、图的遍历-深度优先搜索,算法实现：,2

9、6,一、图的遍历-广度优先搜索,算法思想：（1）顶点v入队列。（2）当队列非空时则继续执行，否则算法结束。（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。（4）查找顶点v的第一个邻接顶点col。（5）若v的邻接顶点col未被访问过的，则col入队列。（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。例：如图广度优先搜索结果为：v1-v2-v3-v4-v5-v6-v7-v8根据生成树的性质可知，对于连通图的深度优先遍历结果得到的是一棵宽度优先生成树,27,一、图的遍历-广度优先搜索,算法实现：,28,二、最小生成

10、树,生成树的代价：设G=（V，E）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。最小生成树的概念可以应用到许多实际问题中。例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？,29,二、最小生成树,MST性质：假设G=(V,E)是一个无向连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中uU，vVU，则必存在一棵包含边(u,v)的最小生成树。,30,二、最小生成树-Kruskal算法,克鲁斯卡尔算法的基本思想

11、为：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。Kruskal算法,31,V1,V4,V2,V3,V5,V6,6,5,1,5,5,3,6,4,2,6,V1,V3,V6,V4,V2,V5,二、最小生成树-Kruskal算法,算法实现：,32,二、最小生成树-Prim算法,普里姆算法的基本思想是：首先选取图中任意一个顶点 v 作为生成树的根，之后继续往生成树中添加顶点 w，则在顶点 w 和顶点 v 之间必须有边，且该边上的权值应在所有和 v 相邻接的边中属最小。Prim算法,33,V1,V4,V2,

12、V3,V5,6,5,1,5,5,3,6,4,2,6,V1,V3,V4,V2,V5,V6,V6,二、最小生成树-Prim算法,算法实现：,34,三、最短路径,定义：在网图中，最短路径是指两顶点之间经历的边上权值之和最短的路径。,35,AE：100ADE：90 ADCE：60 ABCE：70,三、最短路径-单源点,单源点最短路径问题：给定带权有向图G(V,E)和源点vV，求从v到G中其余各顶点的最短路径单源最短路径的概念可以应用到许多实际问题中。例：计算机网络传输的问题：怎样找到一种最经济的方式，从一台计算机向网上所有其它计算机发送一条消息？,36,三、最短路径-Dijkstra算法,迪杰斯特拉的

13、基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对viV-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v,vk，就将vk加入集合S中，并将路径v,vk,vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。,37,三、最短路径-Dijkstra算法,38,10,50,30,10,100,20,60,三、最短路径-Dijkstra算法,算法实现：,39,三、最短路径-任意两顶点,任意两顶点之间的最短路径问题：给定带权有向图G(V,E)和源点vV，求图G中任意两个顶点的最短路径任意两顶点之间的最短路径

14、的概念可以应用到许多实际问题中。例：暑假，小明准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。,40,三、最短路径-Floyd算法,弗洛依德算法的基本思想：求从任意的顶点vi 到vj 的最短路径。第一步：首先考虑vi 到vj 存在长度为Dis(i,j)的路径，但可能不是最短路；第二步：考虑（vi,v0,vj)是否存在，若存在是否小于(vi,vj),取更小的；第三步：再考虑（vi,v1,vj)是否存在，若存在与刚才小者比较，取最小的；第N步：类推(vi,vk,vj)为vi 到vj 经过顶点序号不大

15、于k-1 的最短路径。当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离,41,三、最短路径-Floyd算法,算法实现：,42,四、AOV网,定义：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。AOV网特点：1.AOV网中的弧表示活动之间存在的某种制约关系。2.AOV网中不能出现回路。拓扑序列：设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。拓扑排序：对一个有向图构

16、造拓扑序列的过程称为拓扑排序。,43,拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到满足。,四、AOV网-拓扑排序算法,算法基本思想：从AOV网中选择一个没有前驱的顶点并且输出；从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧；重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。,44,四、AOV网-拓扑排序算法,45,拓扑序列：,C1,C2,C3,C4,C5,C6,C7,四、AOV网-拓扑排序算法,算法实现：,46,五、AOE网,定义：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网

17、，简称AOE网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。AOE网的性质：只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。AOE网的概念可以解决一下实际的问题：1.完成整个工程至少需要多少时间?2.为缩短完成工程所需的时间,应当加快哪些活动?,47,五、AOE网-关键路径,关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。关键活动：关键路径上的活动称为关键活动。由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时

18、间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。,48,五、AOE网-关键路径算法,算法基本思想：事件的最早发生时间Vek：i、从前向后，取大值：直接前驱结点的ej到达边（指向顶点的边）的权值，有多个值的取较大者 ii、首结点Vej已知，为0 事件的最迟发生时间Vlk：i、从后向前，取小值：直接后继结点的lj 发出边（从顶点发出的边）的权值，有多个值的取较小者;ii、终结点Vlj已知，等于它的Vej）活动的最早开始时间ei：ei=Vek;（即：边（活动）的最早开始时间等于，它的发出顶点的最早发生时间)活动的最晚开始时间li:li=Vlj-len（为边（活动）的到达顶点的最晚发生时间减去边的权值最后计算各个活动的时间余量 lk-ek，时间余量为0者即为关键活动。,49,五、AOE网,AOE网,50,五、AOE网-关键路径算法,算法实现：,51,THANKS!,52,