数据结构的第八讲课件

1引言现实世界存在许多不同类型的模拟系统。例如：交通流量就是其中一个实例。顶点表示街道的十字路口，同时边表示街道本身。加权边可以用来表示车速限制或者车道数量。模型可以使用系统来确定最佳路线和可能遭受交通堵塞的街道。每一个飞机场就是一个顶点，而从一个顶点到另一个顶点的航线就是一条边。加权的边可以表示从一个机场到另一个机场飞行的费用，或者表示从一个机场到另一个机场的大概距离，这取决于模拟的内容。

由图模拟真实世界系统第八讲图和图的算法主要内容8.1图的定义8.2图的存储表示8.3图的第一个应用：拓扑排序8.4图的搜索8.5最小生成树8.6查找最短路径

5图的定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)

其中：V={vi|vi

某个数据对象}是顶点的有穷非空集合；E={(vi,vj)|vi,vj

V}或

E={<vi,vj>|vi,vj

V&&Path(vi,vj)}

是顶点之间关系的有穷集合，也叫做边(edge)集合。

Path(vi,vj)表示从vi到vj的一条单向通路,它是有方向的。0213图是由一组顶点和一组边构成的6图的定义无向图:

(vi,vj)=(vj,vi)同一条边.有向图:

<

vi,vj>::=<vj,vi>不同边vivjtailhead7图的定义vivjvi

和vj

是互为邻接顶点;(vi,vj)依附于vi

和vj

vivjvi

邻接到vj

;vj

邻接自vi

;<vi,vj>相关联于viandvj

子图G’G:

V(G’)V(G)&&E(G’)E(G)

0123子图01301230239图的定义路径的长度：从路径中第一个顶点到最后一个顶点的边的数量。

讨论的图对象的限制:

(1)自身环不讨论.(2)与两个特定顶点相关联的边不能多于一条，多重图也不讨论。0101210图的定义简单路径：

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

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

环的长度为0。在有向图中路径至少为1以便于初始定点也是结束定点。

在有向图中，边可能是相同的，但是在无向图中，边必须是不同的。11图的定义权：

某些图的边具有与它相关的数值,称之为权。这种带权图叫做网络。代价：

顶点还可以有权值，被称为代价。13图的定义vID(v)=3OD(v)=1TD(v)=4注意

图G有n个顶点和e条边,那么14图的定义路径长度：

非带权图的路径长度是指此路径上边的条数。

带权图的路径长度是指路径上各边的权之和。ABECF从A到F长度为3的路径{A,B,C,F}15图的定义连通图与连通分量：

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

在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。17图的定义有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。ABECFABECF18图的定义如果存在从任意顶点到其他任意顶点的路径，就认为无向图是连通的（connected）在有向图中，这个条件被称为是强连通（stronglyconnected）如果有向图不是强连通的，但是又认为连通了，这就被称为弱连通（weaklyconnected）

19图的定义完全图:边数最大的图02130213每组顶点之间都有边21图的定义有n个顶点，n-1条边的图必定是生成树吗？对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFEBACDFE主要内容8.1图的定义8.2图的存储表示8.3图的第一个应用：拓扑排序8.4图的搜索8.5最小生成树8.6查找最短路径

8.2图的存储表示25邻接矩阵举例0123G101230123分析1：

无向图的邻接矩阵是对称的；分析2：

顶点i

的度＝第i

行(列)中1的个数；特别：

