ACM培训资料数据结构与算法课件

数据结构

(DATASTRUCTURE)计算机科学与工程系

10第七章图图的基本概念图的存储表示图的遍历与连通性最小生成树最短路径活动网络207.1

图的基本概念图的定义

图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：

Graph＝(V,E)

其中

V={x|x

某个数据对象}

是顶点的有穷非空集合；

E={(x,y)|x,y

V}

或

E={<x,y>|x,y

V&&Path(x,y)}

是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(x,y)表示从x到y的一条通路。30

邻接顶点

如果(u,v)是E(G)中的一条边，则称u与v互为邻接顶点。子图

设有两个图G＝(V,E)和G’＝(V’,E’),若V’V且E’

E,则称图G’是图G的子图。50顶点的度

一个顶点v的度是与它相关联的边的条数，记作TD(v)。顶点v的入度

是以v为终点(弧头)的有向边的条数,记作ID(v);顶点v

的出度是以v为始点(弧尾)的有向边的条数,记作OD(v)。路径

在图G＝(V,E)中,若从顶点

vi出发,沿一些边经过一些顶点

vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vi

vp1vp2...vpm

vj)

为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应是属于E的边。60路径长度非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径

若路径上各顶点v1,v2,...,vm均不互相重复,则称这样的路径为简单路径。回路

若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环。简单回路

除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路

707.2

图的存储结构1）存储特点在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表；还有一个表示各个顶点之间关系的邻接矩阵。2）邻接矩阵设图A=(V,E)是一个有n个顶点的图，则图的邻接矩阵是一个二维数组A[n][n]，定义：7.2.1

邻接矩阵(AdjacencyMatrix)表示法90100

网络的邻接矩阵1104）图的创建

思路：1307.2.2

邻接表(AdjacencyList)1)存储特点对于图G中的每个顶点vi，把所有邻接于vi的顶点vj链成一个单链表，这个单链表称为顶点vi的邻接表；将所有点的邻接表表头放到数组中，就构成了图的邻接表

140特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表例G1bdac1234acdbvexdatafirstarc

4

1^

1^^

3^adjvexnext1502）数据类型描述＃defineMaxVerNum100/*最大顶点数为100*/邻接表类型：

typedefstructArcNode{intadjvex;/*邻接点域*/InfoType*Info;/*表示边上信息的域info*/structArcNode*next;/*指向下一个邻接点的指针域*/}ArcNode;表头结点类型：

typedefstructVnode{VertexTypevertex;/*顶点域*/ArcNode*firstedge;/*边表头指针*/}Vnode,AdjList[MaxVertexNum];图的类型：

typedefstruct{AdjListvertices;/*邻接表*/intvexnum,arcnum;/*顶点数和边数*/}ALGraph;/*ALGraph是以邻接表方式存储的图类型*/1707.2.3

十字链表(OrthogonalList)

十字链表是有向图的另一种链式存储结构，它实际上是邻接表与逆邻接表的结合1)存储特点图中每一条弧有一个结点，把弧头相同的弧连在同一链表上,弧尾相同的弧也连在同一链表上。结点结构为：顶点结点为链表头结点，其结构为：1807.2.4

邻接多重表(AdjacencyMultilist)邻接多重表是无向图的另一种链式存储结构1)存储特点图中每一条边用一个边结点表示，其结构为：每个顶点用一个结点表示，其结构为：markivexilinkjvexjlinkdatafirstedge1907.3

图的遍历与连通性从图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，叫做图的遍历

(GraphTraversal)。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]，它的初始状态为0，在图的遍历过程中，一旦某一个顶点i

被访问，就立即让visited[i]

为1，防止它被多次访问。2107.3.1

深度优先搜索DFS1）基本思想：任选图中一个顶点v,访问此顶点,并作访问标记。从v出发，访问它的任一未被访问过的邻接顶点w

，作访问标记，并以w为新的出发点，继续进行深度优先搜索。当某个顶点的所有邻接顶点都被访问过后，则退回到前一次刚访问过的顶点k，从k的另一个没有被访问的邻接顶点出发进行深度优先搜索。重复上述过程,直到图中所有顶点都被访问过为止220深度优先搜索的示例例V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V3V6V7V52302）算法实现难点：如何标记已访问结点v?如何查找v的所有邻接点？解决办法：设置一个布尔向量数组visited[n]，初值为0。若序号为i的结点已被访问过，则visited[i]=1。根据图的存储方式不同，采取相应方法查找：邻接矩阵：vi

