数据结构图教学课件

图：要求图的基本概念图的存储邻接矩阵、邻接表，邻接多重表，十字链表，边表）图的遍历（深度优先遍历和广度优先遍历）最小生成树构造拓扑排序和关键路径拓扑排序算法实现关键路径的求解步骤最短路径Dijkstra算法求一个顶点到其他各顶点的最短路径Floyd算法：用来求各顶点之间的最短路径，时间复杂度为O(n3)1第一部分图的定义和术语2通常：用

|V|表示顶点的数量（|V|≥1），用

|E|表示边的数量（|E|≥0）。3/15“图”

G可以表示为两个集合：G=（V,E）。每条边是一个顶点对（v,w）E，并且v,wV。图的定义无向图（完全有向图边数与顶点数之间的关系）有向图（完全有向图弧数与顶点数之间的关系）简单图：没有重边和自回路的图邻接路径，路径长度无环（有向）图：没有任何回路的（有向）图度，入度，出度无向图的顶点连通、连通图、连通分量有向图的顶点强连通，强连通图、连通分量3

图的邻接矩阵表示示例[例6.9]带权图的邻接矩阵表示示例12/15带权图的邻接矩阵的定义5邻接表(AdjacencyList)对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表表头放到一个数组中，就构成了图的邻接表。VertexFirstEdge顶点域

边表头指针AdjVNext邻接点域

指针域14/15Vertex：数据域，存储顶点信息；FirstEdge：指针域，指向链表中的第一个结点（即该顶点的第一个邻接点）。AdjV:

邻接点域，指示与顶点Vi邻接的顶点在顶点表中的下标；Next：链域，指向下一个与顶点Vi邻接的结点。6邻接表(AdjacencyList)

无向图的邻接表表示示例3V0V3V2V114/157

对于有向图来说，邻接表有缺陷：正邻接表求顶点的出度易，但求其入度难；逆邻接表求入度易，但求出度难。是否可以将两者结合？可以，十字链表对于无向图来说，邻接表有缺陷：一条边(v,w)的两个表结点分别被选在以v和w为头结点的链表中，在涉及到边的操作会带来不便改进？邻接多重表(AdjacencyMultilist)9在某些应用中，有时主要考察图中边的权值以及所依附的两个顶点，即图的结构主要由边来表示，称为边表存储结构。边表结构采用顺序存储，用2个一维数组构成，一个存储顶点信息，一个存储边的信息。边数组的每个元素由三部分组成：边的起点下标边的终点下标边的权值边表10如图所示。无向图的边表表示v0v2v4v3v16742398顶点表v0v1v2v3v401234边表132149238243344027016116、对于下面的带权无向图，请完成下列任务：（1）写出邻接矩阵（2）画出最小生成树可以看出，如果是有向图，该图共有

4

条弧，如果是无向图，共有

2

条边。7、从邻接矩阵13第二部分图的遍历14深度优先搜索（DepthFirstSearch，简称DFS

）DFS类似于树的先序遍历；3/12算法思想设初始状态时图中的所有顶点未被访问，则：⑴

：从图中某个顶点vi出发，访问vi；然后找到vi的一个邻接顶点vi1；⑵：从vi1出发，深度优先搜索访问和vi1相邻接且未被访问的所有顶点；(3)：转⑴

，直到和vi相邻接的所有顶点都被访问为止(4)：继续选取图中未被访问顶点vj作为起始顶点，转(1)，直到图中所有顶点都被访问为止。15广度优先搜索（BreadthFirstSearch，简称BFS

）BFS类似于树的层序遍历；用一个数组用于标志已访问与否，还需要一个工作队列。CDBAHGEF【例】一个无向图的BFSE→A→F→H→B→D→G→C12586374工作队列:5/1217

算法思想设初始状态时图中的所有顶点未被访问，则：⑴从图中某个顶点vi出发，访问vi；⑵访问所有与vi相邻接且未被访问的所有顶点vi1,vi2,…,vim;⑶以vi1,vi2,…,vim的次序，以vij(1≦j≦m)依次作为vi，转⑴；⑷继续选取图中未被访问顶点vk作为起始顶点，转⑴，直到图中所有顶点都被访问为止。18

广度优先搜索算法和深度优先搜索算法在时间复杂度上是一样的：采用邻接矩阵作为存储结构遍历时，时间复杂度是O(|V|2)

。采用邻接表作为存储结构遍历时，时间复杂度为O(|V|+|E|)

。不同之处仅仅在于顶点访问次序不同。基于图的遍历可以求连通分量生成树（广度优先生成树，深度优先生成树）19第三部分最小生成树21生成树（SpanningTree）7/12CDBAHGEF由深度优先遍历DFS算法和广度优先遍历BFS算法都可以得到生成树：如图所示（当有多个未访问邻接点可选时，以字母序策略选择）生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图（少于n-1条边就不连通）一个有n个顶点的连通图的生成树有n-1条边注意：含n个顶点n-1条边的图不一定是生成树22

最小生成树（MinimumSpanningTree，简记为MST）：带权连通图中代价（生成树中所有边的权值之和）最小的生成树。构造最小生成树的算法有许多，最经典的有两种：普里姆(Prim)算法克鲁斯卡尔(Kruskal)算法普里姆(Prim)算法从连通网N=(V，E)中找最小生成树T=(U，TE)。

