数据结构（Java语言版）课件 第八章 图

数据结构（Java语言版）08图【知识目标】²

掌握图的基本概念；²

掌握图的存储结构；²

熟悉图的遍历；²

掌握生成树和最小生成树；²

理解并掌握构造最小生成树的典型算法；²

掌握最短路径的含义及算法；²

掌握拓扑排序的过程及算法；²

掌握AOE网和关键路径。【能力目标】能够进行图的遍历；能够将图构造为最小生成树；能够找出图的最短路径；能够找出图的关键路径。图是比线性表和树更复杂的数据结构。线性表的数据元素最多只有一个直接前驱和直接后继，树形结构数据元素最多只能和上层一个元素相关；图形结构中，顶点的关系是任意的，

图中任意两个顶点都可能相关。图的基本概念1．图的定义

图是由两个集合V和E组成，记作G=（V,E）V是非空的顶点集合，E是用“顶点对”表示的边的集合。顶点（或结点）：图中，数据元素vi称为顶点或结点。图的基本概念无向图：图中，如果顶点之间的连线是没有方向区分的，则称这样的边是无向边，简称边,用（vi,vj）来表示。如果某图全部是由无向边构成，则称该图为无向图。图的基本概念无向图VVVV1图的基本概念例如右图G是无向图，G=(V,E)，

其中：V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v4),(v2,v3),

(v2,v4),(v3,v5),(v4,v5)}

有向图：在一个图中，如果两个顶点之间的连线是有方向区分的，则称这样的边是有向边，简称弧。用<vi,vj>来表示。如果某图全部是由有向边构成，则称该图为有向图。V2V0V3V1有向图G2图的基本概念图的基本概念例如右图G1是有向图，G1=(V1,E1)，

其中：V1={v1,v2,v3,v4,v5}E1={<v1,v2>,<v2,v3>,<v2,v4>,

<v4,v1>,<v4,v2>,<v4,v5>,<v5,v3>}

有向完全图：在一个有向图中，对任意两个不同结点之间都有方向相反的两条弧相连。

结论：在一个含有n个顶点的有向完全图中，有n(n-1)条弧。V0V3V1证明：n个顶点中，每个顶点都有n-1条弧射向其余的n-1个顶点，所以总弧数为n(n-1)图的基本概念

无向完全图：在一个无向图中，对于任意两个不相同的顶点之间都有一条边将它们连接。结论：在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。V0V3V2V1图的基本概念顶点的度：指和该顶点相关联的边的数目，通常记为D(v)。

V2V0V3V1V0V3V2V1在有向图中，将从该顶点出发的弧的数目称为该顶点的出度，用OD(v)表示；将以该顶点结束的弧的数目称为该顶点的入度，用ID(v)表示；

有向图顶点的度为出度和入度之和：D(v)=ID(v)＋OD(v)。

图的基本概念

权：若图中的边或弧上附加有数量信息，如用于表示从一个顶点到另一个顶点的距离、耗费的代价、所需的时间、次数等，这种可反映边或弧某种特征的数据称为权。

V2V0V3V146527网络图的基本概念网络：若图的每条边(弧)都被赋予权值，代表具体的含义，称这样的图为网络。

V2V0V3V146527网络图的基本概念有向网：带权的有向图。

无向网：带权的无向图。

例如下图分别为有向网和无向网图的基本概念

路径：从一个顶点到另一个顶点所经过的节点序列。V2V0V3V146527路径上边的数目称为路径长度。如果路径的起点和终点相同则称此路径为回路。如果路径上所有顶点均不相同称为简单路径。图的基本概念

子图：设G(V,E)，G’(V’,E’)是两个图，假设V’为V的子集，且E’为E的子集，则称G’为G的子图。当满足V’=V且E’为E的子集时，称G’为G的生成子图（顶点相同，边是原图的子集）。G1的生成子图V1V0V2V3V2V1V0V2V0V3V1有向图G2无向图G1V0V3V2V1G2的子图图的基本概念连通：若从顶点vi到顶点vj（i≠j）之间有路径存在，则称该两个顶点是连通的。