完全图的邻接矩阵中，对角元素为0，其余全1。26邻接矩阵举例012G2012012注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第j列含义：以结点vj为头的弧(即入度边）。29顶点的表示要开始构造Graph类的第一步是构造存储图内顶点的Vertex类。这个类与LinkedList类和BinarySearchTree类中的Node类具有相同的功效。Vertex类需要两个数据成员：一个用来识别顶点数据一个布尔型成员则用来跟踪顶点的“访问”30顶点的表示这两种数据成员分别命名为LabelwasVisited此类需要的唯一方法就是允许设置数据成员label和wasVisited的构造器方法。在这个实现中将不使用默认的构造器，这是因为每次开始引用顶点对象时都会进行一次实例化操作。顶点列表会存储在数组内，而且在Graph类中会通过它们在数组内的位置对其进行引用。31边的表示边描述了图的结构，所以关于图的真实信息是存储在边内的。选择用来表示图中边的方法称为是邻接矩阵。邻接矩阵是一个二维数组，数组内的元素表示了两个顶点之间是否存在边。把顶点作为矩阵内行和列的标头罗列出来。如果在两个顶点之间存在一条边，那么就把1放在这个位置上。如果边不存在，那么就赋值为0。很显然这里也可以使用布尔型的数值。32图的构造有了表示顶点和边的方法，接下来就准备构造图了。首先，需要建立一个图中顶点的列表。最后，需要添加连接顶点的边。33Graph类的初步定义构造器方法重新构建了顶点数组和在常量NUM-VERTICES中指定数值的邻接矩阵。既然数组是基于零的，所以数据成员numVerts存储着顶点列表内当前的数量以便于把列表初始设置为0。AddVertex方法会为顶点标签取走一个字符串参数，实例化一个新的Vertex对象，并且把它添加到顶点数组内。AddEdge方法则会取走两个整型值参数。这些整数表示顶点，并且说明在它们之间存在一条边。showVertex方法会显示出指定顶点的标签。34邻接表(AdjacencyList)邻接表:是图的一种链式存储结构。边的结点结构

adjvex;//该边所指向的顶点的位置

nextarc;//指向下一条边指针

info;//该边相关信息的指针35邻接表(AdjacencyList)顶点的结点结构data;//顶点信息firstarc;//指向第一条依附该顶点的边adjvexnextarcinfodatafirstarc36无向图的邻接表

同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边(边结点),结点中有另一顶点的下标dest和指针link。ABCDdataadjABCD0123destlink32destlink101037有向图的邻接表和逆邻接表ABC邻接表(出边表)逆邻接表(入边表)dataadjABC012destlinkdestlink102dataadjABC012destlink01138网络(带权图)的邻接表BACD69528dataadjABCD0123destcostlink1

53

62

83

21

9(出边表)(顶点表)39邻接表存储法的特点它其实是对邻接矩阵法的一种改进分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(e<<n2)，则比邻接矩阵表示法O(n2)省空间。分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。40邻接表度的计算怎样计算无向图顶点的度？TD(Vi)=单链表中链接的结点个数怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点Vi的度：OD(Vi)＝单链出边表中链接的结点数ID(Vi)＝邻接点为Vi的边个数TD(Vi)=OD(Vi)+ID(Vi)41邻接表的优缺点邻接表的缺点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。42邻接表与邻接矩阵有什么异同之处1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：

①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；邻接表多用于稀疏图的存储（e<<n2)主要内容8.1图的定义8.2图的存储表示8.3图的第一个应用：拓扑排序8.4图的搜索8.5最小生成树8.6查找最短路径

8.3图的第一个应用：拓扑排序45活动网络(ActivityNetwork)计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。用顶点表示活动的网络(AOV网络)46举例

C1

高等数学

C2

程序设计基础

C3

离散数学C1,C2

C4

数据结构C3,C2C5

高级语言程序设计C2C6

编译方法C5,C4C7

操作系统C4,C9C8

普通物理C1C9

计算机原理C8

课程代号课程名称先修课程47建图学生课程学习工程图C8C3C5C4C9C6C7C1C248AOV网络用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络

(ActivityOnVertices)。在AOV网络中不能出现有向回路,即有向环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。对给定的AOV网络，必须先判断它是否存在有向环。49拓扑排序检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则该网络中必定不会出现有向环。50拓扑排序如果AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。例如,对学生选课工程图进行拓扑排序,得到的拓扑有序序列为

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

或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C251拓扑排序的方法①

输入AOV网络。令n为顶点个数。 ②在AOV网络中选一个没有直接前驱的顶点,并输出之;③从图中删去该顶点,同时删去所有它发出的有向边;④重复以上②、③步,直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点,但已跳出处理循环。说明图中还剩下一些顶点,它们都有直接前驱。这时网络中必存在有向环。52C0C1C2C3C4C5(a)有向无环图C2C5C1C0C3(b)输出顶点C4C4C1C2C5C3(c)输出顶点C0C0C2C5C1C3(d)输出顶点C3拓扑排序的过程53C1C2C5(e)输出顶点C2C5C1(f)输出顶点C1C5(g)输出顶点C5

最后得到的拓扑有序序列为C4,C0,C3,C2,C1,C5

。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。(h)拓扑排序完成拓扑排序的过程54C0C1C2C3C4C5

C0C1C2C30C4C50012345countdataadj

130103

1

destlink

30

5

1

50

0

1

50AOV网络及其邻接表表示55拓扑排序算法使用一个存放入度为零的顶点的链式栈,供选择和输出无前驱的顶点。拓扑排序算法可描述如下：建立入度为零的顶点栈;当入度为零的顶点栈不空时,重复执行

从顶点栈中退出一个顶点,并输出之;

从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;

如果边的终顶点入度减至0,则该顶点进入度为零的顶点栈;