的邻接点是邻接矩阵中第i行上非0元素对应的列值，若A[i][j]<>0，则vj为vi邻接点。邻接表：是以G.vertices[i]为表头结点的单链表上的所有结点。250V1V2V4V5V3V7V6V8例1234V1V3V4V2vexdatafirstarc

2

7

8

3^^^adjvexnext5V5

6^

4

8

2^V6V7V8678

7^^^深度遍历：V1V3V7V6V2V4V8V5260广度优先搜索的示例例V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V6V7V8V5290广度优先搜索的示例遍历结果：A、B、C、D例300为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。2）算法实现开始标志数组初始化Vi=1Vi访问过BFSVi=Vi+1Vi==Vexnums结束NNYY310

BFS开始访问Vi,置标志求V邻接点WW存在吗V下一邻接点WW访问过结束NYNY初始化队列Vi入队队列空吗队头V出队访问W,置标志W入队NY320如果使用邻接表表示图，则循环的总时间代价为d1+d2+…+dn=O(e)，其中的di是顶点i的度。如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的n个元素，总的时间代价为O(n2)。3）算法分析3307.4

图的连通性与生成树7.4.1

图的连通性问题连通图与连通分量

在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量

在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。340连通图例245136强连通图356例非连通图连通分量例2451363507.4.2

最小生成树

1）图的生成树连通图G的一个子图如果是一棵包含G的所有顶点的树（所有顶点均由边连接在一起，但不存在回路,有n-1条边），则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则将出现一个回路；若去掉一条边，将会使之变成非连通图。使用不同的遍历图的方法，可以得到不同的生成树360说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树GHKI370V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8380例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林390

问题提出——要在n个城市间建立通信联络网，

顶点——

城市

权——

城市间建立通信线路所需花费代价

生成树各边的权值总和称为生成树的权。权最小的生成树称为最小生成树。2)构造最小生成树

问题分析n个城市间,最多可设置n(n-1)/2条线路n个城市间建立通信网,只需n-1条线路问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费各边权值之和）最小1654327131791812752410400最小生成树的重要性质：

设G=（V，E）是一个连通网络，U是顶点集V的一个真子集。若（u，v）是G中所有的一个顶点在U,另一个顶点不在U的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边。uvUV—U410①普里姆(Prim)算法普里姆算法的基本思想：假设图G={V,E}，所求最小生成树T=(U,TE),其中U=V,TEE

从连通网络G={V,E}中的某一顶点u0

出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。420

算法实现:(略)

算法分析：

上述算法的初始化时间是O(1)，k循环中有两个循环语句，其时间大致为：

令O(1)为某一正常数C，展开上述求和公式可知其数量级仍是n的平方。所以，整个算法的时间复杂性是O(n2)430②克鲁斯卡尔(Kruskal)

算法克鲁斯卡尔算法的基本思想：设有一个有n个顶点的连通网络G={V,E}，最初先构造一个只有n个顶点，没有边的非连通图T={V,},图中每个顶点自成一个连通分量。在E中选取一条具有最小权值的边(u,v)，若该边的两个顶点落在两个不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此上步，直到T中所有顶点在同一个连通分量上为止。440应用克鲁斯卡尔算法构造最小生成树的过程例1654326513566425165432123454507.5

有向无环图及其应用计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。7.5.1

活动网络(ActivityNetwork)

用顶点表示活动的网络(AOV网络)460

C1

高等数学C2程序设计基础C3离散数学C1,C2

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

课程代号课程名称先修课程470学生课程学习工程图480可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边<Vi,Vj>表示活动间的优先关系，Vi必须先于活动Vj

进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。在AOV网络中，如果活动Vi必须在活动Vj之前进行，则存在有向边<Vi,Vj>，AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。490检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。拓扑排序：从某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。1）拓扑排序500例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为

C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C65102）进行拓扑排序的方法

输入AOV网络，令n为顶点个数在AOV网络中选一个没有直接前驱的顶点（即此顶点入度为0）,并输出之；从图中删去该顶点,同时删去所有它发出的有向边;重复以上两步,直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。520C0C1C2C3C4C5例：拓扑排序的过程(a)有向无环图(b)输出顶点C4(c)输出顶点C0C2C5C1C0C3C4C1C2C5C3C0C2C5C1C3(d)输出顶点C3530C1C2C5(e)输出顶点C2C5C1(f)输出顶点C1C5(g)输出顶点C5(h)拓扑排序完成540AOV网络及其邻接表表示C0C1C2C3C4C5