连通图：对于无向图，其中任意两顶点都是连通的。

图的基本概念V2V0V3V1G3的连通分量V4V5V2V3V0V1V2V3V0V1V4V5非连通图G3

G3为非连通图，它有两个连通分量无向图中的极大连通子图称为连通分量。图的基本概念在有向图中，若任意两个顶点vi和vj都连通，则称该有向图为强连通图。有向图的极大强连通子图称为强连通分量。V0V1V3V2G4的两个强连通分量V1V0非强连通图G4V2V3V4V48.2图的存储表示图的存储表示——邻接矩阵(顺序)、邻接表(链式)3V1V3V2V08.2图的存储表示

邻接矩阵用二维数组来描述图中结点之间相邻关系的存储结构称为邻接矩阵。假设无向图G＝(V，E)，其中V＝{v0,v1,…,vn-1}，用一个n×n的矩阵来表示G中各顶点相邻的关系，则矩阵的表示如下：

邻接矩阵

3V1V3V2V0无向图中存在边（v0,v1），则A[0][1]=1

A[1][0]=18.2图的存储表示有向图的邻接矩阵3V1V3V2V0有向图中:存在弧<v0,v1>，则A[0][1]=1=0100000010001010A8.2图的存储表示邻接矩阵的说明：

①无向图的邻接矩阵是一个对称矩阵,对角线上元素都为0。

②无向图邻接矩阵第i行（或第i列）中非零元素的个数表示第i个顶点的度。

③有向图邻接矩阵第i行（或第i列）中非零元素的个数表示第i个顶点的出度（或入度）。

8.2图的存储表示3V1V3V2V0

classMgragh{

int[]vexs;/*顶点信息*/

int[][]adj;/*邻接矩阵*/

intn,e;/*顶点数和边数*/

}图的邻接矩阵存储方法用一个二维数组存储顶点之间的相邻关系，再用一个一维数组存储顶点的内容，另外还需要存储图的顶点数和边(弧)数。

2．图的邻接矩阵的建立3V1V3V2V08.2图的存储表示设计一个类，使用邻接矩阵的方式，存储下图结构。主方法中实例化一个该图的对象。3V1V3V2V08.2图的存储表示classgraph{String[]vexs;int[][]adj;intn,e;publicmar(String[]v,int[][]a,intn1,inte1){vexs=v;adj=a;n=n1;e=e1;}}

3V1V3V2V0

publicstaticvoidmain(String[]args){String[]s={"V0","V1","V2","V3"};int[][]n={{0,1,0,1},{1,0,0,1},{0,0,0,1},{1,0,0,0}};graphg=newgraph(s,n,4,4);}3V1V3V2V08.2图的存储表示邻接表是图的一种链式存储结构：对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。

V0V1V2V30321032∧3∧113∧0∧3V1V3V2V0无向图邻接表邻接表有向图的邻接表，反映的是顶点的出度邻接情况。V2V0V3V1V0V1V2V303∧1∧0123∧∧有向图邻接表邻接表图的遍历——从图中的某个顶点出发，对图中所有顶点访问且只访问一次的过程。

8.3图的遍历

V6

无向图V7V3V4V5V1V2V0图的遍历有深度优先遍历和广度优先遍历两种方式。图的遍历

1、从图中某个顶点V0出发，并访问此顶点；

2、访问与V0邻接的顶点V1后，再从V1出发，访问与V1邻接且未被访问过的顶点V2。如果当前结点的邻接点都访问过，返回其前驱结点，重复上述过程，直到不存在未访问过的邻接点为止。

3、如果是连通图，从任一顶点V0出发，可以遍历所有顶点；如果是非连通图，则再选择一个未被访问过的顶点作为出发点，重复step1、step2，直到全部顶点都被访问。深度优先遍历V6