如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。56拓扑排序算法1.找到一个没有后继顶点的顶点。2.把此顶点添加到顶点列表内。3.从图中移除掉此顶点。4.重复步骤1直到把所有顶点从图中移除掉。在实现的细节上存在挑战，但这正是拓扑排序的关键所在。57拓扑排序算法的实现拓扑排序需要两个方法。一个方法用来确定顶点是否有后继顶点另一方法则是把顶点从图中删除下面先来看看确定没有后继顶点的方法。在邻接矩阵中可以找到没有后继的顶点，这种顶点所在行对应的所有列都为零。方法会用嵌套的for循环来逐行检查每组列的内容。如果在某列发现1，就跳出内部循环，并对下一行进行检查。如果找到一行对应的所有列都为零，那么返回这个行号。如果两层循环结束且没有行号返回，那么返回-1，这表示不存在无后继的顶点。58拓扑排序算法的实现接下来需要明白如何从图中移除顶点。需要做的第一件事就是从顶点列表中移除掉该顶点。这是很容易的。然后，就需要从邻接矩阵中移除掉相应的行和列，同时还要把移除行上面的行向下移动并且把移除列右侧的列向左移动，以此来填充移除顶点留下的行和列的空白。为了实现这个操作，这里编写了名为delVertex的方法，它包括两个助手方法moveRow和moveCol

59拓扑排序算法的实现需要一个TopSort方法来控制排序的过程。

TopSort方法循环遍历图内顶点，找到一个无后继的顶点就把它删除，然后再移动到下一个顶点上。每次删除顶点时，会把它的标签压进一个栈内。栈是一种使用便利的数据结构，因为找到第一个顶点实际上就是图内的最后一个顶点（或者是最后中的一个）。当TopSort方法运行完成的时候，栈内的内容将包括压入栈底的最后一个顶点和在栈顶的图的第一个顶点。这时只需要循环遍历栈来弹出每个元素进行显示就是图的正确拓扑顺序了。主要内容8.1图的定义8.2图的存储表示8.3图的第一个应用：拓扑排序8.4图的搜索8.5最小生成树8.6查找最短路径

8.4图的搜索62引言图的搜索是在图上经常执行的一种操作，通过该操作确定从一个顶点能到达哪些顶点是。例如：人们可能需要知道在地图上哪些路可以从一个城镇到达其他城镇，或者从一个机场到其他机场可以走哪条航线。

在图上执行这些操作都用到了查找算法。图上可以执行两种基础查找：深度优先（depth-first）搜索广度优先（breadth-first）搜索深度优先搜索深度优先搜索的含义是沿着一条路径从开始顶点到达最后的顶点，然后原路返回，并且沿着下一条路径达到最后的顶点，如此继续直到走过所有路径。63深度优先搜索算法的工作过程首先，选取一个起始点，它可能是任何顶点。访问这个顶点，把它压入一个栈内，并且标记为已访问的。接着转到下一个未访问的顶点，也把它压入栈内，并且做好标记。继续这样的操作直到到达最后一个顶点为止。然后，检查栈顶的顶点是否还有其他未访问的相邻顶点。如果没有，就把它从栈内弹出，并且检查下一个顶点。如果找到一个这样的顶点，那么就开始访问相邻顶点直到没有未访问的为止，还要检查更多未访问的相邻顶点并且继续此过程。当最终到达栈内最后一个顶点并且没有相邻的未访问顶点的时候，才算完成深度优先搜索。64深度优先搜索65算法DFS输入：有向或无向图G=(V,E)输出：深度优先遍历序列Step1.predfn=0;postdfn=0;Step2.for每个顶点vV

标记v未访问

endforStep3.for每个顶点vVifv未访问thendfs(v)endfor0123456dfs(0)Tp=O(n+e)(邻接表)Tp=O(n2).(邻接矩阵)练习66对下列非连通图G进行深度优先搜索遍历，得到顶点的访问序列为：

计算机如何实现DFS67123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS结果邻接矩阵A辅助数组visited[n]起点v2→v1→v3→v5→v4→v6——开辅助数组visited[n]！例：123456101110021000103100010410000150110006000100在图的邻接表中如何进行DFS—照样借用visited[n]！v0→v1→v2→v3DFS结果00000123辅助数组visited[n]1000110011101111例：起点0123注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。DFS算法效率分析69（设图中有n个顶点，e条边）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。如果用邻接表来表示图，虽然有2e

个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。广度优先搜索广度优先搜索算法会从第一个顶点开始尝试访问所有可能在第一个顶点附近的顶点。从本质上说，这种搜索在图上的移动是逐层进行的，首先会检查与第一个顶点相邻的层，然后逐步向下检查远离初始顶点的层。70广度优先搜索算法1.找到一个与当前顶点相邻的未访问过的顶点，把它标记为已访问的，然后把它添加到队列中。

2.如果找不到一个未访问过的相邻顶点，那么从队列中移除掉一个顶点（只要队列中有顶点可以移除掉），把它作为当前顶点，然后重新开始。

