数据结构 第6章 图

2023年2月5日

数据结构

2023年2月5日

线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构

2023年2月5日

第6章图6.1

图的定义和基本术语6.2

图的存储结构6.3

图的遍历6.4

图的应用教学内容

2023年2月5日

1.掌握：图的基本概念及相关术语和性质2.熟练掌握：图的邻接矩阵和邻接表两种存储表示方法3.熟练掌握：图的两种遍历方法DFS和BFS4.熟练掌握：最短路算法（Dijkstra算法）5.掌握：最小生成树的两种算法及拓扑排序算法的思想教学目标

2023年2月5日

6.1图的定义和术语图：Graph=(V,E)V：顶点(数据元素)的有穷非空集合；

E：边的有穷集合。无向图：有向图：每条边都是无方向的每条边都是有方向的

2023年2月5日

完全图：任意两个点都有一条边相连无向完全图有向完全图n(n-1)/2条边n(n-1)条边

2023年2月5日

稀疏图：有很少边或弧的图。稠密图：有较多边或弧的图。网：边/弧带权的图。邻接：有边/弧相连的两个顶点之间的关系。存在(vi,vj)，则称vi和vj互为邻接点；存在<vi,vj>，则称vi邻接到vj，vj邻接于vi

关联(依附)：边/弧与顶点之间的关系。存在(vi,vj)/<vi,vj>，则称该边/弧关联于vi和vj

2023年2月5日

顶点的度：与该顶点相关联的边的数目，记为TD(v)在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数,记作ID(v)

顶点v的出度是以v为始点的有向边的条数,记作OD(v)问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？答：是树！而且是一棵有向树！

2023年2月5日

路径：接续的边构成的顶点序列。路径长度：路径上边或弧的数目/权值之和。回路(环)：第一个顶点和最后一个顶点相同的路径。简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。

2023年2月5日

非连通图

连通图

强连通图

非强连通图

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

V1

V5

V4连通图（强连通图）在无（有）向图G=(V,{E})中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）。

2023年2月5日

(a)(b)(c)

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2子图设有两个图G=（V，{E}）、G1=（V1，{E1}），若V1V，E1E，则称G1是G的子图。

例:(b)、(c)是(a)的子图权与网图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。

2023年2月5日

连通分量（强连通分量）非连通图

V0

V2

V3

V1

V5

V4无向图G的极大连通子图称为G的连通分量。

极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。

V0

V2

V3

V1

V5

V4连通分量

2023年2月5日

有向图G的极大强连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量

V0

V1

V2

V3

V0

V2

V3

V1

2023年2月5日

极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。

生成树：包含无向图G所有顶点的极小连通子图。生成森林：对非连通图，由各个连通分量的生成树的集合。连通图G1G1的生成树

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

2023年2月5日

6.2图的存储结构邻接表邻接多重表十字链表链式存储结构：顺序存储结构：数组表示法（邻接矩阵）多重链表重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法

2023年2月5日

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图A=(V,E)有n

个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：数组（邻接矩阵）表示法

2023年2月5日

邻接矩阵：A.Edge=（v1v2

v3v4v5）v1v2v3v4v500

0

0000

0000

00000000000000分析1：无向图的邻接矩阵是对称的；分析2：顶点i

的度＝第i

行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余1。01

0

1010

1010

101110101011

1001

0

1010

1

010

1

01110101011

10顶点表：无向图的邻接矩阵表示法v1v2v3v5v4v4

2023年2月5日

分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和顶点的入度=第i列元素之和顶点的度=第i行元素之和+第i列元素之和

v1v2v3v4A邻接矩阵：A.Edge=(v1v2

v3v4)v1v2v3v400

0

000

000

0000000注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表：01

1

000

000

0

01

1

00001

1

000

000

0

01

1

000有向图的邻接矩阵表示法

2023年2月5日

定义为：A.Edge[i][j]=Wij

<vi,vj>或（vi,vj）∈VR∞

无边（弧）v1v2v3v4Nv5v65489755613邻接矩阵：∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞∞

∞