无向图V7V3V4V5V1V2V0深度优先遍历过程：(1)从顶点v0出发进行遍历，在访问了顶点v0之后，选择其邻接点之一v1访问。(2)从v1出发进行遍历。可选择点有v6或v0，由于v0已经被访问过，因此选择v6。

(3)从v6出发进行遍历。可选择点有v1和v5，由于v1已被访问过，选择v5。深度优先遍历V6

无向图V7V3V4V5V1V2V0(4)再访问v5的邻接点v4。由于该点邻接点都被访问，退回到v5。继续后退v6，v1,v0。再访问v2v3v7最终得到的顶点访问序列为：v0→v1→v6→v5→v4→v2→v3→v7。注意：一个图的深度优先遍历序列不唯一

深度优先遍历序列为：v1→v2→v4→v8→v5→v6→v3→v7从V1出发，写出该图的深度优先遍历序列

深度优先遍历广度优先遍历过程：首先任选一顶点v为源点，访问源点v，接着依次访问v的所有邻接点w1，…，wt，然后再依次访问与wl，…，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径的顶点都已访问到为止。

广度优先遍历

若G是连通图，则遍历完成；否则，在图另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。V6

无向图V7V3V4V5V1V2V0首先访问v0

和v0的邻接点v1、v2和v5，然后依次访问v1的邻接点v6、v2邻接的点v3和v7、v5的邻接点v4。访问序列为：广度优先遍历v0→v1→v2→v5→v6→v3→v7→v4序列为：v1→v2→v3→v4→v5→v6→v7→v8从V1出发，写出该图的广度优先遍历序列

深度优先遍历

图的生成树

设G=(E，G)为连通图，遍历图G的过程所经过的边和图G中所有顶点一起构成连通图G1，称G1为原图G的一棵生成树。一个连通图的生成树有多棵，一种遍历也有多种走法。V6

无向图V7V3V4V5V1V2V0

深度优先生成树

V6V7V3V4V5V1V2V0

广度优先生成树

V6V7V3V4V5V1V2V0最小生成树

假设无向连通图是一个网络，即每条边都有一个权值，它的所有生成树中边的权值总和最小的生成树——图的最小生成树。构造最小生成树的方法:普里姆算法和克鲁斯卡尔算法8.4图的生成树

475290695458ACGBDEF55532442普里姆（Prim）算法①设置一个顶点的集合S初始状态为空；②选定图中的一个顶点V0，将V0加入到集合S中；③重复下列操作，直到所有顶点都加入到集合S中为止：选取一条权值最小的边(X,Y),其中X∈S,not(Y∈S);

将顶点Y加入集合S;④该过程得到的边的集合与所有顶点构成最小生成树

最小生成树

V0V1V2V3V4S例，从顶点A出发，普里姆算法构造最小生成树。

475290695458ACGBDEF55532442475254ACGBDEF532442475254AGBDEF5324425254ABDEF53244254ABDE5342AB53ABE5342练习：普里姆算法构造最小生成树。

52ACGBDEF2442475354克鲁斯卡尔（Kruskal）算法：从当前边中不断选取最小边，保证不产生回路直至所有顶点都在同一个连通分量中。最小生成树

克鲁斯卡尔算法（Kruskal）最小生成树475290695458ACGBDEF55532442ACGBDEF24ACGBDEF2442ACGBDEF244247ACGBDEF24424752ACGBDEF244247535252ACGBDEF2442475354鲁斯卡尔算法：从当前边中不断选取最小边，保证不产生回路直至所有顶点都在同一个连通分量中。例克鲁斯卡尔算法（Kruskal）最小生成树练习：克鲁斯卡尔算法（Kruskal）最小生成树

最短路径