算法思想⑴若从顶点v0出发构造，U={v0}，TE={}；⑵先找权值最小的边(u，v)，其中u∈U且v∈V-U，并且子图不构成环，则U=U∪{v}，TE=TE∪{(u，v)}；⑶重复⑵，直到U=V为止。则TE中必有n-1条边，T=(U，TE)就是最小生成树。23克鲁斯卡尔(Kruskal)算法

算法思想

设连通网N=(V,E)，令最小生成树

初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量

在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边

依此类推，直至T中所有顶点都在同一连通分量上为止25寻找“最小生成树”的Kruskal

（克鲁斯卡尔）算法T={}(L,F,2)(H,F,3)(B,L,4)(W,H,4)(D,L,4)(X,Y,5)(H,Y,5)(Z,W,5)(Y,C,6)克鲁斯卡尔算法的基本工作有3点：1、选择一条权重最小的边；2、判定一条边的两端是否属于同一棵树；3、合并两棵树。11/1226最短路径Dijkstra算法：时间复杂度单源点最短路径O(n2)各顶点之间的时间复杂度O(n3)求解最短路径Floyd算法作用：用来求解各顶点之间的最短路径时间复杂度O(n3)29针对单源点的最短路径问题，Dijkstra提出了一种按路径长度递增次序产生最短路径的算法，即迪杰斯特拉(Dijkstra)算法。Dijkstra算法求最短路径步骤初使时令S={V0},T={其余顶点}，T中顶点对应的距离值若存在<V0,Vi>，为<V0,Vi>弧上的权值若不存在<V0,Vi>，为从T中选取一个其距离值为最小的顶点W，加入S对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值重复上述步骤，直到S中包含所有顶点，即S=V为止30例如：1．（10分）试用Dijkstra算法，求下图(2)中从V1到其余各顶点的最短路径，写出算法过程中每一步的状态。

最短路径如下：最短路径长度v1->v53v1->v5->v68v1->v5->v413v1->v5->v4->v314v1->v5->v6->v21531

过

程终点=>从v1到各终点的Distance值和最短路径Path的变化过程

=>初始(第0步)选v5(第1步)选v6(第2步)选v4(第3步)选v3(第4步)选v2(第5步)DPathDPathDPathDPathDPathDPathv216<v1,v2>16<v1,v2>15<v1,v5,v6,v2>15<v1,v5,v6,v2>15<v1,v5,v6,v2>15<v1,v5,v6,v2>v3∞∞20<v1,v5,v6,v3>14<v1,v5,v4,v3>14<v1,v5,v4,v3>v4∞13<v1,v5,v4>13<v1,v5,v4>13<v1,v5,v4>v53<v1,v5>3<v1,v5>v6∞8<v1,v5,v6>8<v1,v5,v6>说明更新到v2和v5的距离，最短距离是3，最短路径是<v1,v5>更新到v4和v6的距离，最短距离是8，最短路径是<v1,v5,v6>更新到v2和v3的距离，最短距离是13，最短路径是<v1,v5,v4>更新到v3的距离，最短距离是14，最短路径是<v1,v5,v4,v3>最短距离是15，最短路径是<v1,v5,v6,v2>结束，D中是v1到各定点的最短路径长度，path是到各定点的最短路径3212345255316534602373、按Dijkstra方法计算下列图中从顶点1到其他顶点的最短路径。按顺序写出先后计算的最短路径（包括起止点和途径各点）及该路径长度。顶点1到所有顶点的最短路径都已求出，如下：最短路径长度1->2251->2->4411->2->4->3481->2->4->3->5532．Floyd算法是用来求解(D)。

A．拓扑排序B．关键路径

C．某点到其余顶点间最短距离D．任意两点间最短距离33拓扑序列和关键路径拓扑排序写出拓扑序列（厦大：2次，南大：1次）判定是否有回路（编程：南航1次，选择题：夏大1次）关键路径关键路径定义：从源点到汇点的最长路径关键路径的求解：（南航：2次）34求一个拓扑序列简单算法：[step1]如果找得到任何一个入度为0的顶点v，则step2，否则step4；[step2]输出顶点v，并从图中删除该顶点以及与其相连的所有边；[step3]对改变后的图重复这一过程，转step1；[step4]如果已经输出全部顶点，则结束；否则该有向图不是DAG。理论依据是基于下面的结论：一个顶点数|V|>1的有向图，如果每个顶点的入度都大于0，那么它必定存在回路。11/2435例如1、（1）请至少列出下图的三种拓扑序列，请问该图存在回路吗？为什么？拓扑序列一：a，b，c，d，e，f拓扑序列二：a，b，c，d，f，e拓扑序列三：a,c，b，d，e，f拓扑序列四：a,c，b，d，f，e没有回路，因为拓扑序列能输出图中所有的顶点。2、下面哪一方法可以判断出一个有向图是否有环（回路）：（）A、深度优先遍历B、拓扑排序C、求最短路径D、求关键路径答案：B36求解关键路径找出图中各顶点的一个拓扑序列

从最后一个顶点按拓扑序列逆序求各个事件的最晚完成时间：Latest(v)

Latest(n-1)=Earliest(n-1)开始向后递推:

Latest(v)=MIN{Latest(w)-Cv,w}<v,w>∈E从第一个顶点按拓扑序列正序求各个事件的最早完成时间：Earliest(v)

从Earliest(0)=0开始向前递推:

Earliest(w)