1、5.1 图的基本概念图的基本概念 图是一种重要的，比树更复杂的非线性数据结构。图是一种重要的，比树更复杂的非线性数据结构。在树中，每个结点只与上层的父结点有联系，并在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系。但在图中，可以与其下层的多个子结点有联系。但在图中，结点之间的联系是任意的，每个结点都可以与其结点之间的联系是任意的，每个结点都可以与其它的结点相联系。它的结点相联系。 图的应用极为广泛，特别是近年来发展迅速，已图的应用极为广泛，特别是近年来发展迅速，已渗入到诸如语言学、逻辑学、物理、化学、电信渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其它
2、分支中。工程、计算机、数学及其它分支中。图的定义及相关术语图的定义及相关术语(1)图的定义：图的定义：图图G由两个集合由两个集合V(G)和和E(G)所所组成组成，记作，记作G=(V,E)。其中，。其中，V(G)是图中顶是图中顶点的非空有限集合，点的非空有限集合，E(G)是图中边的有限是图中边的有限集合。集合。 (2) 有向图有向图。如果图中每条边都是顶点的有序。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的图为有向图。有向图中的边也称为弧边也称为弧，用，用尖括号尖括号括起一对顶点表示。括起一对顶点表示。有向图示例有向图
3、示例1324G1 图中所示的图中所示的G1为有向图，它由为有向图，它由V(G1)和和E(G1)组成。组成。 V(G1)= V1，V2，V3，V4 E(G1)= ， 如其中弧如其中弧，称，称V1为初始点或弧之为初始点或弧之尾，尾，V2为终端点或弧之头。为终端点或弧之头。 (3) 无向图无向图。如果图中每条边都是顶点的无。如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用序对，则称此图为无向图。无向边用圆括号圆括号括起的两个相关顶点来表示。如图所示的括起的两个相关顶点来表示。如图所示的G2为无向图。为无向图。 V(G2)= V1，V2，V3，V4 E(G2)= (V1, V2)，(V1,
4、V3)，(V3, V4)，( V4, V1) 注意，在无向图中，注意，在无向图中，(V1, V2)与与(V2, V1)表示表示同一条边。同一条边。图图3-23 无向图示例无向图示例1234G2 (4) 子图子图。设有两个图。设有两个图GA和和GB，且满足，且满足 V(GB) V(GA) E(GB) E(GA) 则称则称GB是是GA的子图。如下图所示。的子图。如下图所示。132112132132G3G3的子图 图与子图图与子图 (5) 带权图带权图。在图的边或弧上加上一个相关。在图的边或弧上加上一个相关联的数联的数(权权)，称为带权图或网。如下图所示。，称为带权图或网。如下图所示。ABECF15
5、97211132有向网有向网14235915251030无向网无向网(6)完全图完全图。假设图中有假设图中有 n 个顶点，个顶点，e 条条边，则含有边，则含有 e=n(n-1)/2 条边的无向图称条边的无向图称作作完全图完全图；含有含有 e=n(n-1) 条弧的有向图条弧的有向图称作称作有向完全图。有向完全图。(7) 稠密图与稀疏图稠密图与稀疏图。若图的边或弧的数若图的边或弧的数目接近于相应完全图的边或弧的数目，目接近于相应完全图的边或弧的数目，则称之为则称之为稠密图稠密图，否则称为，否则称为稀疏图。稀疏图。 (8) 路径路径。在一个图中，如果从顶点。在一个图中，如果从顶点V1出发，出发，沿着
6、一些边经过顶点沿着一些边经过顶点V1，V2，Vn-1到达到达顶点顶点Vn，则称顶点序列，则称顶点序列(V1，V2，Vn-1 ，Vn)为从为从V1到到Vn的一条路径。的一条路径。路径上边路径上边(弧弧)的数目称为该路径的长度的数目称为该路径的长度。例如：下图中，例如：下图中，A,B,C,F的路径长度为的路径长度为3。ABECF(9) 简单路径简单路径：序列中顶点不重复出现的路径。：序列中顶点不重复出现的路径。(10) 简单回路简单回路：序列中第一个顶点和最后一：序列中第一个顶点和最后一个顶点相同的简单路径。个顶点相同的简单路径。(11) 连通图：连通图：在无向图中，若每一对顶点之在无向图中，若每
7、一对顶点之间都有路径，则称此图为间都有路径，则称此图为连通图连通图。(12) 连通分量：连通分量：若无向图为非连通图，则图若无向图为非连通图，则图中各个极大连通子图称作此图的中各个极大连通子图称作此图的连通分量连通分量。连通图连通图BACDFEBACDFE非连通图非连通图(13) 强连通图：强连通图：在有向图中，若每一对顶点在有向图中，若每一对顶点u和和v之间都存在之间都存在v到到u及及u到到v的路径，则称此的路径，则称此图为图为强连通图强连通图。(14) 强连通分量：强连通分量：各个强连通子图称作该各个强连通子图称作该有有向图向图的的强连通分量强连通分量。强连通图强连通图ABECFABECF
8、非强连通图非强连通图(15) 邻接点邻接点。在无向图中，如果边。在无向图中，如果边 (u,v)E，则，则u和和v互为邻结点，即互为邻结点，即u是是v的邻结点，的邻结点，v也是也是u的的邻结点。邻结点。边边(v,w) 与顶点与顶点u 和和v相相关联关联。在有向图中，如果弧在有向图中，如果弧E，则，则v是是u的邻结的邻结点。称点。称u邻接到邻接到v，或顶点，或顶点v邻接自顶点邻接自顶点u。(16) 顶点的度顶点的度。在无向图中，顶点的度就是和该。在无向图中，顶点的度就是和该顶点相关联的边的数目，记为顶点相关联的边的数目，记为TD(V)。在有向图。在有向图中，以某顶点为弧头的弧的数目，称为此顶点中，
9、以某顶点为弧头的弧的数目，称为此顶点的的入度入度，记作，记作ID(V)；以某顶点为弧尾的弧的数；以某顶点为弧尾的弧的数目称为此顶点的目称为此顶点的出度出度，记作，记作OD(V)。该顶点的度。该顶点的度则是此顶点的入度与出度之和。则是此顶点的入度与出度之和。ACDFETD(B) = 3，TD(A) = 2 BABECFID(B) = 2，OD(B) = 1TD(B)=ID(B)+OD(B) =3建立和销毁图结构建立和销毁图结构插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作访问顶点访问顶点遍历图遍历图插入和删除弧插入和删除弧基本操作基本操作5.2 图的存储结构图的存储结构图的存储结构图的
10、存储结构一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示二、图的邻接表存储表示二、图的邻接表存储表示*三、有向图的十字链表存储表示三、有向图的十字链表存储表示 *四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示根据图的定义可知，一个图的逻辑结构分两部根据图的定义可知，一个图的逻辑结构分两部分，一部分是组成图的分，一部分是组成图的顶点的集合顶点的集合；另一部分；另一部分是顶点之间的联系，即是顶点之间的联系，即边或弧的集合边或弧的集合。可用一个一维数组存放图中所有顶点的信息；可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的用一个二维数组来存放
11、数据元素之间的关系的信息信息(即边或弧的集合即边或弧的集合E)。这个二维数组称之为。这个二维数组称之为邻接矩阵。邻接矩阵。邻接矩阵是表示顶点之间的邻接关系的矩阵邻接矩阵是表示顶点之间的邻接关系的矩阵。设设G =(V，E)是有是有n(n1)个顶点的图，则个顶点的图，则G的邻的邻接矩阵接矩阵A是一个是一个nn阶矩阵。阶矩阵。Aij=0 若(Vi,Vj)或E(G)1 若(Vi,Vj)或E(G)一、图的数组一、图的数组( (邻接矩阵邻接矩阵) )存储表示存储表示定义定义:矩阵的元素为矩阵的元素为BADFEC010010100011000101001001110000011100ABCDEFABCDEF
12、有向图的邻接矩阵有向图的邻接矩阵ABDCE0101000100000010010011000ABCDE 在一般情况下，我们不关心图中顶点在一般情况下，我们不关心图中顶点的情况，若将顶点编号为的情况，若将顶点编号为1Vtxnum，设弧上或边上无权值，则图的存储结构设弧上或边上无权值，则图的存储结构可以简化为用一个二维数组表示：可以简化为用一个二维数组表示： int adjmatrixVtxnumVtxnum；无向图无向图的邻接矩阵是对称的的邻接矩阵是对称的; ; 有向图有向图的邻接矩阵不一定对称。的邻接矩阵不一定对称。对于无向图，邻接矩阵第对于无向图，邻接矩阵第i行行(或第或第i列列)的元的元素
13、之和是顶点素之和是顶点Vi的度。的度。对于有向图，邻接矩阵第对于有向图，邻接矩阵第i行元素之和为顶行元素之和为顶点点Vi的出度；第的出度；第i列的元素之和为顶点列的元素之和为顶点Vi的的入度。入度。使用邻接矩阵法容易使用邻接矩阵法容易判断任意两个点的邻判断任意两个点的邻接关系。接关系。 网的邻接矩阵可定义为网的邻接矩阵可定义为ijijijW (V, V) V, VE(G)Ai, j 反之若若或或其中其中Wij是边是边(Vi, Vj)或弧或弧上的权值。上的权值。 邻接表是一种顺序分配和链式分配相结合的邻接表是一种顺序分配和链式分配相结合的存储结构存储结构。它包括两个部分：一部分是。它包括两个部分
14、：一部分是链表链表；另一部分是另一部分是向量向量。 在邻接表中，对图中每个顶点建立一个单链在邻接表中，对图中每个顶点建立一个单链表，第表，第i个单链表中的结点包含了顶点个单链表中的结点包含了顶点Vi的所的所有邻接顶点。每个结点由三个域组成：有邻接顶点。每个结点由三个域组成：adjvex、data和和nextarc，如下图所示。，如下图所示。二、图的邻接表存储表示二、图的邻接表存储表示邻接表中表结点的结点结构邻接表中表结点的结点结构顶点顶点Vi的邻接点在图中的位置的邻接点在图中的位置指向顶点指向顶点Vi的下一邻接点的指针的下一邻接点的指针adjvexdatanextarc权值权值 为便于邻接表操
15、作，在每个单链表上附设一为便于邻接表操作，在每个单链表上附设一个头结点，在头结点中有两个域：个头结点，在头结点中有两个域：vexdata和和firstarc。如下图所示。如下图所示。邻接表中头结点的结点结构邻接表中头结点的结点结构 vexdatafirstarc指向顶点指向顶点Vi的第一个邻接点的指针的第一个邻接点的指针存储存储Vi的名字或有关信息的名字或有关信息 为了利用顺序存储结构的随机访问特性，邻为了利用顺序存储结构的随机访问特性，邻接表中将每个单链表的头结点以顺序结构的形接表中将每个单链表的头结点以顺序结构的形式存储，以便能随机访问任一顶点的单链表。式存储，以便能随机访问任一顶点的单链
16、表。 邻接表的存储结构可以用邻接表的存储结构可以用C语言描述如下：语言描述如下： #define VTXUNMn /*n为图中顶点个数的最大可能值为图中顶点个数的最大可能值*/ struct arcnode int adjvex;float data;struct arcnode *nextarc; ; typedef struct arcnode ARCNODE; struct headnode int vexdata;ARCNODE *firstarc; adjlistVTXUNM;BACDFE0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3 示
17、例：无向图的邻接表示例：无向图的邻接表有向图的邻接表有向图的邻接表ABDCE在有向图的邻接表中不在有向图的邻接表中不易找到指向该顶点的弧，易找到指向该顶点的弧，即难以确定某个顶点的即难以确定某个顶点的入度。入度。1 3242 00 1 2 3 4 A B C D E1ABECD有向图的逆邻接表有向图的逆邻接表在有向图的逆邻接表在有向图的逆邻接表中，每个顶点链接的中，每个顶点链接的是指向该顶点的弧。是指向该顶点的弧。A B C D E 303120 012344 有向带权图的邻接表有向带权图的邻接表231231437ABCABC734(a)(b) 在邻接表上容易找到任一顶点的第一个邻接在邻接表上
18、容易找到任一顶点的第一个邻接点和下一个邻接点，点和下一个邻接点，但要判定任意两个顶点但要判定任意两个顶点(Vi和和Vj)之间是否有边或弧相连，则需搜索第之间是否有边或弧相连，则需搜索第i个或第个或第j个链表，因此不及邻接矩阵方便个链表，因此不及邻接矩阵方便。 对一个图来说，对一个图来说，邻接表不是惟一的邻接表不是惟一的，它取决，它取决于建立邻接表时，结点在每个单链表中的插于建立邻接表时，结点在每个单链表中的插入策略。另外，对于有向图，其邻接表中第入策略。另外，对于有向图，其邻接表中第i个单链表的结点个数就是此结点的出度；对个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第于无向图，其
19、邻接表中第i个单链表的结点个个单链表的结点个数就是此结点的度。数就是此结点的度。5.3 图的遍历图的遍历图的遍历图的遍历从图中某个顶点出发访问图中每个顶点从图中某个顶点出发访问图中每个顶点一次且仅一次的过程。一次且仅一次的过程。图的遍历算法是求解图的连通性问题、拓图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。扑排序和求关键路径等算法的基础。深度优先搜索深度优先搜索广度优先搜索广度优先搜索从图中某个顶点从图中某个顶点V0 出发，访问此顶点，出发，访问此顶点，然后然后依次从依次从V0的各个未被访问的邻接点的各个未被访问的邻接点出发深度优先搜索遍历图中的其余顶点出发深度优先搜索
20、遍历图中的其余顶点，直至图中所有和直至图中所有和V0有路径相通的顶点都有路径相通的顶点都被访问到为止。被访问到为止。一、深度优先搜索遍历图一、深度优先搜索遍历图连通图连通图的深度优先搜索遍历的深度优先搜索遍历(用栈用栈)W1、W2和和W3 均为均为 V0 的邻接点，的邻接点，SG1、SG2 和和 SG3 分别为含分别为含顶点顶点W1、W2和和W3 的的子图。子图。访问顶点访问顶点 V0 ：for (W1、W2、W3 ) 若若该邻接点该邻接点Wi未被访问过未被访问过， 则则从它出发进行深度优先搜索遍历。从它出发进行深度优先搜索遍历。V0w1SG1SG2SG3w2w3w2算法分析算法分析1. 深度
21、优先搜索遍历连通图的过程类似深度优先搜索遍历连通图的过程类似于树的先根遍历；于树的先根遍历；解决的办法：设立一个一维数组，用来解决的办法：设立一个一维数组，用来记录每个顶点是否被访问过，即记录每个顶点是否被访问过，即 “访问访问标志标志 visitedw”。2. 如何判别如何判别V0的邻接点是否被访问？的邻接点是否被访问？ 显然，这个遍历过程是个递归过程。在设计显然，这个遍历过程是个递归过程。在设计具体算法时，首先要确定图的存储结构，下具体算法时，首先要确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。面以邻接表为例，讨论深度优先搜索法。 例例 连通图连通图G的邻接表表示如下图所示，以的
22、邻接表表示如下图所示，以顶点顶点V1为始点，按深度优先搜索遍历图中所为始点，按深度优先搜索遍历图中所有顶点，写出顶点的遍历序列。有顶点，写出顶点的遍历序列。42123123124(a)(b)31451672843528563867387847856Vi5678连通图连通图G及其邻接表及其邻接表 解：解：先访问先访问V1，再访问与，再访问与V1邻接的邻接的V2，再，再访问访问V2的第一个邻接点，因的第一个邻接点，因V1已被访问过，已被访问过，则访问则访问V2的下一个邻接点的下一个邻接点V4，然后依次访，然后依次访问问V8，V5。这时，与。这时，与V5相邻接的顶点均已相邻接的顶点均已被访问，于是反
23、向回到被访问，于是反向回到V8去访问与去访问与V8相邻相邻接且尚未被访问的接且尚未被访问的V6，接着访问，接着访问V3，V7，至此，全部顶点均被访问。相应的访问序列至此，全部顶点均被访问。相应的访问序列为：为：V1V2V4V8V5V6V3V7。 下面给出下面给出dfs的递归算法。的递归算法。 #define VTXUNMn /*n为图中顶点个数的最大可能值为图中顶点个数的最大可能值*/ struct arcnode int adjvex;float data;struct arcnode *nextarc; ; typedef struct arcnode ARCNODE; struct he
24、adnode int vexdata;ARCNODE *firstarc; ; struct headnode GVTXUNM+1; int visitedVTXUNM+1; void dfs(struct headnode G,int v) ARCNODE *p;printf(%d-, Gv.vexdata);visitedv=1;p=Gv.firstarc;while (p!=NULL) /* 当邻接点存在时当邻接点存在时*/if (visitedp-adjvex=0)dfs(G,p-adjvex); p=p-nextarc; /* 找下一邻接点找下一邻接点*/ void traver(s
25、truct headnode G) int v;for(v=1;v= VTXUNM;v+)visitedv=0;for(v=1; v, Gv.vexdata);visitedv=1;rear=(rear+1)% VTXUNM;queuerear=v; /*访问过的顶点进队列访问过的顶点进队列*/while (rear!=front) front=(front+1)% VTXUNM;v=queuefront;p=Gv.firstarc;while(p!=NULL) if (visitedp-adjvex=0) printf(%d-, Gp-adjvex.vexdata);visitedp-adj
26、vex=1;rear=(rear+1)% VTXUNM;queuerear=p-adjvex; p=p-nextarc; 若此时图中尚有顶点未被访问，则另选图中一若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。直至图中所有顶点都被访问到为止。非连通图的广度优先搜索遍历需多次调用非连通图的广度优先搜索遍历需多次调用bfs算算法。每调用一次法。每调用一次bfs得到的顶点集合恰为图中一得到的顶点集合恰为图中一个连通分量的顶点集合，这些顶点集合中的顶个连通分量的顶点集合，这些顶点集合中的顶点加上
27、所有依附于这些顶点的边，便构成了非点加上所有依附于这些顶点的边，便构成了非连通图的一个连通分量。连通图的一个连通分量。非连通图的广度优先搜索遍历非连通图的广度优先搜索遍历5.4 图的应用图的应用 生成树生成树：若图是连通图，从图中的某一个顶：若图是连通图，从图中的某一个顶点出发进行遍历时，可以系统地访问图中所点出发进行遍历时，可以系统地访问图中所有顶点，此时图中所有的顶点加上遍历时经有顶点，此时图中所有的顶点加上遍历时经过的边所构成的子图，称为连通图的生成树。过的边所构成的子图，称为连通图的生成树。并且称并且称由深度优先搜索得到的生成树为深度由深度优先搜索得到的生成树为深度优先生成树；由广度优
28、先搜索得到的生成树优先生成树；由广度优先搜索得到的生成树为广度优先生成树为广度优先生成树。 例如，下面的图示分别为连通图例如，下面的图示分别为连通图G的深度优的深度优先生成树和广度优先生成树。先生成树和广度优先生成树。生成树的概念生成树的概念42123123124(a)(b)31451672843528563867387847856Vi5678连通图连通图G及其邻接表及其邻接表1423586714235867(a)(b)连通图连通图G从从V1出发的两种生成树出发的两种生成树(a) 深度优先生成树；深度优先生成树；(b) 广度优先生成树广度优先生成树 有有n个顶点的连通图，其生成树有个顶点的连通
29、图，其生成树有n1条边；条边；生成树中不含回路；生成树不是惟一的生成树中不含回路；生成树不是惟一的，因，因为起点不同，访问的路径也不同。为起点不同，访问的路径也不同。 对于非连通图，每个连通分量中的顶点集和对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森些连通分量的生成树组成非连通图的生成森林。林。 生成树可以解决一些实际问题。如要建生成树可以解决一些实际问题。如要建n个城个城市之间的通信联络网，则连通市之间的通信联络网，则连通n个城市只需个城市只需n1条线路。若以条线路。若以n个城市做图的
30、顶点，个城市做图的顶点，n1条条线路做图的边，则该图的生成树就是可行的线路做图的边，则该图的生成树就是可行的建造方案。每条线路建造需付出一定代价建造方案。每条线路建造需付出一定代价(相相当于边上的权当于边上的权)，那么对，那么对n个顶点的连通网可个顶点的连通网可以建立许多不同的生成树，每棵生成树都可以建立许多不同的生成树，每棵生成树都可以是一个通信网，我们当然希望选择一个总以是一个通信网，我们当然希望选择一个总耗费最小的生成树，即最小代价生成树。耗费最小的生成树，即最小代价生成树。 最小生成树：生成树各边上的代价之和，称最小生成树：生成树各边上的代价之和，称为生成树的代价，使代价最小的生成树，
31、称为生成树的代价，使代价最小的生成树，称为最小代价生成树，简称最小生成树。为最小代价生成树，简称最小生成树。 那么上述通信网的问题就转化为求最小生成那么上述通信网的问题就转化为求最小生成树的问题。树的问题。 例如，下图中图例如，下图中图(a)是个连通网，它的最小生是个连通网，它的最小生成树如图成树如图(b)所示。所示。125643125643(a)(b)726664775346532连通网及其最小生成树连通网及其最小生成树(a) 无向连通网；无向连通网；(b) 最小生成树最小生成树 构造最小生成树的原则：构造最小生成树的原则： (1) 尽可能选权值小的边，但不构成回路。尽可能选权值小的边，但不
32、构成回路。 (2) 在网中选在网中选n1条边以连接网中的条边以连接网中的n个顶点。个顶点。 通常求最小生成树的算法有两种：普里姆通常求最小生成树的算法有两种：普里姆(Prim)算法和克鲁斯卡尔算法和克鲁斯卡尔(Kruskal)算法。算法。两顶点之间的最短路径问题两顶点之间的最短路径问题 求从某个源点到其余各顶点的求从某个源点到其余各顶点的最短路径最短路径 每一对顶点之间的最短路径每一对顶点之间的最短路径(略略)迪杰斯特拉算法是著名的求解最迪杰斯特拉算法是著名的求解最短路径的算法。短路径的算法。 求求从源点到其余各点的最短路径从源点到其余各点的最短路径的算的算法的基本思想法的基本思想: 依最短路
33、径的长度递增的次序求得各条依最短路径的长度递增的次序求得各条路径。路径。源点源点v1其中，从源点到顶其中，从源点到顶点点v的最短路径是指的最短路径是指从源点到从源点到v的所有路的所有路径中权值之和最小径中权值之和最小的那条路径。的那条路径。v2v1 :无无v0v2:10v0 v4 v3:50v0 v4:30v0 v4 v3 v5:60v0v1v2v3v4v51006030201050510在这条路径上，在这条路径上，必定只含一条弧必定只含一条弧，并且这，并且这条弧的条弧的权值最小。权值最小。 下一条路径长度次短的路径为路径为：路径长度上第一条最短路径为路径为： 它只可能有两种情况：或者是它只可
34、能有两种情况：或者是直接从源点直接从源点到该点到该点(只含一条弧只含一条弧)； 或者是或者是从源点经过顶从源点经过顶点点v1，再到达该顶点，再到达该顶点(由两条弧组成由两条弧组成)。其余最短路径的特点：其余最短路径的特点：再下一条再下一条路径长度次短路径长度次短的路径为的路径为:可能有三种情况：或者是可能有三种情况：或者是直接从源点到该点直接从源点到该点(只含一条弧只含一条弧)； 或者是或者是从源点经过顶点从源点经过顶点v1，再到达该顶点再到达该顶点(由两条弧组成由两条弧组成)；或者是从源；或者是从源点经过顶点点经过顶点v2，再到达该顶点。，再到达该顶点。或者是或者是直接从源点到该点直接从源点到该点(只含一条弧只含一条弧)； 或者是或者是从源点经过已求得最短路径的顶点，从源点经过已求得最短路径的顶点，再到达该顶点再到达该顶点。习习 题题 P122 一一(114)、二、二(111)、三、三(15)