求最短路径是图的一个典型应用。如果两地之间有多条通路，如何求得其中的最短路径？用带权图表示交通网，图的顶点表示城市，边（弧）表示两个城市间有通路，权值表示两地之间的距离。1006020501053010ABCDEF迪杰斯特拉(Dijkstra)算法：一源点到其它各点的最短路径。算法思想：求一个源点v0到其余顶点的最短路径，设置两个顶点集合S和T，S存放已找到最短路径的顶点，T存放未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从T中选取到源点v0路径长度最短的顶点u加入到集合S中，S每加入一个新顶点，都要修改顶点v0到集合T中剩余顶点的最短路径长度值。重复此过程，直到顶点全部加入到S中或无通路为止。迪杰斯特拉(Dijkstra)算法1006020501053010ABCDEFV0V1V2V3V4ST若源点为A，则初始状态S={A}

T＝{B，C，D，E，F}，求A到顶点B，C，D，E，F的距离，如果两点间有弧（无中转点），则距离为弧上的权值，否则为∞。

结果：{∞，10，∞，30，100}其中最短距离为到C的距离10，则S={A，C}。AC两点的最短路径为<a,c>101006020501053010ABCDEF迪杰斯特拉(Dijkstra)算法(2)S={A，C}

T＝{B，D，E，F}当S={A，C}后，点C可以作为中转点，更新A到B，D，E，F的最小距离为{∞，60，30，100}，最小值为到E的距离30，S={A，C，E},T＝{B，D，F}。AE两点的最短路径为<a,e>301006020501053010ABCDEF迪杰斯特拉(Dijkstra)算法(3)S={A，C，E}

T＝{B，D，F}当S={A，C,E}后，求A到其它顶点B，D，F的最小距离，集合S中新增加的点E可以作为中转点，更新A到B，D，F的最小距离为{∞，50（经E），90（经E）}，最小值为到D的距离50，S={A，C，D,E},T＝{B，F}，AD两点的最短路径为<a,e,d>501006020501053010ABCDEF迪杰斯特拉(Dijkstra)算法(4)S={A，C，D,E}

T＝{B，F}当S={A，C,D,E}后，更新

A到B，F的最小距离为{∞，60（经e、d）

}，最小值为到F的距离60，S={A，C，D,E,F},T＝{B}，AF两点的最短路径为<a,e,d,f>60，由于AB无通路则该过程停止。1006020501053010ABCDEF迪杰斯特拉(Dijkstra)算法1006020501053010ABCDEFA到其它点的最短路径A→B：无A→C：10A→D：50（经E）A→E

：30A→F：60（经E，D）迪杰斯特拉(Dijkstra)算法0到其它点的最短路径0→4：10路径：040→2：30路径：020→3

：60路径：0430→1

：70路径：0431迪杰斯特拉(Dijkstra)算法有向无环图的应用1-拓扑排序利用有向无环图可以用来描述一项任务或工程的进行过程.V3V2V1V0V4V5有向无环图AOV网与拓扑排序。1．AOV网(Activityonvertexnetwork)用一个有向无环图表示一项工程或任务，其中顶点表示活动(工程的子工程或子任务)，用弧表示活动之间的先后关系(前面的活动的完成是后面活动进行的前提条件。有的可同时进行有的必须有先后关系)，则这样构成的有向图称为AOV网。2．相关概念

在AOV网中，若从顶点vi到顶点vj之间存在一条有向路径，称顶点vi是顶点vj的前驱，vj是vi的后继。

把AOV网中的所有顶点排成一个线性序列，使的在此序列中前驱与后继之间的关系与AOV网中前驱与后继的关系相同，就称这个线性序列为拓扑有序序列，对AOV网构造拓扑有序序列的操作称为拓扑排序。

V3V2V1V0V4V5

注意：1AOV网中不能出现环，因为某项活动不能是自身以自身完成为先决条件。

