《算法与数据结构》第5章图与网ppt.ppt

算法与数据结构,第5章 图与网,第5章 图与网,图与网是更为复杂的数据结构，数据元素之间的关系既不是线性表中的一对一的邻接关系，也不是树型结构中的一对多的层次关系，而是一种多对多的网状关系，任意两个数据元素之间都可能相关。 由于许多问题都可以用图或网来表示，所以其应用已渗透到语言学、逻辑学、物理、化学、电子、通讯、数学等诸多学科领域。,第5章 图与网,5.1 图与网的基本概念 5.2 图与网的存储结构 5.3 图的遍历 5.4 无向连通网的最小生成树 5.5 有向网的最短路径 5.6 有向无环图及其应用,5.1 图与网的基本概念,5.1.1 图与网的定义 5.1.2 图的相关术语,图的定义,图（graph）是由非空的顶点集合V和描述顶点间关系的弧（或边）的集合E组成的二元组，即 G=(V，E) 其中： V=vi | vidataobject，E= | vi , vjV， dataobject是具有相同性质的数据元素（即顶点）的集合； 表示从vi到vj有一条边单向相连称作弧，且称vi为弧尾（起点），vj为弧头（终点），此时称图为有向图（digraph）。 若E，必有E，则可以用无序对（vi , vj）代替这两个有序对，即从vi 到 vj有一条双向边（即无向边，也可看作双向边）相连称作边，此时图称为无向图（undigraph）。,图的示例,G1=(V1，E1) 其中： V1=v1，v2，v3，v4， E1=， ，；,G2=(V2，E2) 其中： V2=v1，v2，v3，v4，v5， E2=(v1，v2)，(v1，v4)， (v2，v3)，(v2，v5)， (v3，v4)，(v3，v5),图的定义（续）,如果用n表示图中顶点数目，用e表示边或弧的数目，且不考虑顶点到自身的边或弧，那么对于无向图e的取值范围是0到n(n-1)/2，而对于有向图e的取值范围为0到n(n-1)。 把具有n(n-1)/2条边的无向图称为无向完全图； 把具有n(n-1)条弧的有向图称为有向完全图； 有向完全图和无向完全图统称完全图（completed graph）。 若图中边或弧的数目很少则称为稀疏图（sparse graph），反之边或弧的数目接近完全图则称为稠密图（dense graph）。,子图的定义,假设有两个图G=（V，E）和G=（V，E），如果V V且E E，则称G是G的子图（subgraph）。 子图示例如下：,网的定义,把图中与边或弧相关的数称之为权(weight)；权可以表示从一个顶点到另一个顶点的距离、时间、电流、电压、耗费等， 通常把这种带权图称作网（network）； 当然也可以依据边或弧有无向网和有向网的概念。 网的示例如下图：,5.1 图与网的基本概念,5.1.1 图与网的定义 5.1.2 图的相关术语,图的相关术语,在无向图中，某个顶点的度（degree）是指所依附于该顶点的边的数目，顶点v的度通常记作TD（V）。例如在无向图G2中，TD（v1）=2，TD（v2）=3，TD（v3）=3，TD（v4）=2，TD（v5）=2。,在有向图中要区别顶点的入度和出度的概念， 入度是指以顶点V为终点的弧的数目，通常记作ID(V)； 出度是指以顶点V为始点的弧的数目，通常记作OD(V)； 顶点的度定义为入度和出度的和，即: TD（V）=ID（V）+OD（V）。,图的相关术语（续）,例如在有向图G1中， ID（v1）=1，OD（v1）=2，TD（v1）=3； ID（v2）=1，OD（v2）=0，TD（v2）=1； ID（v3）=1，OD（v3）=1，TD（v3）=2； ID（v4）=1，OD（v4）=1，TD（v4）=2。,一般地，对于具有n 个顶点e条边或弧的图，边或弧的个数与各顶点的度TD（vi）之间满足如下关系：,图的相关术语（续）,在无向图G=（V，E）中，若（vp，vi1），（vi1，vi2） （vin，vq）都是E中的边，则称结点序列vp，vi1，vi2 vin，vq为从vp到vq的一条路径； 在有向图中，则要求， 都是E中的弧。 路径（path）长度定义为路径上边或弧的数目； 如有向图G1中有，所以说从V3到V2存在一条长度为3的路径； 如无向图G2有(v1，v2)，(v2，v5)和(v1，v4)，(v4，v3)，(v3，v5)，所以说从V1到V5存在一条长度各为2和3的路径。,图的相关术语（续）,如果顶点序列中不出现重复顶点，则称顶点序列为简单路径，例如前面所举三条路径的顶点序列分别为v3、v4、v1、v2和v1、v2、v5与v1、v4、v3、v5，均无重复顶点出现都是简单路径。 第一个顶点和最后一个顶点相同（即vp =vq）的简单路径称为简单回路或环（cycle）， 例如在有向图G1中的v1，v3，v4，v1和无向图G2中的v1，v4，v3，v2，v1与v2，v3，v5，v2等都是简单回路或环。,图的相关术语（续）,在无向图中，如果从一个顶点vi到另一个顶点vj 有路径，则称vi和vj是连通的；如果图中任意两个顶点vi和vj都是连通的，则称该无向图是连通图（connected graph）。例如无向图G2是连通图，,而如下无向图G5是非连通图。,图的相关术语（续）,无向图的极大连通子图称为图的连通分量（connected component）。 例如下图给出了无向图G5的两个连通分量。,图的相关术语（续）,在有向图中，如果对于任意两个顶点vi和vj（vivj）从vi到vj和从vj到vi都存在路径，则称该有向图为强连通图（strong graph）。 有向图的极大强连通子图称为图的强连通分量（strongly connected component）。 例如有向图G1不是强连通图，它的两个强连通分量如下图所示。,图的相关术语（续）,一个连通图的生成树（spanning tree）是该图的一个极小连通子图，它包含图中全部的n个顶点和连通这n个顶点的n-1条边。 如果在生成树上添加任意一条原图中的其它边必定会产生回路或环；换句话说，有n个顶点n条或n条以上边的无向图一定存在回路或环。如果n个顶点的图其边数少于n-1条，则一定是非连通图。 例如无向图G2的一棵生成树如下图所示。,图的相关术语（续）,在非连通图中，由每个连通分量都可以得到一个极小连通子图，即一棵生成树，这些连通分量的生成树就构成了该非连通图的生成森林。 对于有向图，其生成树或生成森林必定是有向树和有向森林。 例如无向图G5的生成森林如下图所示。,第5章 图与网,5.1 图与网的基本概念 5.2 图与网的存储结构 5.3 图的遍历 5.4 无向连通网的最小生成树 5.5 有向网的最短路径 5.6 有向无环图及其应用,图和网的存储结构,由于图的结构复杂，其数据元素间存在着多对多的网状关系，所以无法用物理位置关系表示元素间的逻辑关系，即不存在顺序存储结构； 但可借用数组来表示元素间的逻辑关系。由于图中顶点的度差别一般较大，故也不宜采用多重链表存储结构； 但可根据图的具体情况和需要进行的操作，设计恰当的结点结构和表结构来存储顶点信息和顶点间的关系，,5.2 图与网的存储结构,5.2.1 邻接矩阵 5.2.2 邻接表与逆邻接表 5.2.3 邻接多重表,邻接矩阵,所谓邻接矩阵（adjacency matrix）存储结构，就是用一维数组存储图或网的顶点信息，用二维数组表示顶点之间的邻接关系（即邻接矩阵）。 若G=（V，E）是具有n个顶点的图或网，G的邻接矩阵A是如下定义的n阶方阵： 当G是无向图或有向图时，矩阵A中元素定义为,邻接矩阵（续）,当G是无向网或有向网时，矩阵A中元素定义为 其中：Wij表示边或弧上的权值，表示一个所用计算机上所允许的大于所有权值的数或者一个特殊的其它值。,邻接矩阵存储结构举例,邻接矩阵存储,邻接矩阵存储,邻接矩阵存储结构举例(续),邻接矩阵存储,邻接矩阵存储,邻接矩阵存储结构的特点,从图的邻接矩阵存储表示容易看出该表示法具有如下特点： 无向图或网的邻接矩阵一定是一个对称矩阵，因此在存储邻接矩阵时可以只存储其上三角阵或下三角阵以节省存储空间。 对于无向图或网，其邻接矩阵中第i行（或第i列）中非零元素（或非元素）的个数正好是第i个顶点的度。即,邻接矩阵存储结构的特点(续),对于有向图或网，其邻接矩阵中第i行中非零元素（或非元素）的个数正好是第i个顶点的出度OD(vi)，而第i列中非零元素（或非元素）的个数正好是第i个顶点的入度ID(vi) 。即 很容易确定图或网中任意两个顶点之间是否有边或弧相连；但要确定图或网中有多少条边或弧则需要逐行逐列扫描方阵，时间代价是O(n2)，这是该方法的局限性。,邻接矩阵存储图或网的类型定义,用一维数组存储顶点信息，用邻接矩阵存储顶点间关系信息的图或网的形式描述如下： #define maxvernum 100 #define infinity maxinteger typedef struct vertextype vexmaxvernum; int adjmatrixmaxvernummaxvernum; int n,e; /*定义顶点数和边或弧数变量单元*/ mgraph;,5.2 图与网的存储结构,5.2.1 邻接矩阵 5.2.2 邻接表与逆邻接表 5.2.3 邻接多重表,邻接表,邻接表（adjacency list）是图和网的一种链式存储结构。在邻接表中，对图或网中的每个顶点建立一个单链表，第i个单链表中的结点是与vi相关联的边所联结的结点（对有向图是以顶点vi为尾的弧所联结的结点，即弧头结点）。 每个结点由三个域组成，其中：邻接点域adjvex指示与顶点vi邻接的点在图中的位置，链域next指示下一条边或弧所联结的结点，数据域info存储和边或弧相关的信息（如网中的权值等）。每个单链表都附设一个表头结点，如下图所示。,邻接表（续）,除了设有链域next指向链表中的第一个结点外，还设有数据域data存放顶点vi的有关信息（如顶点名，顶点位置等）。 这些表头结点也可以组织为一个链表，但通常以向量形式存储于一维数组中，以方便随机访问任一顶点的单链表。 例如有向网G3的邻接表如下图所示。,邻接表举例,无向网G4的邻接表如下图所示。,邻接表中结点和表头结点的形式描述,邻接表中结点和表头结点的形式描述定义如下： #define maxvernum 100 typedef struct node /*定义表结点结构*/ int adjvex,info; struct node *next; nodetype; typedef struct frontnode /*定义表头结点结构*/ vertextype data; struct node *next; frontnodetype; typedef frontnodetype adjlistmaxvernum;,邻接表与逆邻接表,若无向图或网中有n个顶点e条边，则它的邻接表需n个表头结点和2e个表结点。显然在边稀疏的情况下，用邻接表比邻接矩阵节省存储空间，当与边相关的信息较多时更是如此。 在无向图或网的邻接表中，顶点vi的度恰为第i个链表中的结点数。在有向图或网的邻接表中，第i个链表中的结点数只是顶点vi的出度；为了求vi的入度，必须遍历整个邻接表，所有邻接点域adjvex的值为i的结点个数是顶点vi的入度。 有时为了便于确定顶点的入度或以vi为头的弧，可以建立逆邻接表，即对vi建立一个链接以vi为头的弧的表。 在邻接表上，可以很方便地找到任一顶点的第一个邻接点和下一个邻接点；但要判定任意两个顶点vi和vj之间是否有边或弧相连，则需要第i个或第j个单链表，在这一点上不及邻接矩阵方便。,逆邻接表举例,有向网G3的逆邻接表如下图所示,5.2 图与网的存储结构,5.2.1 邻接矩阵 5.2.2 邻接表与逆邻接表 5.2.3 邻接多重表,邻接多重表,邻接多重表(adjacency multilist)是无向图和网的另一种链式存储结构。 在邻接表中，可以很方便地得到关于顶点和边的有关信息；然而和一条边(vi，vj)相关联的两个结点vi和vj分别存储在第i和第j两个单链表中，给无向图或网的某些操作带来不便。 例如，要对已搜索过的边作记号或删除一条边等操作，需要找到表示同一条边的两个结点。在对无向图或网进行这一类操作的问题中，宜采用下面将要介绍的邻接多重表作存储结构。,邻接多重表（续）,在邻接多重表中，每一条边用一个结点来表示，每个结点由五个或六个域组成，如下图所示。 其中：mark为标志域，可用来标记该条边是否已被搜索过；ivex和jvex为该边所关联的两个顶点在图中的位置或序号；ilink指向下一条依附于顶点ivex的边，jlink指向下一条依附于顶点jvex的边； 需要时还可增加一个存放和边相关的各种信息的域info。,邻接多重表（续）,无向图或网中的每个顶点也用一个结点表示，它由存储与该顶点相关的信息的域data和指示第一条依附于该顶点的边的域firstedge组成，如下图所示。 在邻接多重表中，所有依附于同一个顶点的边都链接在同一个链表中；由于每一条边都依附于两个顶点，所以每一个边结点都同时链接在两个链表中。 由此可见，对于无向图和无向网而言，其邻接多重表和邻接表的差别仅在于同一条边在邻接表中用两个结点而在邻接多重表中只用一个结点。 除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。在邻接多重表中，各种基本操作的实现也和邻接表相似。,邻接多重表的边结点和顶点结点的形式描述,邻接多重表的边结点和顶点结点的形式描述定义如下： typedef struct edgenode /*定义边结点类型*/ int mark ,ivex ,jvex; /*对于网可增加整型info域*/ struct edgenode *ilink,*jlink; edgenodetype ; typedef struct vexnode /*定义顶点结点类型*/ int data; struct edgenode *firstedge; vexnodetype; typedef vexnodetype adjmulistmaxvernum;,邻接多重表举例,邻接多重表举例（续）,第5章 图与网,5.1 图与网的基本概念 5.2 图与网的存储结构 5.3 图的遍历 5.4 无向连通网的最小生成树 5.5 有向网的最短路径 5.6 有向无环图及其应用,图的遍历,和树的遍历类似，图的遍历（traversing graph）是指从图中的任一顶点出发访问图中所有顶点，且使每个顶点仅被访问一次的过程。 然而由于图结构本身的复杂性，使得图的遍历比树的遍历复杂得多，主要表现在以下几个方面： 图中没有一个惟一的开始结点，可以从任意一个顶点开始访问； 从一个顶点出发只能访问到它所在连通分量的各顶点，对于非连通图还需考虑其它连通分量上顶点的访问；,图的遍历（续）, 如果有回路存在，一个顶点被访问之后又可能沿回路回到该顶点，为了避免对同一顶点的多次访问，在遍历过程中必须记下已访问过的顶点，通常利用一维辅助数组记录顶点被访问的情况； 一个顶点可以和多个顶点相邻接，当访问过这个顶点之后如何选择下一个要访问的顶点。 图的遍历是图的重要操作，对图和网的许多操作都是建立在对图的遍历操作的基础之上，如图的连通性问题，拓扑排序问题等。通常有两种遍历图的方法，即深度优先搜索遍历和广度优先搜索遍历，这两种遍历方法对无向图和有向图都适用。,5.3 图的遍历,5.3.1 深度优先搜索遍历 5.3.2 广度优先搜索遍历 5.3.3 图的遍历应用举例 图的连通性与生成树,深度优先搜索遍历,图的深度优先搜索（depth-first search）遍历类似于树的先根次序遍历，是树的先根次序遍历的推广。 其递归定义如下： 从图中某个顶点v0出发并访问它； 依次从v0的未被访问的邻接顶点出发深度优先遍历图，直到图中所有从v0出发有路径可达的顶点都已被访问到； 若图中还有顶点未被访问到，则另选一个未被访问的顶点记作v0转，否则图的深度优先遍历结束。,深度优先搜索遍历（续）,在深度优先搜索遍历开始时，图G的初始状态是所有顶点都未曾被访问： 首先从某一顶点v0出发并访问它； 然后访问与v0相邻接的顶点vi，下一个要访问的是与顶点vi相邻接的尚未被访问的顶点vj，再下一个是与vj相邻接的尚未被访问的顶点vk， 依此类推直到某个顶点所有的邻接顶点都已被访问过时达到最“深处”； 此时逐层回退到某个尚有邻接顶点未被访问的顶点vr，再从vr的一个未被访问的邻接顶点出发重复上述过程；,深度优先搜索遍历（续）,直到图中从v0出发有路径可达的顶点都访问到时，图的一个连通分量深度优先搜索遍历结束， 对于非连通图中的其它连通分量，还要继续上述的深度优先搜索遍历过程，直到图中所有顶点都被访问过时止。,例如，对于右图的无向图G6的深度优先搜索遍历，若从v1出发结点的访问顺序为 v1v2v4v8v5v3v6v7,深度优先搜索遍历（续）,假设图用邻接表作存储结构，图中n个顶点的表头结点存入数组gn+1中，并用1到n作为标识每一个顶点的序号，gi存放顶点vi的有关信息，v为给定的出发顶点序号。 为了在遍历过程中区分顶点是否已被访问过，设置标志数组cn+1，初始值全为0，一旦顶点vi被访问时置ci为1。,深度优先搜索遍历（续）,从顶点v 出发按深度优先搜索遍历图的递归算法dfs如下： void dfs(adjlist g,int v,int c) int i ; nodetype *p; cv=1; printf(“%dn”,v); /*访问顶点v*/ for(p=gv.next;p!=NULL;p=p-next) i=p-adjvex; if(ci=0) dfs(g,i,c); ,深度优先搜索遍历（续）,对整个图的遍历算法travergraph如下： void travergraph(adjlist g ,int n ) int v; int cn+1; for(v=1;v=n;v+) cv=0; /*标志数组初始化*/ for(v=1;v=n;v+) if(cv=0) /*按深度优先遍历图g*/ dfs(g,v,c); ,深度优先搜索遍历（续）,在遍历时，对每个顶点至多调用一次dfs函数；因为一旦某个顶点被标志为已被访问，就不会再从它出发进行搜索。 因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程，其时间耗费取决于所采用的存储结构。 在上述以邻接表作图的存储结构时，找邻接点所需时间为O(e)，e为无向图的边数或有向图的弧数。由于在travergraph中需要O(n)的时间建立标志数组，故深度优先搜索遍历图的时间复杂度为O(n+e)。,5.3 图的遍历,5.3.1 深度优先搜索遍历 5.3.2 广度优先搜索遍历 5.3.3 图的遍历应用举例 图的连通性与生成树,广度优先搜索遍历,广度优先搜索(broadth-first search)遍历类似于树的按层次遍历，是树的层次次序遍历的推广。 其定义如下： 从图中某个顶点v0出发并访问它； 依次访问v0的各个未被访问的邻接顶点，然后分别从这些邻接顶点出发依次访问它们的邻接顶点，并使先被访问顶点的邻接顶点先于后被访问顶点的邻接顶点，直到图中已被访问过的顶点的邻接顶点都被访问到； 若图中还有顶点未被访问到，则另选一个未被访问的顶点记作v0转，否则图的广度优先遍历结束。,广度优先搜索遍历（续）,换句话说，图的广度优先搜索遍历过程是：从v0出发由近及远依次访问有路径可达且路径长度分别为1、2、3、的各顶点。,例如对右图的无向图G6进行广度优先搜索遍历； 从v1出发访问v1，然后访问v1的邻接点v2和v3，紧接着访问v2的邻接点v4和v5，v3的邻接点v6和v7，最后访问v4的邻接点v8。此时所有顶点均已被访问过，图G6的广度优先搜索遍历完成，得到的广度优先搜索遍历顶点序列为 v1v2v3v4v5v6v7v8,广度优先搜索遍历（续）,由于先被访问顶点的邻接顶点先于后被访问顶点的邻接顶点被访问，在广度优先搜索遍历时应设置队列q存放已被访问过的顶点以保证按层次依次访问它们的邻接顶点； 同时需要设置一个数组c记录顶点是否已被访问的情况。 假定图以邻接表存储，其它约定也和深度优先搜索算法相同。,广度优先搜索遍历（续）,图的广度优先搜索算法bfs可描述如下： void bfs(adjlist g,int v,int c) int qN+1,r=0,f=0; nodetype *p; cv=1; printf(“%dn”,v); q0=v; while(fadjvex; if(cv=0) cv=1; printf(“%dn”,v); q+r=v; p=p-next; ,广度优先搜索遍历（续）,在图的广度优先搜索算法中，每个顶点至多进一次队列。 图的遍历过程实质上是通过边或弧找邻接顶点的过程， 因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同都为O(n+e)， 两者的区别仅在于对顶点的访问次序不同(即bfs和dfs的差别),5.3 图的遍历,5.3.1 深度优先搜索遍历 5.3.2 广度优先搜索遍历 5.3.3 图的遍历应用举例 图的连通性与生成树,图的连通性问题,对于无向图G进行遍历时，若G是连通图，仅需从图中任一顶点v0出发进行深度优先搜索遍历或广度优先搜索遍历访问完图中所有顶点； 若G是非连通图，则需从多个顶点出发进行搜索遍历，每一次从一个未被访问过的顶点出发，遍历过程中访问到它所在连通分量中的所有顶点。,例如对左图的无向图G2，从v1出发深度优先搜索遍历得到顶点序列v1v2v3v4v5，访问完所有顶点；,图的连通性问题（续）,例如对右图的无向图G5，从A出发深度优先搜索得到顶点序列ABDHGC只访问完一个连通分量，还需再从E出发深度优先搜索得到结点序列EF才访问完所有结点。,图的连通性问题（续）,由此，我们只要在算法travergraph中设置一个计数器变量count并赋初值为0，每调用一次dfs(或bfs)就给count加1，在算法执行结束时就可依据count的值是否为1判定图G 是否连通图了； 同样的道理，在travergraph算法中每次调用dfs(或bfs)之间设置输出标志，就可以区分非连通图G的连通分量了。也就是说，利用图的遍历算法可以确定无向图的连通性，也可以求无向图的连通分量。 同样的道理，对于有向图G进行遍历时，可利用travergraph算法判定有向图G是否为强连通图，也可以利用travergraph算法求有向图G 的强连通分量。,生成树,一个含有n个顶点的连通图的生成树，是图的一个极小连通子图，它包含图中全部n个顶点和保证使任意两个顶点连通所需的n-1条边。 对于无向连通图G=(V,E)，从任一顶点v0出发遍历图G时，必定将边的集合E划分为两个集合E1和E2。 其中：E1为遍历过程中所经过的边(不含回边)的集合。E2为其余边的集合。 由E1和顶点集合V一起构成图G的极小连通子图，就是G的生成树。 由深度优先遍历得到的生成树称为深度优先生成树，由广度优先搜索遍历得到的生成树称为广度优先生成树。,生成树举例,由图可见，连通图的生成树不惟一。从图中的不同顶点出发，或者采用不同的遍历方法，遍历图的过程中经过的边不同，得到的生成树也就不同。,生成森林,对于非连通的无向图，遍历过程中得到几棵生成树；有几个连通分量就有几棵生成树，即为生成森林。 和生成树的道理一样，生成森林也是不惟一的。 对于有向图G进行深度优先搜索遍历或广度优先搜索遍历，若有向图G是强连通图，则得到的是一棵深度优先有向树或一棵广度优先有向树；若有向图G是非强连通图，则得到的是有向森林。,生成森林举例,第5章 图与网,5.1 图与网的基本概念 5.2 图与网的存储结构 5.3 图的遍历 5.4 无向连通网的最小生成树 5.5 有向网的最短路径 5.6 有向无环图及其应用,5.4 无向连通网的最小生成树,5.4.1 最小生成树的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,最小生成树的概念,对于一个无向网（即带权无向图），生成树上各边权值之和称为这棵生成树的代价；最小代价生成树是各边权值总和最小的生成树，简称最小生成树(minimum spanning tree)。 例如下图所示无向连通网G7和它的最小生成树：,最小生成树的应用,最小生成树有很多实际应用。 例如要在n个城市之间建立通讯网，连通n个城市只需要n-1条线路；而每两个城市之间都可以设置一条线路，相应地都要付出一定代价；n个城市之间最多可能设置n(n-1)/2条线路，如何在其中选择n-1条以使总的耗费最少？即求通讯网的最小生成树问题。 又如要在m个村庄之间修建公路，使这m个村庄村与村之间可达且总的修建费用最少；此问题是一个以村为顶点，以村与村直达公路为边其修建费用为权的公路网求最小生成树的问题。 一个无向连通网的最小生成树也可能不是惟一的，但其总代价一定是最小的。,5.4 无向连通网的最小生成树,5.4.1 最小生成树的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,Prim算法,Prim算法是从连通网中的某一个顶点开始，以此作为生成树的初始状态，然后不断地将网中的其它顶点添加到生成树上，直到最后一个顶点添加到生成树上时得到最小生成树。 其具体方法是： 从网中任一顶点开始，先把该顶点包含在生成树中，此时生成树只有一个顶点； 找出一个端点在生成树中另一个端点在生成树外的所有边，并把权值最小的边连同它所关联的另一个顶点添加到生成树中；当有两条及以上具有相同最小权值的边可供选择时，选择其中任意一条都可以； 反复执行，直到所有顶点都包含在生成树中时止。,利用Prim算法构造最小生成树的过程,下图给出了利用Prim算法从顶v1开始得到无向连通网G7的最小生成树的过程：,Prim算法（续）,为了实现Prim算法，需设一个辅助数组closedge以记录每次选择的权值最小的边。 数组元素closedgei对应于序号为i的顶点vi，它包含两个域adjvex和lowcost。 若vi已在生成树上，则置closedgei.lowcost=0； 若顶点vi不在生成树上，用closedgei. lowcost存放vi与生成树上的顶点构成的最小代价边的权值， 而用closedgei.adjvex存放该边所关联的生成树上的另一顶点的序号。,Prim算法（续）,设有n个顶点的无向连通网以邻接矩阵g存储，从序号为k的顶点vk开始构造最小生成树，则辅助数组的初始情况为： closedgek.lowcost=0; closedgei.lowcost=g.adjmatrixk,i (ik且1in) closedgei.adjvex=k; (ik且1in) 然后从数组中选出某一个j，它满足closedgej.lowcost不等于0且是最小的值，将vj添加到生成树上并修改closedge数组中的值。如此不断进行下去，直到全部的n个顶点都在生成树上，就得到了要求的最小生成树。,Prim算法的形式化描述,#define m 30 /*m为顶点的个数最大值*/ #define max 99 /*max为权的上限值*/ void prim(mgraph g,int k,int n) int i,j,min,p; struct int adjvex; int lowcost; closedgem; for(i=1;i=n;i+) /*辅助数组初始化*/ if(i!=k) closedgei.adjvex=k; closedgei.lowcost=g.adjmatrixki; closedgek.lowcost=0;,Prim算法的形式化描述（续）,for(i=1;in;i+) p=1; min=max; for(j=1;j=n;j+) /*选最小权值及对应顶点vp*/ if(closedgej.lowcost!=0 ,Prim算法的形式化描述（续）,for(j=1;j=n;j+) if(g.adjmatrixpjclosedgej.lowclst) closedgej.lowcost=g.adjmatrixpj; closedgej.adjvex=p; /*选一条边及对应顶点结束*/ /*prim结束*/ 在该算法中有一个两重循环，外层执行n-1次，里层两个并列循环各执行n次。所以Prim算法与网中的边数无关，其时间复杂度为O(n2)，适合于求边稠密的网的最小生成树。,在Prim算法中辅助数组中各分量值变化举例,下表中给出了利用Prim算法求无向连通网G7从顶点v1出发生成树的过程中辅助数组中各分量值的变化情况。,5.4 无向连通网的最小生成树,5.4.1 最小生成树的概念 5.4.2 Prim算法 5.4.3 Kruskal算法,Kruskal算法,Kruskal算法是求无向连通网的最小生成树的另一种常用算法。它与Prim算法不同，时间复杂度主要与网中边的条数e相关为O(eloge)，适合用于求边稀疏的无向连通网的最小生成树。 Kruskal算法的思想为： 将n个顶点看作是n个独立的连通分量，将e条边按权值大小由小到大排序； 从权值最小的边开始依权值递增顺序查看每一条边，如果该边所依附的两个顶点在不同的连通分量上，则选定此边连接两个连通分量为一个连通分量，否则舍弃此边； 反复执行，直到所有顶点都在同一个连通分量上为止，这个连通分量即为所求的最小生成树。,利用Kruskal算法构造最小生成树的过程,第5章 图与网,5.1 图与网的基本概念 5.2 图与网的存储结构 5.3 图的遍历 5.4 无向连通网的最小生成树 5.5 有向网的最短路径 5.6 有向无环图及其应用,有向网的最短路径,如果右图中的G7表示一个已建成的公路交通网，顶点表示不同的村庄(或城镇)，边表示村庄(或城镇)间的公路，边上的权值表示公路的长度，从村庄(或城镇)v1到村庄(或城镇)v7走哪条路径最短呢？,或者边上的权值代表时间，走哪条路径最快呢？或者边上的权值代表乘车费用，走哪条路径最省钱呢？如果在每个村庄(或城镇)都需要换乘车辆，走哪条路换乘次数最少呢？诸如此类问题，归结起来就是一个求网中顶点之间最短路径的问题，即要求路径上边的权值之和最小或边的条数最少。,有向网的最短路径（续）,考虑到交通网的有向性，如公路的上坡和下坡、航运的顺水和逆水其时间等不一样，这里讨论有向网的最短路径(shortest path)，并称路径上的第一个顶点为源点(sourse)，最后一个顶点为终点(destination)。 对于无向网的最短路径问题，可以利用有向网求最短路径的算法来求解，只不过把无向网中的一条边看作两条权值相等方向相反的弧罢了。,5.5 有向网的最短路径,5.5.1 单源最短路径 5.5.2 所有顶点对之间的最短路径,单源最短路径,所谓单源最短路径，是指从一个顶点（源点）出发到其它各顶点的最短路径，即给定有向网G和源点vk，求从vk到G 中其它各顶点vj(j=1,2,n, jk)的最短路径。 迪杰斯特拉(E.W.Dijkstra)提出了一种按路径长度递增的次序产生最短路径的算法。 其基本思想是，把网中所有顶点分成两组，第一组是已确定最短路径的顶点集合S，第二组是尚未确定最短路径的顶点集合V；把V中的顶点按最短路径长度递增的顺序逐个添加到S中，添加过程中始终保持从vk到S中每个顶点的最短路径长度都不大于从vk到V中任何顶点的最短路径长度，直到从vk出发可以到达的顶点都在S中时止。,单源最短路径（续）,一开始时，S中只有顶点vk，其余顶点在V中。 这里引入一维辅助数组dist，用disti表示在当前时刻所找到的从源点vk到每个终点vi的最短路径长度；其初始值为：distk=0，若存在弧则disti为其弧上的权值，否则从vk到vi无弧时distk=。 然后每次从V中的顶点中选取一个dist值最小的顶点vj（distj=mindisti|viV）加入到S中；并对V中顶点的dist值进行相应修正，即若以加入S中的顶点vj做中间顶点使得V中某顶点的dist值更小时要相应修改该顶点的dist值。这样从V中选一个顶点加入S中，对V中顶点的dist值修改一遍，只需做n-1次就可求得从vk到其余各顶点的最短路径。,单源最短路径（续）,在求最短路径的过程中，最短路径长度已记在dist数组中，同时需要把路径也记下来。 为此我们设一维数组pre，prei中存放从vk到vi的路径上vi前一个顶点的序号；若从vk到vi无路径可达，则vi的前一个顶点序号用0表示（即prei=0）。 在算法结束时，沿着顶点vi对应的prei向前追溯就能确定从vk到vi的最短路径，其最短路径长度为disti。 设有向网用邻接矩阵a表示，ai,j表示弧上的权值，无弧时ai,j为max；ai,i=0，当vi进入S 中时用ai,i=1来标识。,最短路径的Dijkstra算法描述,求有向网中从顶点vk出发到其它各顶点的最短路径的Dijkstra算法如下： void dijkstra(int a,int k,int pre,int dist,int n) int i,j,p,min; for (i=1;i=n;i+) disti=aki; if (distimax) prei=k; else prei=0; prek=0; distk=0; akk=1;,最短路径的Dijkstra算法描述(续),for (p=1;p=n-1;p+) min=max; j=-1; for(i=1;i=n;i+) /*在V中选dist最小的顶点*/ if (aii=0 /*dijkstra*/,最短路径的Dijkstra算法举例,最短路径的Dijkstra算法举例(续),使用Dijkstra算法对于前图中所示的有向图G8，求从顶点v1到其它各顶点的最短路径及其算法执行过程中dist数组和pre数组的变化情况如下表所示。,最短路径的Dijkstra算法举例(续),各顶点进入S中的顺序为v1，v3，v5，v4，v6；最终v2仍留在V中未进入S中，说明从v1没有路径到达v2。要求从v1到某个顶点vi的最短路径，可由prei回溯得到。 例如求v1到v6的最短路径，可由pre6=4，pre4=5，pre5=1得到最短路径为v1v5v4v6，路径长度为dist6=60。,5.5 有向网的最短路径,5.5.1 单源最短路径 5.5.2 所有顶点对之间的最短路径,所有顶点对之间的最短路径,求所有顶点对之间的最短路径的显而易见的方法是，每次以一个顶点为源点重复执行Dijkstra算法n 次来求得，总的执行时间为O(n3)。 下面介绍的是由费洛伊德（E.W.Floyd）提出的另一个算法。该算法也是用邻接矩阵a表示有向网，其时间复杂度也是O(n3)，但在形式上更简单些。,Floyd算法的基本思想,Floyd算法的基本思想是： 从邻接矩阵a开始进行n次迭代，第一次迭代后ai,j的值是从vi到vj且中间不经过编号大于1的顶点（即v2到vn）的最短路径长度；第k次迭代后ai,j的值是从vi到vj且中间不经过编号大于k的顶点（即vk+1到vn）的最短路径长度；经第n次迭代后ai,j的值就是从vi到vj的最短路径长度。其迭代公式为： aki,j=minak-1i,j，ak-1i,k+ak-1k,j 其中：1kn，迭代初值a0即为有向网的邻接矩阵。 迭代公式的意义是，如果在第k次迭代时加入顶点vk后，存在从vi到vk和从vk到vj的两条路径，且长度之和小于迭代前从vi到vj的路径长度，则更新为新路径的值，否则保留原有的值。,迭代公式直观地表示,迭代公式可以直观地表示为下图所示，图中用波浪线表示一条路径。,Floyd算法,为了实现Floyd算法，还需引入一个矩阵path。 pathi,j是从vi到vj的最短路径上vj前一个顶点的序号，并约定从vi到vj无路径时pathi,j=0。 在求得最短路径后由pathi,j的值向前追溯，可以得到从vi到vj的最短路径。,Floyd算法的形式化描述,void floyd (int a,int p,int n) /*求有向网中所有顶点对之间的最短路径*/ int i,j,k; for(i=1;i=n;i+) /*对path数组初始化，假定邻接矩阵已存入a数组中*/ for(j=1;j=n;j+) if (i=j) pathij=0; else if(aijmax) pathij=i; else pathij=0; ,Floyd算法的形式化描述(续),for(k=1;k=n;k+) /*迭代求最短路径及其长度*/ for(i=1;i=n;i+) for(j=1;j=n;j+) if(aik+akjaij) aij=aik+akj; pathij=pathkj; /*floyd*/,Floyd算法举例,Floyd算法举例(续),用Floyd算法求前图所示有向网G9中所有顶点对之间的最短路径及长度的过程如下表所示。,Floyd算法举例(续),由矩阵path可知任一顶点对之间的最短路径。 例如v1到v3的最短路径，由path1,3=1知v3的前一个顶点是v1，即只有一步v1v3，其长度为a1,3=8； 又如求v3到v2的最短路径，由path3,2=1知v2的前一个顶点是v1，由path3,1=3知v1的前一个顶点是v3，即只有两步路，v3v1v2，其长度为a3,2=3； 再如求v3到v4的最短路径，由path3,4=2知v4前一个顶点是v2，由path3,2=1知v2前一个顶点是v1，由path3,1=3知v1前一个顶点是v3，即有三步路v3v1v2v4，其长度为a3,4=10。,第5章 图与网,5.1 图与网的基本概念 5.2 图与网的存储结构 5.3 图的遍历 5.4 无向连通网的最小生成树 5.5 有向网的最短路径 5.6 有向无环图及其应用,5.6 有向无环图及其应用,5.6.1 有向无环图的概念 5.6.2 AOV网与拓扑排序 5.6.3 AOE网与关键路径,有向无环图的概念,有向无环图（directed acycline graph）是指无环的有向图，简称为DAG图，它是一类比有向树更一般的特殊有向图。 下图给出了有向树、DAG图和有向图的例子，(a)、(b)、(c)都是有向图，(a)、(b)都是DAG图，只有(a)是有向树；可以通过观察图例理解三者之间的联系与区别。,有向无环图表示举例,有向无环图是描述含有公共子式的一类表达式的有效工具。例如对于表达式 (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 可以用第四章讨论的二叉树表示为如下图所示的有向树。,仔细观察表达式可以发现，表达式中含有一些相同的子表达式如(c+d)和(c+d)*e等，在二叉树中这些相同的子表达式也重复出现。,有向无环图表示举例(续),例如对于同样表达式 (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 利用有向无环图则可实现对相同子式的共享，从而节省存储空间，下图给出了该表达式的有向无环图。,判断一个图是否存在环,要检查一个有向图是否存在环，比检查一个无向图是否存在环复杂。 对于无向图来说，深度优先搜索遍历过程中若遇到回边（即指向已访问过顶点的边）则必定存在环。 对于有向图来说，深度优先搜索遍历过程中遇到的回边，有可能是指向深度优先生成森林中的另一棵生成树上顶点的弧，这种情况下不构成环； 只有这个回边是指向深度优先森林中同一棵生成树上顶点的弧，即从有向图上的某个顶点v出发遍历执行dfs(v)结束之前出现回边弧，由于u在生成树上是v的子孙，有向图必定存在包含顶点v和u的环。,有向无环图的应用,有向无环图也是描述一项工程或系统进展过程的有效工具。 除了最简单的情况之外，几乎所有的工程（project）都可分为若干个活动（activity）的子工程，而这些子工程之间通常受着一定条件的约束，其中某些子工程的开始必须在另外一些子工程的完成之后。 对整个工程和系统，人们所关心的是两个方面的问题： 一是工程能否顺利进展， 二是预期完成整个工程所必须花费的时间最短； 对应于描述工程进展过程的有向无环图而言，即为进行拓扑排序和关键路径的操作。,5.6 有向无环图及其应用,5.6.1 有向无环图的概念 5.6.2 AOV网与拓扑排序 5.6.3 AOE网与关键路径,AOV网及应用举例,如果在有向图中用顶点表示活动而用弧表示活动间的优先关系，人们称该有向图为顶点表示活动的网（activity on vertex network），简称为AOV网。 例如，软件工程专业的学生必须学习一组基础课程和专业基础课程。其中有些基础课程是独立于其它课程的，如高等数学和高级语言程序设计；有些课程必须在学完其先导课程后才能开始学习，如在学完高级语言程序设计和离散数学之后才能学习算法与数据结构。 若用顶点表示课程，用弧表示课程之间的先后修关系（即弧表示课程j的先修课程是i）。,AOV网的应用举例示图,AOV网,AOV网中的关系是顶点集合上的偏序关系。 回忆前导课程离散数学中关于偏序关系的定义，集合X上的偏序关系R是指R是自反的、反对称的和可传递的。 如上例课程之间的先后修关系满足自反性、反对称性和可传递性，课程间的先后修关系是课程集合上的偏序关系。,拓扑排序,偏序关系是集合中仅有部分成员之间可比较； 如果集合中全体成员之间都可以比较，则为全序关系，即设R是集合X上的偏序关系，如果对每个x、yX必有xRy或yRx，则称R是集合X 上的全序关系。这个全序称作拓扑有序（topological order）； 由偏序定义得到拓扑有序的操作称作拓扑排序(topological sort)。,AOV网与拓扑排序,AOV网应是有向无环图即DAG图。 这是因为工程中的各子工程（活动）先后有序不可能存在环，若存在环意味着一个子工程以自身的后续子工程的完成为开始条件的谬论，如上例软件工程专业的一组课程之间不可能存在以自身的后修课程作为前导课程的课程。 所以，对设计的工程流程图即给定的AOV网，首先要检查它是否存在环路。检查的办法是构造它的顶点的拓扑有序序列。若AOV网中所有顶点都在它的拓扑有序序列中，则该AOV网中必定不存在环。,AOV网与拓扑排序示例,如下图中的AOV网可以有如下拓扑有序序列： c1c2c3c4c5c6c7c8c9c10c11 和 c2c3c4c1c5c6c11c9c7c8c10 当然还可以构造出其它一些拓扑有序序列。,拓扑有序序列的特点,所构造出的拓扑有序序列的特点是： 在AOV网中，若顶点i领先于顶点j，则在拓扑有序序列中仍然领先； 对于网中无领先关系的顶点i和j，在拓扑有序序列中建立一个领先关系，或者i领先于j，或者j领先于i。 拓扑排序就是由AOV网中顶点集合上的偏序关系得到该集合上的一个全序关系的操作。对于任何一项工程中各个子工程（活动）的安排，必须按照其中某一个拓扑有序序列中的顺序进行安排。,AOV网进行拓扑排序的方法和步骤,对AOV网进行拓扑排序的方法和步骤如下： 从AOV网中选择一个入度为0的顶点输出它； 从网中删去该顶点和以它为尾（即从它出发）的所有弧； 重复和，直到网中不存在入度为0的顶点时止。 操作的结果有两种可能，一种是网中全部顶点均已经输出，拓扑排序完成；一种是有剩余顶点未被输出，但无入度为0的顶点，说明网中有环路。,AOV网进行拓扑排序举例,以右图的AOV网为例。 网中v1和v6入度为0，则可选其中之一如v6输出之；删除v6及弧和之后，只有v1入度为0，输出v1并删除v1和弧，；此时v3和v4入度为0，选择其一如v4输出，删除v4和弧；现在只有v3入度为0，输出v3并删除v3和弧与；对最后剩下的两个入度为0的孤立顶点v2和v5分别输出，就完成了拓扑排序。 其过程如右下图所示，得到的拓扑有序序列为v6v1v4v3v2v5。,拓扑排序算法的实现,拓扑排序算法的实现：对AOV网采用邻接表存储结构，并且在表头结点中增加一个域indegree来存放顶点的入度。选择并输出一个入度为0的顶点可通过查表头数组实现，而删除顶点和以它为尾的弧的操作用弧头顶点的入度减1来实现。 AOV网的邻接表的表示如下图所示：,拓扑排序算法的实现举例,例如，在右图的AOV网中，其中v6的入度为0，在输出v6后可将v4和v5的入度分别由2和3减为1和2。为了避免重复检测入度为0的顶点，可把所有入度为0的顶点保存于一链栈中，每当输出从栈中弹出一个，每当出现新的入度为0的顶点便压入之。其算法步骤如下： 将所有入度为0的顶点入栈； 弹出栈顶元素输出，并把各邻接顶点的入度域值减1； 将新产生的入度为0的顶点入栈； 重复、两步，直到栈空时为止。,拓扑排序算法的实现（续）,在这里栈仅起保存入度为0的顶点的作用，入度为0的顶点谁先谁后无关紧要，故也可以用链队列或数组来保存。 可借用值为0的入度域indegree存放链中的指针，把入度域为0的表头结点链接起来形成链栈。,拓扑排序算法的实现举例,对于前面所举的示例AOV网的邻接表，入度域初始状态和栈状态如右图(a)所示； 执行算法步骤后状态如右图所示，此时栈顶指针top指向顶点v6的表头结点，其indegree域值为1（即指向顶点v1的表头结点），而v1的表头结点的indegree域值为0（即为链尾结点）； 执行步骤后输出v6，并将v5和v4的表头结点的入度域减1，未产生入度为0的新顶点，步骤相当于空操作；栈顶指针top=1，如右图(c)所示； 再次执行步骤输出v1，并将v4，v3和v2的表头结点的入度域减1，产生了两个入度为0的新顶点v4和v3，执行步骤后链栈中只有这两个结点，栈顶指针top=3而v3的入度域为4指向v4，v4的入度域为0是链尾，如右图(d)所示； 其余的依此类推，分表如右图的(e)到(h)所示。,邻接表的表结点和表头结点的定义,AOV网的邻接表的表结点和表头结点的定义可形式化描述如下： typedef struct node /*表结点*/ int adjvex; struct node *next; nodetype; /*表结点类型*/ typedef struct frontnode /*表头结点*/ vertextype data; int indegree; struct node *next frontnodetype; /*邻接表结点类型*/ typedef frontnodetype adjlistmaxvernum; /*邻接表类型*/,拓扑排序算法可用C语言描述,拓扑排序算法可用C语言描述如下。函数toposort值为0时说明AOV网中存在环路，无法给出所有顶点的拓扑有序序列；否则为1时拓扑排序成功，输出AOV网中全部顶点的拓扑有序序列。 int toposort(adjlist g,int n) int i,j,k,m=0; int top=0; nodetype *p; for(i=1;i=n;i+) if(gi.indegree=0) gi.indegree=top; top=i;,拓扑排序算法可用C语言描述续,while(top!=0) /*开始拓扑排序*/ j=top; top=gtop.indegree; printf(“%dt”,gj.data); m+; p=gj.next; while(p!=NULL) /