1、第第7章章 图图 7.1 图的定义和术语图的定义和术语 7.2 图的存储结构图的存储结构 7.3 图的遍历图的遍历 7.4 图的应用图的应用 7.1 图的定义和术语图的定义和术语l1、图、顶点、边、图、顶点、边l图图G是由集合是由集合V(G)和和E(G)组成组成,记为记为G=(V,E)，其中，其中V(G)是顶是顶点的非空有限集合，点的非空有限集合，E(G)是边的有限集合，边是顶点的无序是边的有限集合，边是顶点的无序对或有序对。对或有序对。l2、有向图、弧、无向图有向图、弧、无向图 245136G1l若图中的边是顶点的有序对，则称此图为若图中的边是顶点的有序对，则称此图为有向图。有向图。l有向边
2、又称为有向边又称为弧弧，通常用尖括号表示一条有向边，通常用尖括号表示一条有向边，表示表示从顶点从顶点v到到w顶点的一条弧，顶点的一条弧，v称为边的始点（或称为边的始点（或弧尾弧尾），），w称称为边的终点（或为边的终点（或弧头弧头）。）。例例245136G1l图图G1中：中：V(G1)=1,2,3,4,5,6lE(G1)=,例例157324G26l图图G2中：中：V(G2)=1,2,3,4,5,6,7l无向图无向图 若图中的边是顶点的无序对，则称此图为若图中的边是顶点的无序对，则称此图为无向图无向图。通。通常用园括号表示常用园括号表示无向边无向边。（v,w）或（）或（w,v)，并且（，并且（v,
3、w)=(w,v)7.1 图的定义和术语图的定义和术语lE(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)l3、有向完全图、无向完全图、有向完全图、无向完全图l4、相邻顶点、相关联弧或边、相邻顶点、相关联弧或边l无向完全图无向完全图：n个顶点的无向图最大边数是个顶点的无向图最大边数是n(n-1)/2，具有，具有n(n-1)/2条边的无向图称为无向完全图。条边的无向图称为无向完全图。213有向完全图有向完全图213无向完全图无向完全图7.1 图的定义和术语图的定义和术语l若若 E或或(V1,V2)E，则，则V1，V2是是相邻顶点相邻顶点，弧，弧或边或边(
4、V1,V2)是与顶点是与顶点V1和和V2相关联弧或边相关联弧或边。l有向完全图有向完全图：具有：具有n(n-1)条弧的有向图称为有向完全图。条弧的有向图称为有向完全图。l5、度、度 例例1245136G1l顶点顶点2入度：入度：1 出度：出度：3l顶点顶点4入度：入度：1 出度：出度：0例例2157324G26l顶点顶点5的度：的度：3l顶点顶点2的度：的度：47.1 图的定义和术语图的定义和术语l一个顶点一个顶点V的度是与该顶点相关联的边的数目，记为的度是与该顶点相关联的边的数目，记为TD（V）。）。l对于有向图，则把以顶点对于有向图，则把以顶点V为弧尾的数目称为点为弧尾的数目称为点V的出度
5、，的出度，记为记为OD（V），把以顶点），把以顶点V为头的弧的数目称为顶点为头的弧的数目称为顶点V的入的入度，记为度，记为ID（V）。）。顶点顶点V的度为：的度为：lTD（V）=ID（V）+OD（V）l6、子图、子图l设有两个图设有两个图 G(V,E)和和 G(V,E)。若。若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。7.1 图的定义和术语图的定义和术语l7、路径、路径l若一条路径上除了若一条路径上除了vi 和和vj 可以相同外，可以相同外，其余顶点均不相同，其余顶点均不相同，则称此路径为一条则称此路径为一条简单路径简单路径。7.1 图的定义和术语图的定义和术语l
6、在无向图在无向图 G(V,E)中中,若存在一个顶点序列若存在一个顶点序列 vp1,vp2,vpm，使得使得(vi,vp1)、(vp1,vp2)、.、(vpm,vj)均属于均属于E，则称顶点，则称顶点vi到到vj存在一存在一 条路径。条路径。路径长度定义为路径上边或弧的数目。路径长度定义为路径上边或弧的数目。l起点和终点相同的路径称为起点和终点相同的路径称为简单回路或简单环简单回路或简单环。例例2157324G26例例1245136G1l路径：路径：1，2，3，5，6，3l路径：路径：1，2，5，7，6，5，2，37.1 图的定义和术语图的定义和术语l路径长度：路径长度：5l简单路径：简单路径：
7、1，2，3，5l回路：回路：1，2，3，5，6，3，1l简单回路：简单回路：3，5，6，3l路径长度：路径长度：7l简单路径：简单路径：1，2，5，7，6l回路：回路：1，2，5，7，6，5，2，1l简单回路：简单回路：1，2，3，18、图的连通、图的连通 在无向图在无向图G中，若两个顶点中，若两个顶点vi和和vj之间有路径存在，之间有路径存在，则称则称vi 和和vj 是连通的。是连通的。若若G中任意两个顶点都是连通的，则称中任意两个顶点都是连通的，则称G为连通图。为连通图。连通图连通图例例245136强连通图强连通图356例例例例245136非连通图，连通分量非连通图，连通分量9、强连通图与
8、强连通分量、强连通图与强连通分量 在有向图中在有向图中,若对于每一对顶点若对于每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是则称此图是强连通图强连通图。非强连通图的极大强连通子图叫做强连通分量。非强连通图的极大强连通子图叫做强连通分量。7.1 图的定义和术语图的定义和术语l非连通图的极大连通子图叫做非连通图的极大连通子图叫做连通分量连通分量。10、带权图或网、带权图或网1235687410796671231516ABDCE60304535804075l若给图中每一条边附加一个实数作为权，则该图称若给图中每一条边附加一个实数作为权，则该图
9、称为为带权图或网。带权图或网。7.1 图的定义和术语图的定义和术语l这些权可以表示从一个顶点到另一个顶点的距离这些权可以表示从一个顶点到另一个顶点的距离或花费的代价。或花费的代价。一、图的数组一、图的数组(邻接矩阵邻接矩阵)存储表示存储表示7.2 图的存储结构图的存储结构二、图的邻接表存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示三、有向图的十字链表存储表示四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示l用数组存储数据元素（顶点）的信息和数据元素之间的关用数组存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。系（边或弧）的信息。一、数组表示法（邻接矩阵一
10、、数组表示法（邻接矩阵），其它0E(G)v,v或)v,(v若1,jijijiAl在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。表，还有一个表示各个顶点之间关系的邻接矩阵。l设图设图 A=(V,E)是一个有是一个有 n 个顶点的图，则图的邻接矩阵个顶点的图，则图的邻接矩阵定义：定义：l无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。对称的。例例G12413例例15324G20011000101110101010101010000110000
11、0000110一、数组表示法（邻接矩阵）一、数组表示法（邻接矩阵）l借助邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相借助邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相连，并容易求得各个顶点的度。连，并容易求得各个顶点的度。10)_()(njiNUMVERTEXMAXnjiAVTDl对于无向图，顶点对于无向图，顶点Vi的度是邻接矩阵中第的度是邻接矩阵中第i行（或第行（或第i列）的元列）的元素之和，即素之和，即 l对于有向图，对于有向图，第第i行的元素之和为顶点行的元素之和为顶点Vi的出度的出度OD（Vi），第），第j列的元素之和为顶点列的元素之和为顶点Vj的入度的入度ID(Vj)。一、
12、数组表示法（邻接矩阵）一、数组表示法（邻接矩阵）例例G124130001100000000110l网的邻接矩阵可定义为：网的邻接矩阵可定义为：，其它E(G)v,v或)v,(v若,jijiijwjiA例例14523753186426183624127845375一、数组表示法（邻接矩阵）一、数组表示法（邻接矩阵）二、图的邻接表存储表示二、图的邻接表存储表示q邻接表邻接表是图的一种链式存储结构。是图的一种链式存储结构。在邻接表中，在邻接表中，对图中每个顶点建立一个单链表，对图中每个顶点建立一个单链表，第第i个单链表中个单链表中的结点表示依附于顶点的结点表示依附于顶点Vi的边（对有向图中指以顶的边（
13、对有向图中指以顶点点Vi为尾的弧）。为尾的弧）。adjvex nextarc infoq每个结点有三个域组成：每个结点有三个域组成：q邻接结点域邻接结点域(adjvex)：指示与顶点：指示与顶点Vi邻接的点在图邻接的点在图中的位置。中的位置。q链域链域(nextarc)：指示下一条边或弧的结点。：指示下一条边或弧的结点。q数据域数据域(info)：存储和边相关的信息，如权值等：存储和边相关的信息，如权值等l每个链表上附设一个表头结点。在表头结点中，除了设有链域每个链表上附设一个表头结点。在表头结点中，除了设有链域(firstarc)指向链表中第一个结点之外，还设有存储顶点指向链表中第一个结点之
14、外，还设有存储顶点Vi的名的名或其它有关信息的数据域或其它有关信息的数据域(data)。头结点头结点 data firstarc二、图的邻接表存储表示二、图的邻接表存储表示例例V1V5V3V2V4G20123V1V3V4V2vexdatafirstarc 1 4 23adjvexnext4V5 3 20 4 1 0 21l若无向图中有若无向图中有n个顶点、个顶点、e条边，则它的邻接表需条边，则它的邻接表需n个头结点个头结点和和2e个表结点。个表结点。显然，在边稀疏显然，在边稀疏(en(n-1)/2)的情况下，用的情况下，用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息邻接表表示图比邻接矩
15、阵节省存储空间，当和边相关的信息较多时更是如此。较多时更是如此。二、图的邻接表存储表示二、图的邻接表存储表示例例V1V5V3V2V4G20123V1V3V4V2vexdatafirstarc 1 4 23adjvexnext4V5 3 20 4 1 0 21例例G1V2V4V1V30123V1V3V4V2vexdatafirstarc 2 1 3 0adjvexnext二、图的邻接表存储表示二、图的邻接表存储表示l在无向图的邻接表中，顶点在无向图的邻接表中，顶点vi的度恰为第的度恰为第i个链表中的结点数；个链表中的结点数；l而在有向图中，第而在有向图中，第i个链表中的结点个数只是顶点个链表中的
16、结点个数只是顶点vi的出度，的出度，为求入度，必须遍历整个邻接表。为求入度，必须遍历整个邻接表。l在所有链表中其邻接点域的值为在所有链表中其邻接点域的值为i的结点的个数是顶点的结点的个数是顶点vi的的入度。入度。ABECD二、图的邻接表存储表示二、图的邻接表存储表示l有时，为了便于确定顶点的入度或以顶点有时，为了便于确定顶点的入度或以顶点vi为头的弧，可以建为头的弧，可以建立一个有向图的逆邻接表，即对每个顶点立一个有向图的逆邻接表，即对每个顶点vi 建立一个链接以建立一个链接以vi为头的弧的链表。为头的弧的链表。l在邻接表上容易找到任一顶点的第在邻接表上容易找到任一顶点的第1个邻接点和下一个邻
17、接点，个邻接点和下一个邻接点，3 30 4 2 0 EDCBA43210l但是要判定任意两个顶点（但是要判定任意两个顶点（vi和和vj）之间是否有边或狐相连，则）之间是否有边或狐相连，则需搜索第需搜索第i个或第个或第j个链表，因此，不及邻接矩阵方便。个链表，因此，不及邻接矩阵方便。7.3 图的遍历图的遍历l从图中某一顶点出发访遍图中其余顶点，且使每一个顶点从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就叫做仅被访问一次。这一过程就叫做图的遍历图的遍历。l通常有两条遍历图的路径：通常有两条遍历图的路径：l深度优先搜索遍历深度优先搜索遍历l广度优先搜索遍历广度优先搜索遍历
18、1、深度优先搜索遍历、深度优先搜索遍历(DFS)方法方法l深度优先搜索遍历深度优先搜索遍历类似于树的先根遍历，是树的先根类似于树的先根遍历，是树的先根遍历的推广。遍历的推广。l深度优先可以从图中某个顶点深度优先可以从图中某个顶点V出发，访问此顶点，出发，访问此顶点，l若此时图中尚有顶点未被访问，则另选图中一个未曾若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直至图中所有被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。顶点都被访问为止。l然后依次从然后依次从V的未被访问的邻接点出发，深度优先遍的未被访问的邻接点出发，深度优先遍历图，直至图中所有和
19、历图，直至图中所有和V有路径的顶点都被访问到；有路径的顶点都被访问到；（1）假定从图中的某一顶点）假定从图中的某一顶点V出发进行遍历，首先访问顶出发进行遍历，首先访问顶点点V，再访问一个与，再访问一个与V相邻的顶点相邻的顶点W，接着访问一个与，接着访问一个与W相邻且未被访问的顶点。依次类推，直至某个被访问的相邻且未被访问的顶点。依次类推，直至某个被访问的顶点的所有相邻顶点均被访问过为止。顶点的所有相邻顶点均被访问过为止。（2）然后退回到尚有相邻顶点未被访问的顶点）然后退回到尚有相邻顶点未被访问的顶点R，再从顶，再从顶点点R的一个未被访问的相邻顶点出发，重复上述过程，直的一个未被访问的相邻顶点出
20、发，重复上述过程，直到图中所有和到图中所有和V有路径相通的顶点都被访问过。有路径相通的顶点都被访问过。（3）若此时图中尚有顶点未被访问，则另选图中一个未被）若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。都被访问为止。1、深度优先搜索遍历、深度优先搜索遍历(DFS)方法方法深度遍历：深度遍历：V1V2 V4 V8 V5 V3 V6 V71、深度优先搜索遍历、深度优先搜索遍历(DFS)方法方法V1V2V4V5V3V7V6V8例例12341342vexdatafirstarc 2 7 8 3
21、adjvexnext55 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V1V2V4V5V3V7V6V8例例12341342vexdatafirstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍历：深度遍历：V1V2 V4 V8 V5 V3 V6 V71、深度优先搜索遍历、深度优先搜索遍历(DFS)方法方法2、广度优先搜索遍历、广度优先搜索遍历(BFS)l方法：方法：广度优先遍历是按层次遍历的过程广度优先遍历是按层次遍历的过程。假设从图中某。假设从图中某顶点顶点V出发，访问此顶点出发，访问此顶点V后，依次访问后，依次访问V的各个未曾访问
22、的各个未曾访问过的邻接点；过的邻接点；l若此时图中尚有顶点未被访问，则另选图中一个未被访若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。被访问为止。l然后分别从这些邻接点出发依次访问它们的邻接点，并使然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点先被访问的顶点的邻接点”先于先于“后被访问的顶点的邻后被访问的顶点的邻接点接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问，直至图中所有已被访问的顶点的邻接点都被访问到；被访问到；V1V2V4V5V3V7V6V
23、8例例l广度遍历广度遍历V1V2V4V5V3V7V6V8例例V1V2 V1V3 V4 V5 V6 V7 V8l广度遍历广度遍历V2 V3 V4 V6 V7 V8 V52、广度优先搜索遍历、广度优先搜索遍历(BFS)7.4-1 最小生成树最小生成树l假设要在假设要在n个城市间建立通信联络网，自然会考虑这样一个问个城市间建立通信联络网，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通讯网？题，如何在最节省经费的前提下建立这个通讯网？l在每个城市之间都可以设置一条线路，相应地都要付出一定的经在每个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。济代价。n个城市之间，最多可能设置个
24、城市之间，最多可能设置n(n-1)/2条线路，那么，如条线路，那么，如何在这些可能的线路中选择何在这些可能的线路中选择n-1条，以使总的耗费最少呢？条，以使总的耗费最少呢？l可以用连通网来表示可以用连通网来表示n个城市以及个城市以及n个城市间可能设置的通讯线个城市间可能设置的通讯线路，其中路，其中网的网的顶点表示城市，边表示两个城市之间的线路，赋于顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价边的权值表示相应的代价。对于。对于n个顶点的连通网可以建立许多个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通讯网。不同的生成树，每一棵生成树都可以是一个通讯网。lD
25、FS生成深度优先树，生成深度优先树，BFS生成广度优先树。生成广度优先树。n个顶点，个顶点，n-1条边。条边。l现在，我们要选择这样一棵生成树，也就是使总的耗费最现在，我们要选择这样一棵生成树，也就是使总的耗费最少，这个问题就是构造连通网的少，这个问题就是构造连通网的最小代价生成树最小代价生成树（简称为最（简称为最小生成树）的问题。小生成树）的问题。l一棵生成树的代价就是树上各边的代价之和。一棵生成树的代价就是树上各边的代价之和。l构造最小生成树可以有多种方法。其中多数算法利用了最小生构造最小生成树可以有多种方法。其中多数算法利用了最小生成树的下列一种简称为成树的下列一种简称为MST的性质：的
26、性质：假设假设N=（V，E）是一个）是一个连通网，连通网，U是顶点集是顶点集V的一个非空子集。若（的一个非空子集。若（u，v）是一条具有）是一条具有最小权值（代价）的边，其中最小权值（代价）的边，其中u U，v V-U，则必存在一棵包，则必存在一棵包含边（含边（u，v）的最小生成树。）的最小生成树。l普里姆普里姆算法和克鲁斯卡尔算法是两个利用算法和克鲁斯卡尔算法是两个利用MST性质构造最小生性质构造最小生成树的算法。成树的算法。7.4 最小生成树最小生成树1、普里姆算法、普里姆算法l假设假设N=（V,E)是连通图是连通图,TE是是N上最小生成树中边的集合上最小生成树中边的集合.算法从算法从U=
27、u0(u0 V),TE=开始，重复执行下述操作开始，重复执行下述操作:l在所有在所有uU,vVU的边的边(u,v)E中中,找一条代价最小找一条代价最小的边（的边（u0,v0）并入集合）并入集合TE，同时，同时v0并入并入U中，中，l如此不断重复如此不断重复,直到直到UV为止。此时为止。此时TE必有必有n-1条边条边,则则T=（V,TE）为）为N的最小生成树。的最小生成树。l如此进行下去，每次往生成树如此进行下去，每次往生成树里加一个顶点和一条权值最小里加一个顶点和一条权值最小的边的边，直到把所有的顶点都包括进生成树。，直到把所有的顶点都包括进生成树。1、普里姆算法、普里姆算法l从任意一个顶点开
28、始从任意一个顶点开始，首先把这个顶点包括在生成树里，首先把这个顶点包括在生成树里，l然后在那些其一个端点已在生成树里另一个端点还未在生成然后在那些其一个端点已在生成树里另一个端点还未在生成数里的边中，数里的边中，找权值最小的一条边找权值最小的一条边，l当有两条具有同样的最小权值的边可供选择时，选哪一条都当有两条具有同样的最小权值的边可供选择时，选哪一条都行。行。l并把这条并把这条边和其不在生成树里的那个端点包括进生成树里边和其不在生成树里的那个端点包括进生成树里。例例16543265135664251311631416431421164321425165432142531、普里姆算法、普里姆算
29、法l普里姆算法普里姆算法的时间复杂度为的时间复杂度为O（n2），与网中的边数），与网中的边数无关，因此无关，因此适用于求边稠密的网的最小生成树适用于求边稠密的网的最小生成树。2、克鲁斯卡尔、克鲁斯卡尔(Kruskal)算法算法l而而克鲁斯尔算法克鲁斯尔算法恰恰相反，它的时间复杂度为恰恰相反，它的时间复杂度为O(eloge)（e为网中边的数目），因此，它相当于普里为网中边的数目），因此，它相当于普里姆算法而言，姆算法而言，适合于求边稀疏的网的最小生成树适合于求边稀疏的网的最小生成树。例例165432651356642516543212345l克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法:假设连
30、通网假设连通网N=（V，E），则令），则令最小生成树的初始状态为只有最小生成树的初始状态为只有n个顶点而无边的非连通图个顶点而无边的非连通图T=（V，），图中每个顶点自成一个连同分量。在），图中每个顶点自成一个连同分量。在E中选择代中选择代价最小的边，若该边依附的顶点落在价最小的边，若该边依附的顶点落在T中不同的连通分量上，中不同的连通分量上，则将此边加入到则将此边加入到T中，否则舍去此边而选择下一条代价最小的中，否则舍去此边而选择下一条代价最小的边。依次类推，直至边。依次类推，直至T中所有顶点都在同一连通量上为止。中所有顶点都在同一连通量上为止。2、克鲁斯卡尔、克鲁斯卡尔(Kruskal)算
31、法算法（1）用顶点数组和边数组存放顶点和边信息）用顶点数组和边数组存放顶点和边信息顶点结点：顶点结点：typedef struct int data;/顶点信息顶点信息 int jihe;VEX;边结点：边结点：typedef struct int vexh,vext;/边依附的两顶点边依附的两顶点 int weight;/边的权值边的权值 int flag;/标志域标志域 EDGE;（2）初始时，令每个顶点的）初始时，令每个顶点的jihe互不相同；每个边的互不相同；每个边的flag为为0（3）选出权值最小且）选出权值最小且flag为为0的边的边（4）若该边依附的两个顶点的）若该边依附的两个顶
32、点的jihe 值不同，即非连通，则令该值不同，即非连通，则令该边的边的flag=1,选中该边；选中该边；l（5）重复上述步骤，直到选出）重复上述步骤，直到选出n-1条边为止条边为止 l再令该边依附的两顶点的再令该边依附的两顶点的jihe以及两集合中所有顶点的以及两集合中所有顶点的jihe相同。相同。若该边依附的两个顶点的若该边依附的两个顶点的jihe 值相同，即连通，则令该边值相同，即连通，则令该边的的flag=2,即舍去该边即舍去该边例例1654326513566425datajihe124536124536124536vexhweight112213233544vextflag615355
33、00000001342567893345566664260000111114211122222165432123452、克鲁斯卡尔、克鲁斯卡尔(Kruskal)算法算法 交通网络中常常提出这样的问题：从甲地到乙地之间交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通是否有公路连通?在有多条通路的情况下，哪一条路最短在有多条通路的情况下，哪一条路最短?7.4-2 最短路径最短路径 迪杰斯特拉迪杰斯特拉(Dijkstra)(Dijkstra)算法的基本思想是算法的基本思想是:逐步扩充一个集合逐步扩充一个集合S S，存放已求出其最短路径的顶点；，存放已求出其最短路径的顶点；尚未确定最短路径
34、的顶点集合是尚未确定最短路径的顶点集合是V-SV-S，其中，其中V V为网中所有顶为网中所有顶点集合；点集合；按最短路径长度递增的顺序逐个以按最短路径长度递增的顺序逐个以V-SV-S中的顶点加到中的顶点加到S S中；中；直到直到S S中包含全部顶点，而中包含全部顶点，而V-SV-S为空。为空。具体做法具体做法:设源点为设源点为Vl,Vl,则则S S中只包含顶点中只包含顶点VlVl，令，令W=V-SW=V-S，则，则W W中包含中包含除除VlVl外图中所有顶点，外图中所有顶点，VlVl对应的距离值为对应的距离值为0 0，W W中顶点对应的距离值中顶点对应的距离值:若图中有弧若图中有弧，则，则Vj
35、Vj顶点的距离为此弧权值，否则为顶点的距离为此弧权值，否则为(一个一个很大的数很大的数)，每次从每次从W W中选一个其距离值为最小的顶点中选一个其距离值为最小的顶点VmVm加入到加入到S S中，对中，对W W中的各中的各个顶点的距离值进行一次修改。个顶点的距离值进行一次修改。若加进若加进VmVm做中间顶点，使做中间顶点，使+的值小于的值小于值，值，则用则用+代替原来代替原来VjVj的距离，否则，什么也不做。的距离，否则，什么也不做。修改后再在修改后再在W W中选距离值最小的顶点加入到中选距离值最小的顶点加入到S S中，中，如此进行下去，直到如此进行下去，直到S S中包含了图中所有顶点为止。中包
36、含了图中所有顶点为止。迪杰斯特拉算法的求解过程：迪杰斯特拉算法的求解过程：10 3 5 20 8 25 4 30 3 30 1 2 3 5 4 (a)一个有向网点 (b)源点 1 到其它顶点的初始距离 1 2 3 5 4 12 3 8 25 30 1 2 3 5 4(c)第一次求得的结果 (d)第二次求得的结果 3 8 12 4 1 2 3 5 4 3 8 12 4 3 8 12 4(e)第三次求得的结果 (f)第四次求得的结果 1 2 3 5 4 1 2 3 5 4 10 3 5 20 8 25 4 30(a)一个有向网点 (b)源点 1 到其它顶点的初始距离 1 2 3 5 4 12 顶点
37、对之间的最短路径是指：对于给定的有向网顶点对之间的最短路径是指：对于给定的有向网G=(V,E),G=(V,E),要要对对G G中任意一对顶点有序对中任意一对顶点有序对V V、W(VW),W(VW),找出找出V V到到W W的最短距离。的最短距离。解决此问题的一个有效方法是解决此问题的一个有效方法是:轮流以每一个顶点为源点轮流以每一个顶点为源点,重重复执行迪杰斯特拉算法复执行迪杰斯特拉算法n n次次,即可求得每一对顶点之间的最短路径即可求得每一对顶点之间的最短路径,总的时间复杂度为总的时间复杂度为O(nO(n3 3)。弗洛伊德提出了另外一个求图中任意两顶点之间最短路径的弗洛伊德提出了另外一个求图
38、中任意两顶点之间最短路径的算法，虽然其时间复杂度也是算法，虽然其时间复杂度也是 O(nO(n3 3)，但其算法的形式更简单，易，但其算法的形式更简单，易于理解和编程。于理解和编程。弗洛伊德算法的基本思想是弗洛伊德算法的基本思想是:设置一个设置一个nxnnxn的矩阵的矩阵A A(k)(k)，其，其中除对角线的元素都等于中除对角线的元素都等于0 0外，其它元素外，其它元素a a(k)(k)ijij表示顶点表示顶点i i到顶点到顶点j j的路径长度，的路径长度，K K表示运算步骤。开始时，以任意两个表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路顶点之间的有向边的
39、权值作为路径长度，没有有向边时，路径长度为径长度为，当，当K=OK=O时时,A,A(0)(0)ij=arcsijij=arcsij 以后逐步尝试在原路径中加入其它顶点作为中间顶点，以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：则以此新路径代替原路径，修改矩阵元素。具体做法为：第一步，让所有边上加入中间顶点第一步，让所有边上加入中间顶点1 1，取，取AijAij与与Ai1+A1jAi1+A1j中较小的值作中较小的值作AijAij的值，完成
40、后得到的值，完成后得到A A(1)(1)，第二步，让所有边上加入中间顶点第二步，让所有边上加入中间顶点2 2，取，取AijAij与与Ai2+A2jAi2+A2j中较小的值，完成后得到中较小的值，完成后得到A A(2)(2)，如此进行下去，如此进行下去，当第当第n n步完成后，得到步完成后，得到A A(n)(n)，A A(n)(n)即为我们所求结果即为我们所求结果,A,A(n)(n)ijij表示表示顶点顶点i i到顶点到顶点j j的最短距离。的最短距离。因此，弗洛伊德算法可以描述为因此，弗洛伊德算法可以描述为:A(0)ij=arcsij;/arcs为图的邻接矩阵为图的邻接矩阵 A(k)ij=minA(k-1)ij,A(k-1)ik+A(k-1)kj其中其中 k=1,2,n