destnext

C0C1C2C30C4C50012345countdataadj

130103

1

30

5

1

50

0

1

50在邻接表中增设了一个count域，记录各个顶点入度。入度为零的顶点即无前驱的顶点。5503）拓扑排序算法入度为0的顶点即为没有前驱的顶点。删除顶点及相应弧的操作可转换为弧头顶点入度减1。为避免重复检查入度为0的顶点，在算法中使用一个链式栈将入度为0的顶点链接在一起，供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。560算法描述使用这种栈的拓扑排序算法可以描述如下：

(1)建立入度为零的顶点栈;输出顶点计数器=0(2)当入度为零的顶点栈不空时,重复执行从栈中取出顶点元素,并输出之;计数器+1从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减1;如果边的终顶点入度减至0,则该顶点进入度为零的顶点栈;(3)如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。570分析此拓扑排序算法可知，如果AOV网络有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式栈所需要的时间是O(n)。在正常的情况下，有向图有n个顶点，每个顶点进一次栈，出一次栈，共输出n次。顶点入度减一的运算共执行了e次。所以总的时间复杂度为O(n+e)。4）算法分析5807.5.2

用边表示活动的网络(AOE网络)如果在无环的带权有向图中

用有向边表示一个工程中的活动(Activity)

用边上权值表示活动持续时间(Duration)

用顶点表示事件

(Event)

则这样的有向图叫做用边表示活动的网络，简称AOE(ActivityOnEdges)网络。AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：

(1)完成整个工程至少需要多少时间(假设没有环)?(2)为缩短完成工程所需的时间,应当加快哪些活动?590在AOE网络中,有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。1）关键路径6001324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径.

例如，下图就是一个AOE网。6102）如何求关键路径定义几个与计算关键活动有关的量：事件Vi

的最早发生时间Ve(i)是从源点V0

到顶点Vi的最长路径长度。事件Vi的最迟发生时间Vl[i]是在保证汇点Vn

在Ve[n]时刻完成的前提下，事件Vi

的允许的最迟开始时间。活动ak的最早开始时间e[k]：设活动ak在边<Vi,Vj>上，则e[k]是从源点V0到顶点Vi

的最长路径长度。因此,e[k]=Ve[i]。活动ak的最迟开始时间l[k]是在不会引起时间延误的前提下,该活动允许的最迟开始时间。

l[k]=Vl[j]-dur(<i,j>)其中,dur(<i,j>)是完成ak所需的时间。620时间余量l[k]-e[k]表示活动ak的最早开始时间和最迟开始时间的时间余量。l[k]==e[k]表示活动ak是没有时间余量的关键活动。为找出关键活动,需要求各个活动的e[k]与l[k]，以判别是否l[k]==e[k].为求得e[k]与l[k]，需要先求得从源点V0到各个顶点Vi的Ve[i]和Vl[i]。630求Ve[i]的递推公式从Ve[1]=0开始，向前递推

<Vi,Vj>S2,j=2,,n

其中S2是所有指向顶点Vi的有向边<Vj

,Vi

>的集合从Vl[n]=Ve[n]开始，反向递推

<Vi,Vj>S1,j=n-1,n-2,,1

其中S1是所有从顶点Vi

发出的有向边<Vi

,Vj

>的集合这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。640

算法分析

在拓扑排序求Ve[i]和逆拓扑有序求Vl[i]时,所需时间为O(n+e),求各个活动的e[k]和l[k]时所需时间为O(e),总共花费时间仍然是O(n+e)。6507.6

最短路径(ShortestPath)问题提出:

用带权的有向图表示一个交通运输网，图中：顶点——表示城市边——表示城市间的交通联系权——表示沿此线路运输所花的时间或费用等

问题：从某顶点出发，沿图到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径最短路径：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。问题解法单源最短路径—Dijkstra算法任意顶点对之间的最短路径—Floyd算法6607.6.1

单源最短路径问题问题的提法：

给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。6701)迪杰斯特拉(Dijkstra)算法基本思想

按路径长度递增次序产生最短路径:把V分成两组：

(1)S：已求出最短路径的顶点的集合(2)V-