2一个AOV网的拓扑有序序列不是唯一的(同时进行的工程在序列中没有先后)。V3V2V1V0V4V5课程代号课程名先行课程代号C0C语言程序设计无C1高等数学无C2计算方法C0，C1C3数据结构C0，C2C4数据库原理C2，C3C5C++程序设计C1，C3，C4C1C3C0C2C4C5例如：顶点表示课程的AOV网构造出的拓扑有序序列就是课程开设的先后序列C1C3C0C2C4C54．拓扑排序方法①从AOV网中选择一个没有前驱的顶点（该顶点的入度为0）并且输出它；②从网中删去该顶点，并且删去从该顶点发出的全部有向边；③重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。得到C0，C1，C2，C3，C4，C5。

C1C3C0C2C4C5C1C3C2C4C5输出C0后

C3C2C4C5输出C1后

C3C4C5输出C2后

C4C5输出C3后

写出如下AOV网的拓扑排序序列V1V2V5V3V4V6V7V9V8V10V11V1V2V3V4V5V6V7V9V8V10V11有向无环图的应用2-关键路径

AOE网（Activityonedgenetwork）

AOE网定义：AOE网是一个带权的有向无环图，其中弧表示活动，顶点表示事件(事件表示前边的活动已经完成,后边的活动可以开始)，弧上的权值表示活动持续的时间，通常，AOE网可用来估算工程完成的时间。V1表示开工,a1表示备水泥,a2表示备钢筋.a11=7a8=8a9=4a12=4a15=6a13=10a6=5a10=2a14=1a7=6a2=4a1=3a3=2a4=1a5=3V1V2V5V3V4V6V7V8V9V10V11AOE网具有以下两个性质：①只有某顶点所代表的事件发生后，从该顶点出发的各弧所代表的活动才能开始。如只有V1开工事件发生后,a1,a2表示的备料活动才能开始.

②只有在指向某顶点的所有弧所代表的活动都已经结束，该顶点所代表的事件才能发生。a11,a15表示的内部装修和终期验收活动结束后才能发生V11交工事件.a11=7a8=8a9=4a12=4a15=6a13=10a6=5a10=2a14=1a7=6a2=4a1=3a3=2a4=1a5=3V1V2V5V3V4V6V7V8V9V10V11关键路径

用AOE网表示工程活动时，由于所有的活动都要被执行但有些活动可以同时进行，所以完成工程的最短时间是从源点到终点的最大路径长度（权的和）。所以就把这条路径称为关键路径。关键路径上的活动称为关键活动。a11=7a8=8a9=4a12=4a15=6a13=10a6=5a10=2a14=1a7=6a2=4a1=3a3=2a4=1a5=3V1V2V5V3V4V6V7V8V9V10V11关键路径

分析关键路径的目的是辨别那些是关键活动，通过提高关键活动的工效来缩短工期。v3v2v1v4a1=6a3=8a4=7a2=4从v1到v4的最长路径是15，即事件v4的最早发生时间是15，活动a2的最早发生时间是6，最迟发生时间是11（V4的最早发生时间减活动a2的进行时间，15-4），这两者之差5是完成活动a2的时间余量，这意味着活动a2推迟5天开始或延迟5天完成都不影响整个工程的完成时间，可见提前完成非关键路径上的活动不能加快工程进度。关键活动

非关键活动Vn在一定范围内不直接影响工程的进度，因为其最迟开始时间与最早开始时间的差vl[n]-ve[n]>0，也就是有一定的时间余量，而关键活动直接影响工程的工期，一个关键活动延期一天，整个工程就将延期一天完成，没有任何时间余量，即对关键活动有vl[n]-ve[n]=0。所以vl[n]=ve[n]

的活动就是关键活动。v3v2v1v4a1=6a3=8a4=7a2=3关键路径的确定（1）事件的最早发生时间ve[k]

v3v2v1v4a1=6a3=8a4=7a2=3

ve[l]=0（源点最早发生时间为0）

ve[k]=Max{ve[j]+dut(<vj,vk>)}从前往后推算（2）事件的最迟发生时间vl[k]

vl[k]是指在不推迟整个工期工期的前提下，事件vk允许的最迟发生时间。