3.如果由于队列为空而无法执行第二步操作，那么此算法就此结束。71广度优先搜索72算法BFS输入：有向或无向图G=(V,E)输出：广度优先遍历序列Step1.bfn=0;Step2.for每个顶点vV

标记v未访问

endforStep3.for每个顶点vVifv未访问thenbfs(v)endfor0123456bfs(0)Tp=O(n+e)(邻接表)Tp=O(n2).(邻接矩阵)计算机如何实现BFS73——除辅助数组visited[n]外，还需再开一辅助队列！邻接表例：起点辅助队列v2已访问过了BFS遍历结果入队！初始f=n-1,r=0BFS算法效率分析74DFS与BFS之比较：空间复杂度相同，都是O(n)(借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。如果使用邻接表来表示图，则BFS循环的总时间代价为

d0+d1+…+dn-1=O(e)，其中的

di是顶点

i的度。如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（

n个元素），总的时间代价为O(n2)。（设图中有n个顶点，e条边）练习75对下列连通图G进行广度优先搜索遍历，得到顶点的访问序列为：主要内容8.1图的定义8.2图的存储表示8.3图的第一个应用：拓扑排序8.4图的搜索8.5最小生成树8.6查找最短路径

8.5最小生成树最小生成树当设计网络的时候，网络节点之间的连接数量很可能会多于最小连接数量。额外的连接是一种资源浪费，应该尽可能地消除它。额外的连接也会使其他人对网络的研究和理解变得不必要的复杂。因此需要使得网络只包含对节点连接而言最小数量的必要连接。当把这种网络应用到图上的时候，这样的网络就被称为是最小生成树。

最小生成树的得名源于覆盖每个顶点（范围）所必需的最少数量的构造边，而且说它是树是因为结果图是非循环的。需要牢记一个重要的内容：一张图可能包含多个最小生成树。创建的最小生成树完全依赖于初始顶点。78最小生成树算法79画出下图的生成树02130213最小生成树80首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。即有权图目标：在网络的多个生成树中，寻找一个各边权值之和最小的生成树。构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。典型用途81欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2条线路，那么，如何选择n–1条线路，使总费用最少？数学模型：顶点———表示城市，有n个；边————表示线路，有n–1条；边的权值—表示线路的经济代价；连通网——表示n个城市间通信网。显然此连通网是一个生成树！问题抽象：n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(MinimumcostSpanningTree)如何求得最小生成树82——有多种算法，但最常用的是以下两种：最小生成树的MST性质如下：Kruskal（克鲁斯卡尔）算法Prim（普里姆）算法Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。Prime算法特点:

将顶点归并，与边数无关，适于稠密网。这两个算法，都是利用MST性质来构造最小生成树的。若U集是V的一个非空子集，若(u0,v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0,v0)必在最小生成树上。

克鲁斯卡尔（Kruskal）算法83步骤：(1)首先构造一个只有n个顶点但没有边的非连通图T={V,},

图中每个顶点自成一个连通分量。(2)当在边集

E

中选到一条具有最小权值的边时,若该边的两个顶点落在T中不同的连通分量上，则将此边加入到生成树的边集合T

中；否则将此边舍去，重新选择一条权值最小的边。(3)如此重复下去，直到所有顶点在同一个连通分量上为止。此时的T即为所求（最小生成树）。设N={V,E}是有n个顶点的连通网，Kruskal算法采用邻接表作为图的存储表示Kruskal算法84例：1465231565546362154321352461、初始连通分量：{1},{2},{3},{4},{5},{6}2、反复执行添加、放弃动作。条件：边数不等于n-1时边 动作 连通分量

(1,3)添加 {1,3},{4},{5},{6},{2}(4,6)添加 {1,3},{4,6},{2},{5}(2,5)添加 {1,3},{4,6},{2,5}(3,6)添加 {1,3,4,6},{2,5}(1,4)放弃 因构成回路

(3,4)放弃 因构成回路

(2,3)添加 {1,3,4,5,6,2}普里姆(Prim)算法普里姆算法的基本思想：从连通网络N={V,E}中的某一顶点u0出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。

如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。采用邻接矩阵作为图的存储表示。85Prim算法86例：1465231565546362364251[注]：在最小生成树的生成过程中，所选的边都是一端在V-U中，另一端在U中。50461322810251424221618原图1204613210255边(0,5,10)

加入生成树操作演示-12810lowcostcloseVertex0123456选v=5选边(0,5)00000000000000-12825-1lowcostcloseVertex01234560500000-1100000050461322810251424221618原图12选v=4选边(5,4)5046132102522边(5,4,25)

加入生成树操作演示-1282225-124lowcostcloseVertex0123