∞N.Edge=(v1v2

v3v4v5v6

)顶点表：

5

7

4

8

9

5

6

5

3

1

∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞网（即有权图）的邻接矩阵表示法

2023年2月5日

优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。缺点：n个顶点需要n*n个单元存储边;空间效率为O(n2)。对稀疏图而言尤其浪费空间。邻接矩阵表示法的特点

2023年2月5日

//用两个数组分别存储顶点表和邻接矩阵#defineMaxInt32767 //表示极大值，即∞#defineMVNum100 //最大顶点数typedefcharVerTexType; //假设顶点的数据类型为字符型typedef

int

ArcType; //假设边的权值类型为整型typedef

struct{

VerTexType

vexs[MVNum]; //顶点表

ArcType

arcs[MVNum][MVNum]; //邻接矩阵

int

vexnum,arcnum; //图的当前点数和边数}AMGraph;邻接矩阵的存储表示

2023年2月5日

（1）输入总顶点数和总边数。（2）依次输入点的信息存入顶点表中。（3）初始化邻接矩阵，使每个权值初始化为极大值。（4）构造邻接矩阵。

【算法思想】采用邻接矩阵表示法创建无向网

2023年2月5日

StatusCreateUDN(AMGraph&G){//采用邻接矩阵表示法，创建无向网G

cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数

for(i=0;i<G.vexnum;++i)

cin>>G.vexs[i]; //依次输入点的信息

for(i=0;i<G.vexnum;++i) //初始化邻接矩阵，边的权值均置为极大值for(j=0;j<G.vexnum;++j)

G.arcs[i][j]=MaxInt;

for(k=0;k<G.arcnum;++k){//构造邻接矩阵

cin>>v1>>v2>>w;

//输入一条边依附的顶点及权值

i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中的位置G.arcs[i][j]=w;

//边<v1,v2>的权值置为w

G.arcs[j][i]=G.arcs[i][j];

//置<v1,v2>的对称边<v2,v1>的权值为w}//forreturnOK;}//CreateUDN

【算法描述】

2023年2月5日

int

LocateVex(MGraph

G,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/

inti;

for(i=0;i<G.vexnum;++i)

if(u==G.vexs[i])returni;return-1;}

2023年2月5日

对每个顶点vi建立一个单链表，把与vi有关联的边的信息链接起来，每个结点设为3个域；每个单链表有一个头结点（设为2个域），存vi信息；adjvexnextarcinfodatafirstarc表结点头结点邻接点域，表示vi一个邻接点的位置链域，指向vi下一个边或弧的结点数据域，与边有关信息（如权值）数据域，存储顶点vi

信息链域，指向单链表的第一个结点

每个单链表的头结点另外用顺序存储结构存储。邻接表（链式）表示法

2023年2月5日

01234^1334^142^0注：邻接表不唯一，因各个边结点的链入顺序是任意的v1v2v3v4v523^142^0无向图的邻接表表示空间效率为O(n+2e)。若是稀疏图(e<<n2)，比邻接矩阵表示法O(n2)省空间。TD(Vi)=单链表中链接的结点个数v1v2v3v5v4v4

2023年2月5日

v1v2v3v4V4V3^V2V12^3^0^1邻接表(出边)V4V3V2V1^3^0^2^0逆邻接表(入边)有向图的邻接表表示空间效率为O(n+e)出度入度度：OD(Vi)＝单链出边表中链接的结点数ID(Vi)＝邻接点域为Vi的弧个数TD(Vi)=OD(Vi)+ID(Vi)

2023年2月5日

8064125当邻接表的存储结构形成后，图便唯一确定！已知某网的邻接（出边）表，请画出该网络。

2023年2月5日

#defineMVNum100 //最大顶点数typedef

struct

ArcNode{ //边结点

int

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

struct

ArcNode*nextarc;

//指向下一条边的指针

OtherInfoinfo; //和边相关的信息}ArcNode;typedef

struct

VNode{

VerTexTypedata; //顶点信息

ArcNode*firstarc; //指向第一条依附该顶点的边的指针}VNode,AdjList[MVNum]; //AdjList表示邻接表类型typedef

struct{

AdjListvertices; //邻接表

int

vexnum,arcnum; //图的当前顶点数和边数}ALGraph;邻接表的存储表示

2023年2月5日

（1）输入总顶点数和总边数。（2）依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL。（3）创建邻接表。【算法思想】采用邻接表表示法创建无向网

2023年2月5日

StatusCreateUDG(ALGraph&G){

//采用邻接表表示法，创建无向图G

cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数

for(i=0;i<G.vexnum;++i){ //输入各点，构造表头结点表

cin>>G.vertices[i].data; //输入顶点值

G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL}//for

for(k=0;k<G.arcnum;++k){ //输入各边，构造邻接表

cin>>v1>>v2; //输入一条边依附的两个顶点

i=LocateVex(G,v1);j=LocateVex(G,v2);p1=newArcNode; //生成一个新的边结点*p1

p1->adjvex=j; //邻接点序号为j

p1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;//将新结点*p1插入顶点vi的边表头部

p2=newArcNode;//生成另一个对称的新的边结点*p2

p2->adjvex=i; //邻接点序号为i

p2->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p2;//将新结点*p2插入顶点vj的边表头部

}//forreturnOK;}//CreateUDG

【算法描述】

2023年2月5日

优点：空间效率高，容易寻找顶点的邻接点；缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。邻接表表示法的特点

2023年2月5日

v1v2v3v5v4v443210^1334^142^0v5v4v3v2v123^142^0（v1v2

v3v4v5）v1v2v3v4v500

0

0000

0000

0000000000000001

0

1010

1010

101110101011

1001

0

1010

1

010

1

01110101011

10邻接矩阵与邻接表表示法的关系1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。

2023年2月5日

2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。②邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图邻接矩阵与邻接表表示法的关系

2023年2月5日

遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。6.3图的遍历

2023年2月5日

图常用的遍历：深度优先搜索广度优先搜索解决思路：设置辅助数组

visited[n]，用来标记每个被访问过的顶点。初始状态为0i

被访问，改visited[i]为1，防止被多次访问怎样避免重复访问？

2023年2月5日

基本思想：——仿树的先序遍历过程。v1v1v2v3v8v7v6v4v5DFS结果→→→→→→→v2v4v8v5v3v6v7起点深度优先搜索(DFS－Depth_FirstSearch)

2023年2月5日

深度优先搜索的步骤简单归纳：访问起始点v;若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。

2023年2月5日

深度优先搜索的步骤详细归纳：在访问图中某一起始顶点

v

后，由

v出发，访问它的任一邻接顶点

w1；再从

w1出发，访问与

w1邻接但还未被访问过的顶点

w2；然后再从

w2出发，进行类似的访问，…

如此进行下去，直至到达所有的邻接顶点都被访问过的顶点

u为止。起点

2023年2月5日

深度优先搜索的步骤详细归纳：接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。

如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；

如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。起点v2→v1→v3→v5→v4→v6

2023年2月5日

讨论1：计算机如何实现DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS结果邻接矩阵A辅助数组visited[n]起点v2→v1→v3→v5→v4→v6——开辅助数组

visited[n]！123456101110021000103100010410000150110006000100

2023年2月5日

voidDFS(AMGraphG,intv){ //图G为邻接矩阵类型

cout<<v;visited[v]=true; //访问第v个顶点

for(w=0;w<G.vexnum;w++) //依次检查邻接矩阵v所在的行

if((G.arcs[v][w]!=0)&&(!visited[w]))DFS(G,w);//w是v的邻接点，如果w未访问，则递归调用DFS}讨论2：DFS算法如何编程？——可以用递归算法！

2023年2月5日

讨论3：在图的邻接表中如何进行DFS？v0→v1→v2→v3DFS结果00000123辅助数组visited[n]1000110011101111—照样借用visited[n]！起点0123

2023年2月5日

讨论4：邻接表的DFS算法如何编程？voidDFS(ALGraphG,intv){ //图G为邻接表类型

cout<<v;visited[v]=true; //访问第v个顶点

p=G.vertices[v].firstarc;//p指向v的边链表的第一个边结点while(p!=NULL){ //边结点非空

w=p->adjvex; //表示w是v的邻接点

if(!visited[w])DFS(G,w); //如果w未访问，则递归调用DFSp=p->nextarc; //p指向下一个边结点

}}——仍可用递归算法

2023年2月5日

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。用邻接表来表示图，虽然有2e

个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。DFS算法效率分析

2023年2月5日

基本思想：——仿树的层次遍历过程广度优先搜索(BFS－Breadth_FirstSearch)v1v1v2v3v8v7v6v4v5BFS结果→→→→v2v3→v4v5→v6v7→v8起点

2023年2月5日

简单归纳：在访问了起始点v之后，依次访问v的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。广度优先搜索的步骤

2023年2月5日

讨论1：计算机如何实现BFS？邻接表—除辅助数组visited[n]外，还需再开一辅助队列起点辅助队列v2已访问过了BFS遍历结果入队！初始f=n-1,r=0

2023年2月5日

（1）从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v进队。（2）只要队列不空，则重复下述处理。①队头顶点u出队。②依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w，并置visited[w]的值为true，然后将w进队。【算法思想】

2023年2月5日

voidBFS(GraphG,intv){//按广度优先非递归遍历连通图G

cout<<v;visited[v]=true; //访问第v个顶点

InitQueue(Q); //辅助队列Q初始化，置空

EnQueue(Q,v); //v进队

while(!QueueEmpty(Q)){ //队列非空

DeQueue(Q,u); //队头元素出队并置为u

for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))

if(!visited[w]){ //w为u的尚未访问的邻接顶点

cout<<w;visited[w]=true; EnQueue(Q,w);//w进队

}//if}//while}//BFS

【算法描述】

2023年2月5日

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

n个元素），总的时间代价为O(n2)。用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。BFS算法效率分析

2023年2月5日

空间复杂度相同，都是O(n)(借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。DFS与BFS算法效率比较

2023年2月5日

最小生成树最短路径拓扑排序关键路径6.4图的应用

2023年2月5日

极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。生成树：包含图G所有顶点的极小连通子图（n-1条边）。G1的生成树连通图G1

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2最小生成树

2023年2月5日

DFS生成树邻接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成树v0v1v3v2v4无向连通图画出下图的生成树v0v1v2v4v4v3

2023年2月5日

求最小生成树首先明确：使用不同的遍历图的方法，可以得到不同的生成树从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。目标：在网的多个生成树中，寻找一个各边权值之和最小的生成树

2023年2月5日

必须只使用该网中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点不能使用产生回路的边构造最小生成树的准则

2023年2月5日

欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2条线路，那么，如何选择n–1条线路，使总费用最少？数学模型：顶点———表示城市，有n个；边————表示线路，有n–1条；边的权值—表示线路的经济代价；连通网——表示n个城市间通信网。显然此连通网是一个生成树！最小生成树的典型用途

2023年2月5日

Prim（普里姆）算法Kruskal（克鲁斯卡尔）算法Prime算法:

归并顶点，与边数无关，适于稠密网Kruskal算法：归并边，适于稀疏网如何求最小生成树

2023年2月5日

设连通网络N={V,E}1.从某顶点u0

出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点加入到生成树的顶点集合U中2.每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到U中3.直到所有顶点都加入到生成树顶点集合U中为止普里姆算法的基本思想－－归并顶点

2023年2月5日

应用普里姆算法构造最小生成树的过程

2023年2月5日

设连通网络N={V,E}1.构造一个只有n个顶点，没有边的非连通图T={V,},每个顶点自成一个连通分量2.在E中选最小权值的边,若该边的两个顶点落在不同的连通分量上，则加入T中；否则舍去，重新选择3.重复下去，直到所有顶点在同一连通分量上为止克鲁斯卡尔算法的基本思想－归并边

2023年2月5日

应用克鲁斯卡尔算法构造最小生成树的过程√√√√×√×√

2023年2月5日

用有向图来描述一个工程或系统的进行过程。一个工程可以分为若干个子工程，只要完成了这些子工程（活动），就可以导致整个工程的完成。①AOV网(ActivityOnVertices)—用顶点表示活动的网络②AOE网(ActivityOnEdges)—用边表示活动的网络比如教学计划的制定哪些课程是必须先修的，哪些课程是可以并行学习的。有向无环图及其应用

2023年2月5日

C1

高等数学

C2

程序设计基础

C3

离散数学C1,C2

C4

数据结构C3,C2C5

高级语言程序设计C2C6

编译方法C5,C4C7

操作系统C4,C9C8

普通物理C1C9

计算机原理C8

课程代号课程名称先修课程

2023年2月5日

学生课程学习工程图数据结构离散数学程序设计基础对学生选课工程图进行拓扑排序，得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7

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

2023年2月5日

输入AOV网络。令n为顶点个数。 在AOV网络中选一个没有直接前驱的顶点,并输出之;

从图中删去该顶点,同时删去所有它发出的有向边;

重复以上2、3步,直到：全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或：图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。拓扑排序算法的思想－重复选择没有直接前驱的顶点

2023年2月5日

拓扑排序的过程

2023年2月5日

最后得到拓扑序列

C4,C0,C3,C2,C1,C5

。满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。

2023年2月5日

典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）最短路径

2023年2月5日

一顶点到其余各顶点两种常见的最短路径问题：一、单源最短路径—用Dijkstra（迪杰斯特拉）算法二、所有顶点间的最短路径—用Floyd（弗洛伊德）算法任意两顶点之间

2023年2月5日

目的：

设一有向图G=（V,E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。源点从F→A的路径有4条：①F→A：24②F→B→A：5＋18=23③F→B→C→A：5+7+9=21④

F→D→C→A：25+12+9=36又：从F→B的最短路径是哪条？从F→C的最短路径是哪条？单源最短路径问题（Dijkstra算法）

2023年2月5日

v0(v0,v1)10源点终点

最

短路

径路径长度(v0,v1,v2)(v0,v3,v2)(v0,v3)30

v1

v2

v3

v4100(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)例2：6001234509070讨论：计算机如何自动求出这些最短路径？(v0,v1,v2,v4)60

2023年2月5日

先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。从这些路径中找出一条长度最短的路径（v0,u）,然后对其余各条路径进行适当调整：若在图中存在弧（u,vk），且（v0,u）+（u,vk）<（v0,vk）,则以路径（v0,u,vk）代替（v0,vk）。在调整后的各条路径中，再找长度最短的路径，依此类推。Dijkstra算法的思想

2023年2月5日

①初始化：● 将源点v0加到S中，即S[v0]

=

true；● 将v0到各个终点的最短路径长度初始化为权值，即D[i]

=

G.arcs[v0][vi]，(vi∈V

−

S)；● 如果v0和顶点vi之间有弧，则将vi的前驱置为v0，即Path[i]

=

v0，否则Path[i]

=

−1。②选择下一条最短路径的终点vk，使得：

D[k]

=

Min{D[i]|vi∈V

−

S}【算法思想】

2023年2月5日

③将vk加到S中，即S[vk]

=

true。④更新从v0出发到集合V

−

S上任一顶点的最短路径的长度，同时更改vi的前驱为vk。若D[k]+G.arcs[k][i]<D[i]，则D[i]=D[k]+G.arcs[k][i];Path[i]=k;。⑤重复②～④

n

−

1次，即可按照路径长度的递增顺序，逐个求得从v0到图上其余各顶点的最短路径。【算法思想】

2023年2月5日

2023年2月5日

(v0,v2)+(v2,v3)<(v0,v3)终点

从v0到各终点的dist值和最短路径v1v2v3v4v5vjS之外的当前最短路径之顶点60{v0,v2,v3}50{v0,v4,v3}30{v0,v4}90{v0,v4,v5}60{v0,v4,v3,v5}5540312100603010102050s{v0,v2}{v0,v2,v4}{v0,v2,v4