vl[n]=ve[n]（终点的最迟时间等于最早时间）

vl[k]=Min{vl[j]-dut(<vk,vj>)}(<vk,vj>∈s[k])其中，s[k]为所有以vk发出的弧的集合。v3v2v1v4a1=6a3=8a4=7a2=3从后往前推算

vl[n]=ve[n]（终点的最迟时间等于最早时间）

vl[k]=Min{vl[j]-dut(<vk,vj>)}v3v2v1v4a1=6a3=8a4=7a2=3对v1事件：为不耽误v2事件的发生,其最迟发生时间=vl[2]-6；为了不耽误v3事件发生的其最迟发生时间=vl[3]-8；取两时间中的小值才不会耽误后边的任何事件的发生。（3）活动ai的最早开始时间e[i]

活动ai由弧<vk,vj>表示，活动ai的最早开始时间应等于事件vk的最早发生时间。因此有：

e[i]=ve[k]

（4）活动的最迟开始时间l[i]

在不推迟整个工程完成日期的前提下，ai必须开始的最迟时间。

活动的最迟开始时间要保证其后边的事件的最迟发生时间不被拖后，所以

l[i]=vl[j]-dut(<vk,vj>)

v3v2v1v4a1=6a3=8a4=7a2=3求一工程的关键路径的步骤：

1从前往后求各个事件的最早发生时间ve[k]

第一个事件的最早发生时间为0

2从后往前求各个事件的最迟发生时间ve[k]

最后一个事件的最迟发生时间等于其最早发生时间

3.求各个活动的最早开始时间e[i]和最迟开始时间l[i]

4活动的最早开始时间与最迟开始时间相等的活动就为关键活动，它们构成的路径为关键路径工程应用实例

a11=7a8=8a9=4a12=4a15=6a13=10a6=5a10=2a14=1a7=6a2=4a1=3a3=2a4=1a5=3V1V2V5V3V4V6V7V8V9V10V111.求事件的最早发生时间ve[k]（从前往后推算）

ve(1)=0，ve(7)=max{ve(4)+6,ve(5)+8}=15

ve(2)=3，ve(8)=ve(5)+4=11ve(3)=4，ve(9)=max{ve(8)+10,ve(6)+2}=21ve(4)=ve(2)+2=5，ve(10)=max{ve(8)+4,ve(9)+1}=22ve(5)=max{ve(2)+1,ve(3)+3}=7ve(6)=ve(3)+5=9，ve(11)=max{ve(7)+7,ve(10)+6}=282.求事件的最迟发生时间vl[k]（从后往前推算）

vl(11)=ve(11)=28

vl(10)=vl(11)-6=22

vl(9)=vl(10)-1=21

vl(8)=min{vl(10)-4,vl(9)-10}=11

vl(7)=vl(11)-7=21

vl(6)=vl(9)-2=19

vl(5)=min{vl(7)-8,vl(8)-4}=7

vl(4)=vl(7)-6=15

vl(3)=min{vl(5)-3,vl(6)-5}=4

vl(2)=min{vl(4)-2,vl(5)-1}=6

vl(1)=min{vl(2)-3,vl(3)-4}=0a11=7a8=8a9=4a12=4a15=6a13=10a6=5a10=2a14=1a7=6a2=4a1=3a3=2a4=1a5=3V1V2V5V3V4V6V7V8V9V10V113.求出活动ai的最早开始时间e[i]和最迟开始时间l[i]。活动a1e(1)=ve(1)=0l(1)=vl(2)-3=3

活动a2e(2)=ve(1)=0l(2)=vl(3)-4=0

活动a3e(3)=ve(2)=3l(3)=vl(4)-2=13

活动a4e(4)=ve(2)=3l(4)=vl(5)-1=6

活动a5e(5)=ve(3)=4l(5)=vl(5)-3=4

活动a6e(6)=ve(3)=4l(6)=vl(6)-5=14