Loading... # 图 ## 基本概念 图（graph）是一种非线性结构，在图形结构中，结点与结点之间的关系可以是任意的，从逻辑结构来看，图中任意一个结点的前驱、后继个数都不加限制。现实世界中图的应用极为广泛，已广泛应用于人工智能、通信工程、计算机网络和非线性科学等领域。 定义9.1： 图G=（V，E）是由非空有穷顶点（vertex）集V和V上的顶点对所构成的边（edge）集E组成。如果E中任一条边都是有序顶点对，则图是有向（directed）图。若图中代表任一条边的顶点对是无序的，则称此图为无向图（undirected graph）。常用$<V_1,V_2>$二表示一条有向边，$(V_1,V_2) $表示一条无向边；有向边中$V_1$称为边的始点，$V_2$称为边的终点。有向图中 $<V_1,V_2><V_2,V_1>$代表不同的边，无向图中$(V_1,V_2)(V_2,V_1)$代表同一条边。  简单图，即图中任意两点之间至多有一条边，且不含自回路（即顶点V到V自身的边）。对于简单图，容易得到下述结论∶任何一个具有n个顶点的无向图，其边数小于等于n(n-1)/2。把边数等于n(n-1)/2的含有n个顶点的无向图称为完全图。类似地，在一个含有 n个顶点的有向图中，其最大边数为n(n-1)。 若$(V_1,V_2)\in E$，则称V，和V2是相邻顶点，而边$(V_1,V_2)$则是与顶点$V_1$和$V_2$相关联的边。若$<V_1,V_2>\in E$为有向图的一条边，则称顶点$V_1$邻接到预点$V_2$，顶点$V_2$邻接于顶点$V_1$，，而边<V1，V2>是与顶点$V_1,V_2$相关联的。 在有向图中，以顶点$V_1$为始点与$V_1$相关联的边数，称为$V_1$的出度(out degree)，以顶点$V_1$为终点并与$V_1$相关联的边数称为$V_1$的入度(in degree)。$V_1$的出度与人度之和是$V_1$的度(degree)。无向图中，与$V_1$相关联的边数，称为V的度。 不难验证下述事实，设图G中有n个结点，t条边，若$d_i$为顶点$V_i$的度数，则$t=\frac12\sum_{i=1}^nd_i$ 有向图中，出度为0的顶点称为终端顶点（或叶子） 若$G_1=(V_1,E_2),G_2=(V_2,E_2) $是两个图，且$V_2\subseteq V_1,E_2\subseteq E_1$，则称G。是G的子图(subgraph)。 在有向(（)或无向)图中，如果存在首尾相接且无重复边的边序列$<V_1,V_2>,<V_2,V_3>,\cdots,<V_{n-1},V_n>$(或$(V_1,V_2),(V_2,V_3),\cdots,(V_{n-1},V_n)$)，那么称这个序列是一条从$V_1$到$V_n$的路径(path)(又称为路、通路)。序列中的边数称为路径的长度(length)。若除了起点$V_1$、和终点$V_n$之外，路径上的其他顶点全不相同，则称该路径是一条简单路径. $V_1$=$V_n$，的简单路径称为回路或环(cycle)。 对于无向图G=(V,E)，如果从$V_1$到$V_2$有一条路径相连，则称$V_1$和$V_2$是连通的(connected)。若图G中任意两个顶点$V_i$和$V_j$ $V_i\ne V_j$都是连通的，则称无向图G是连通的。 对于有向图G=(V,E)，若任何有序顶点对$V_i$和$V_j$都有$V_i$到$V_j$的路径(有向的)，则G是强连通的(strong connected）。 一个无向图的连通分支定义为此图的最大连通子图。这种最大连通子图称为图的连通分量。这里所谓最大是指在满足连通的条件下，尽可能多地含有图中的顶点以及这些顶点之间的边。例如图9.2中的图$G_4$中含有 2个最大连通子图。  类似地，有向图中的最大强连通子图称为有向图的强连通分量。一个连通无向图的生成树(spanning tree)是图的一个连通分量，它含有图的全部n个顶点和足以使图保持连通的n-1条边。 有$m(m\ge2)$个连通分量的图的每个连通分量都有一棵生成树，它们构成图的生成树林(spanning forest)。有向图的生成树和生成树林有类似的定义，不同的是对应的树是有向树（有向树中仅有一个顶点的入度为0，其余顶点的入度均为1)。  在某类图中，若每条边都对应一个称为权（weight）的实数，称这样的图为带权图，或。称为网络（network），本节只讨论权为非负实数的网络，权又称为耗费（cost），或称为路径长度。  ## 图的存储表示 ### 相邻矩阵表示图 设图G=(V,E)有n个顶点，m条边，$V=\{V_1,V_2,\cdots,V_3 \} $，则G的相邻矩阵(adjacency matrix)$A_{n\times n}$中的元素$a_{ij}$按下述方式定义： $$ a_{ij}= \begin{cases} 1, &若(V_i,V_j)或<V_i,V_j>是图G的边\\ 2, &若(V_i,V_j)或<V_i,V_j>不是图G的边 \end{cases} $$ 上一节中的$G_1,G_2,G_3$图的相邻矩阵分别为$A_1,A_2,A_3$，其中 $$ A_1= \begin{bmatrix} 0&1&1&0&0\\ 1&0&0&1&0\\ 1&0&0&1&1\\ 0&1&1&0&1\\ 0&0&1&1&0\\ \end{bmatrix} A_2= \begin{bmatrix} 0&1&1&0\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0\\ \end{bmatrix} A_3= \begin{bmatrix} 0&0&1&0&0\\ 1&0&0&1&0\\ 0&0&0&1&0\\ 0&0&0&0&1\\ 0&0&1&0&0\\ \end{bmatrix} $$ 对于带权的图（或称网），其相邻矩阵，即耗费矩阵C按下述方式定义： $$ C_{ij}= \begin{cases} w_{ij},&若(V_i,V_j)\in E (或<V_i,V_j>\in E)，且边(V_i,V_j)\in E或<V_i,V_j>\in E上的权为w_{ij}\\ \infty &否则 \end{cases} $$ 这里$\infty$表示比任何权都大的数，有时，在某些应用中，定义$C_{ij}=0(i=0,1,\cdots,n-1) $。 上节图9.5中的网图可表示为 $$ C= \begin{bmatrix} \infty&20&30&40&\infty & \infty\\ 20&\infty&50&\infty&\infty&\infty\\ 30&50&\infty & \infty&30&60\\ 40&\infty&\infty&\infty&25&\infty\\ \infty&\infty&30&25&\infty&45\\ \infty&\infty&60&\infty&45&\infty\\ \end{bmatrix} $$ 用相邻矩阵表示图，需要存储一个包含n个结点的顺序表来保存结点的信息或指向结点信息的指针，另外还需存储一个n×n的相邻矩阵指示结点间的相邻关系。对于有向图，需 $n^2$个单元存储相邻矩阵;对于无向图，因相邻矩阵是对称的，因而可用一维数组压缩存储它们，仅存其下（或上）三角部分即可。 用相邻矩阵表示图，容易判断任意两个顶点之间是否有边相连，并容易求得各个顶点的度数。对于无向图，相邻矩阵第i行元素值的和就是第i个顶点的度数。对于有向图，矩阵第i行元素值的和是第i个顶点的出度，第 i列元素值的和是第i个顶点的入度。 用相邻矩阵表示图，还容易判定任意两个顶点$V_i$和$V_j$，之间是否有长度为m的路径相连，这只需考虑$A^m(=A*A*\cdots*A)$ 的第i行第j列的元素是否为0即可，如果A第i行第j列的元素为0，则说明从$V_i$到$V_j$之间没有长度为m 的路径相连，否则存在这样的路径。 用相邻矩阵表示图的不足之处是∶无论图中实际含有多少条边，图的读入、存储空间初始化等需要花费O(n)个单位时间，这对边数较少(当边数 $m\lt\lt n_2$) 的稀疏图是不经济的。对于边数较多（如 $m>nlgn$）的稠密图，这种存储方式是有效的。但实际问题中常见的图是非稠密的，因而有必要考虑图的其他存储方式。 ### 图的邻接表示 图的邻接表(adjacency list)由顶点表和边表构成，其中顶点表的结构为顺序存储的一维数值，数组中第 i个元素为指向与顶点V;相关联的第一条边的指针，边表中结点的结构为no next 用邻接表表示无向图，每条边在它的两个端点的边表里各占一个表目，因此，若每个表目占用一个单元，则存储一个有n个顶点m条边的无向图共需n+2m个存储单元。用邻接表表示有向图，根据需要可以保存每个顶点的出边表，也可保存每个顶点的入边表，只保存人边表和出边表之一，则需用n＋m个存储单元。当 $m \lt\lt n^2$时，用邻接表表示图不仅节省了存储单元，而且与同一个顶点相关联的边在同一个链表里，便于某些图运算的实现。 如果要用邻接表表示网，只需在表中每个结点增加一个字段表示边上的权。   ## 邻接多重表 无向图邻接多重表（adjacency multilist）是无向图的一种链接存储方式。在上一节介绍的无向图的邻接表表示法中，每条边在边表中对应两个结点，这给某些图的运算带来不便。例如在无向图中检测某条边是否被访问或插入、删除等，此时需要找到表示同一条边的两个结点或插入对应于同一条边的两个边表中的结点，若采用邻接多重表表示无向图，则边表中一个结点恰好对应一条边。 在邻接多重表中，邻接多重表由顶点表和边表两部分组成，其中顶点表中结点由下面所示的两个域组成： data|edge --|--| 其中，data 表示顶点相关的信息，edge 为指向与该顶点相关联的第一条边。边表中的结点由下面所示的五个域组成： mark|i|ilink|j|jlink --|--|--|--|--| 其中 * mark：边访问标记； * i,j：表边$(V_i,V_j)$中两个顶点的标号； * ilink：边表的指针，指向与$V_i$相关联的边表中的下一条边。 * jlink：边表的指针，指向与$V_j$相关联的边表中的下一条边。  有向图的邻接多重表（或称十字链表）是有向图的一种链接存储结构。它是一种既保有向图的入边表，又保存有向图的由边表的一种链表。多重链表由顶点表和边表两部分组成，顶点表的结构为 data|$edge_1$|$edge_2$ --|--|--| 其中：data-代表顶点的信息； edge1——指向以该顶点为始点的边表中的第一条边;edge2—指向以该顶点为终点的边表中的第一条边。 而边表中结点的结构与无向图的邻接多重表一致，不同的是 ilink、jlink 的意义有所变化。在有向图的邻接多重表中，ilink 为指向边表中以$V_i$为始点的下一条边的指针，jlink 为指向边表中以$V_j$，为终点的下一条边的指针。  ## 基于邻接表表示的Graph结构 ```cpp #include <stdio.h> #include <stdlib.h> typedef int VertexType;//本来应该自定义 struct vertex { VertexType data; Edge * out; }; typedef struct vertex Vertex; struct edge { int jj; EdgeType vertexinfo; struct edge *next; }; typedef struct edge Edge; struct graph { Vertex *VertexList; int NumVertices; int MaxNumVertices,MaxEdges; int NumEdges; }; typedef struct graph Graph; ``` ## 图的遍历 对于给定的图$G(V,E)$和对树的遍历相仿，从V中任一顶点出发按一定规律沿着图中的边访问图的每个顶点恰一次的运算称为对图的遍历。 通常有两种遍历图的方法∶深度优先遍历和广度优先遍历，这两种遍历方法对无向图和有向图都适用。图的遍历运算，尤其是深度优先遍历，在图的许多相关运算中有广泛的应用。 ### 深度优先遍历 图的深度优先遍历（depth first search）是一种广义的树先根次序遍历方法，递归定义如下∶ （1）任选$G=(V,E)$中某个未被访问的顶点$v\in V$出发，访问 v； （2）以与v相关联的每一个未被访问过的顶点w出发深度优先逼历G； （3）若G中还有未被访问的顶点，则转（1）；否则，遍历终止。  若图是连通的无向图或强连通的有向图，则从其中任何一个结点出发都可以系统地访问遍所有的顶点;若图是有根的有向图，则从根出发可以系统地访问遍所有的顶点。在上述情况下，图的所有顶点加上遍历过程中经过的边所构成的子图称为图的生成树。图 9.11（b）实际上是图9.11（a）按深度方向遍历的生成树。 对于不连通的无向图和不是强连通的有向图，从任意顶点出发一般不能系统地访问遍所有的顶点，而只能得到以此顶点为根的连通分支的生成树。要访问其他顶点则需要从没有访问过的顶点中找一个顶点作为起点再进行遍厉，这样最终得到的是生成树林。图9.12（b）给出了图9.12（a）的深度方向优先遍历的生成树林。图9.12（a）中的V和E定义如下。  基于领导表的深度优先遍历算法 ```cpp void DFS(Graph *g){ Bool visited[DefaultVertexNumbers]; int i; for(i=0;i<g->NumVertices;i++) visited[i]=FALSE; for(i=0;i<n;i++) { if(!reach[i]) dfs(g,i,visited); } } void dfs(Graph *g, int v, int visited[]) { int u; printf("visited vertex: %d\n", ReturnValue(g,v)); visited[v]=TRUE; u=ReturnFirstNeighbor(g,v); while(u!=1) { if(!visited[u]) dfs(g,u,visited); u=ReturnNextNeighbor(g,v,u); } } VertexType returnValue(Graph *g,in i) { if(i>=0 && i<g-NumVertices) return g->VertexList[i].data; else { printf("error!"); exit(1); } } int ReturnFirstNeighbor(Graph *g, int v) { Edge *p; if(v!=-1) { p=g->VertexList[v].out; if(p!=NULL) return p->jj; } return -1; } int ReturnNextNeighbor(Graph *g,int vi, int vj) { Edge *p; if(vi!=-1) { p=g->VertexList[vi].out; while(p!=NULL) { if(p->jj==vj&&p->next!=NULL) return p->next->jj; else p=p->next; } } return -1; } ``` ### 广度优先遍历 1. 任选图中一个尚未访问过的顶点v作为遍历起点，访问v； 2. 相继地访问与v相邻而尚未访问过的所有顶点$v_1,v_2,\cdots,v_s$，并依次访问与这些顶点相邻而尚未访问过的所有顶点； 3. 若图中尚有未访问过的顶点，则转（1）；否则遍历过程结束。 ## 最小代价生成树 我们把生成树各迈的权值总和称为生成树的权（或总耗费，总代价），并把权最小的生成树称为G的最小代价生成树（Minimum Cost Spanning Tree）（简称为最小生成树）。 MST定理 定理：设G=(V,E)是一个连通网络，U 是V的一个真子集。若$(u,w)$是G中所有个端点在U（即 $u\in U$）里、另一个端点在$w\notin U$即$w\in V \setminus U$）里的边中T真有最小权值的一条边，刺一定存在G的一棵最小生成树包括此边$(u,w)$。 ``` 普里姆算法： 1. $T=\varnothing(\varnothing代表空集)，U=\{u_0\},u_0\in V$ 2. 选边$$(u^*,w^*)=\min_{u \in U}\{权(u,w)\}$$ 3. $(u^*,w^*)\subseteq T,U=U+\{w^*\}$ 4. 重复2,3，直到$U=V$。  具体实现可叙述为∶欢任意一个顶点开始，首先把这个顶点加入生成树 T中，然后在那些一个端点在生成树、另一个端点不在生成树的边中，选权最小的一条边，并把这条边和其不在生成树里的另一个端点加入生成树。如此重复进行下去，每次往生成树里加一个顶点和一条权最小的边，直到把所有的顶点都包括进生成树。当有两条具有同样的最小权的边可供选择时，选哪一条都可以，这时构造的最小生成树不唯一。图9.15给出了Prim算法构造最小生成树的过程，图9.15()f')和图 9.15(g')为两棵最小生成树。 假设以相邻矩阵表示网，在给出Prim算法之前 ，先确实有关的存储结构如下：网络的边(或最小生成树的边)结点结构： ```cpp weight vi vj typedef struct { int vi,vj; int weight; }edge; int adj[n][n]; edge T[n-1]; ``` ```cpp struct Edge { int vi,vj; int weight; }; typedef struct Edge edge; int adj[n][n]; edge T[n-1]; void prim(void) { int j,k,m,v,min,max=3267,d; edge e; /*T的初始化，顶点编号1,\codts,n*/ for(j=1;j<n;j++) { T[j-1].vi=1; T[j-1].vj=j+1; T[j-1].weight=adj[0][1]; } //求n-1条最小代价生成树的边 for(k=0;k<n-1;k++){//从第一个结点开始 min=max; for(j=k;j<n-1;j++) if(T[j],weight<min) { min=T[j].weight; m=j;//找最小的边 } e=T[m];//T[m],T[k]调换 T[m]=T[k]; T[k]=e; v=T[k].vj; //v是新加入最小代价生成树的顶点号 //修改备选边集 for(j=k+1;j<n-1;j++) { d=adj[v-1][T[j].vj-1]; if(d<T[j].weight) { T[j].weight=d; T[j].vi=v;//把与v相关的换了就好 } } } printf("%d--%d-->",T[0].vi,T[0].weight); for(k=0;k<n-2;k++){ printf("%d--%d-->",T[k].vj,T[k+1].weight); } printf("%d\n",T[n-2].vj); } ``` 上述算法对T的初始化时间是O(n)。k循环内有两个子循环，其时间开销大致为$\sum_{k=1}^{n-2}\left[\sum_{j=k}^{n-1}O(1)+\sum_{j=k+1}^{n-2} \right] \approx2\sum_{k=1}^{n-2}\sum_{j=k}^{n-2}O(1)=O(n^2) $与网中的连数无关，它适合于求边稠密的网的最小生成树。 构造最小生成树的另一个Kruskal算法可描述如下： 1. $T=\varnothing $ 2. while (T含有少于n-1条边且边集E不空) { 从E中挑选一条权最小的边(u*,w*); 从E中删去边(u*,w*); if((u*,w*)加入T后不形成回路) { 则$(u*,w*)\subseteq T $ else 舍弃(u*,w*) } } Kruskal算法的思路很容易理解，它是按边权值的递增顺序构造最小生成树的。图9.16给出了Kruskal算法求图9.15（a）的最小生成树的过程。  Kruskal 算法尚有很多较难实现的细节。具体有以下三方面的问题需解决∶ 1. 图 G=（V，E）的存储结构的选定； 2. 边按权值的排序算法的选定； 3. 如何判断算法中（u*，w）加入 T后不形成回路。 关于（3），一个有效的方法是把V分成若干个子集。初始时刻，每个顶点自成一个集合，当每次选出最小权值的边（u*，w*）后，首先考察两端点 u*，w* 是否在同一集合（每个集合实际上是一个等价类），如果不在同一集合，就把（u*，w*）添加到边集 T中，同时把u* 所在的顶点集和 w* 的顶点集合并成一个集合；否则，舍弃边（u*，v*）。这个过程重复进行，直到V中所有顶点都位于同一个称为等价类的集合中结束。 显然，Kruskal 算法的时间开销与网中的边数有关，主要的时间开销在对边进行排序上。设网中有m条边，则最好的排序算法的时间开销为 $O(mlog_2m)$。Kruskal 算法适合于对边稀疏的网络求最小生成树。 ## 单源最短路径问题 对于给定的带权图G=(V,E)(不含回路和负耗费)及单个源点S，求从S到V到其它顶点的最短路径。  戴克斯特拉（Dikstra，1959）提出了一个找最短路径的方法。方法的基本思想是∶将V中的顶点分成两组V=A+B，其中 A组中的顶点已确定了从V。到该顶点的最短路径，B组中的顶点尚未确定从V。到该顶点的最短路径，Dijkstra算法就是依次按最短路径长度递增的原则把 B中的顶点加入到 A 中的过程。  直到 B为空或者不存在从V。到B中顶点的路径(路径长度为$+\infty$)为止。 具体实现 Dijkstra算法时，需要给A、B中的顶点定义距离值 length∶ $\forall V\in A$，定义V.length=从$V_0$到V的最短路径长度； $\forall V \in B$，定义V.length=从$sV_0$到V只允许A中顶点作为中间顶点从V。到V的最短路径长度。 豪特现好 Dijkstra 算法的正确性基于下述两个事实∶ 1. B中距离值最小的顶点$V_m$，其距离值就是从$V_0$到$V_m$，的最短路径长度； 2. $V_m$是B中最短路径最小的顶点。 证明： 1. 用反证法，若$V_m$的距离值不是从$V_0$到$V_m$的最短路径长度，另有一条从$V_0$经过B组某些顶点到达$V_m$的路径，其长度比$V_m$的距离值小，设经过B组第一个顶点是$V_s$，则$V_s.length\lt V_0$经过$V_s$到$V_m$的路径长度$\lt V_m.length$。与$V_m$是B组中距离值最小的顶点矛盾。 2. 设$V_t$是B中异于$V_m$的任意一个顶点。从$V_0$到$V_t$的最短路径只可能有两种情况：一种情况是最短路径上的中间顶点仅在A组中，这时由距离值的定义，其路径长度必然大于$V_m$的距离值；另一种情况是从$V_0$到$V_t$的最短路径上不只包括A组中的顶点作为中间顶点，设路径上第一个在B组中的中间顶点为$V_u$，则$V_0$到$V_t$的路径长度就是$V_u$的距离值，已大于或等于$V_0$到$V_m$的最短路径长度，那么$V_0$到$V_t$的最短路径长度当然不会小于$V_0$到$V_m$的最短路径长度。因此，$V_m$的确是B 中最短路径最小的顶点。 关于求从顶点$V_0$到其他各顶点的最短路径的Dijkstra算法可描述为： 1. $$ \begin{split}&A=\{V_0\},V_0.length=0\\&B=V\setminus\{V_0\},\forall V_i \in B,V_i.length=\begin{cases}权\langle V_0,V_i\rangle,&若存在边\langle V_0,V_i\rangle\\+\infty,&若不存在边\langle V_0,V_i\rangle\end{cases}\end{split} $$ 2. 若$$ V_m.length=\min_{V_i\in B}V_i(\cdot length) $$ 则 $$ A\Leftarrow A\cup\{V_m\},B\Leftarrow B\{V_m\} $$ $$ 3. 修改B顶点中的距离值$$ \forall V_i\in B, 当V_i.length\gt V_m.length+权\langle V_m,V_i\rangle $$ 则 $$ V_i.length=V_m.length+权\langle V_m,V_i\rangle $$ $$ 4. 重复2,3，直到B为空或$\forall V_i\in B,V_i.length=0$ 若采用相邻矩阵adj表示网络进入算法前$adj[i,i]=0(i=0,1,\cdots,n-1)$；算法中用$adj[i,i]=1$标志第i个顶点已进入A组。数组dist[]的每个元素包含两个域length、pre，其中length代表顶点的距离值，pre记录从$V_0$到该顶点路径上该顶点前一不顶点的序号，算法结束时，沿着顶点$V_i$的pre域追溯可确定$V_0$到$V_i$的最短路径上的中间顶点，而$V_i$的length 域就是从$V_0$到$V_i$的最短路径长度。算法中用到的结构说明为∶ ```cpp typedef struct { int length; int pre; }path; int adj[n][n]; path dist[n]; void DIJ(int k) { int i,u,min=32767; for(i=0;i<n;i++) { dist[i].length=adj[k][i]; if(dist[i].length=adj[k][i]); dist[i].pre=k; else dist[i].pre=-1; } adj[k][k]=1; for(;;) { u=-1; min=32767; for(i=0;i<n;i++) if(adj[i][i]==0&&dist[i].length<min) { u=i; min=dist[i].length; } if(u==-1) return; adj[u][u]=1; for(i=0;i<n;i++) if(adj[i][i]==0&&dist[i].length>(dist[u].length+adj[u][i])) { dist[i].length=dist[u].length+adj[u][i]; dist[i].pre=u; } } } ``` 时间复杂度是$O(n^2)$占用的辅助空间是O(n) ## 每一对顶点间的路径最短问题 使用Dijkstra若网络中含有n个顶点，则用$O(n^3)$的时间就可求出网络中每对顶点间的最短路径。这里介绍由弗洛伊德(Floyd)提出的另一种算法，Floyd算法形式上比Dijkstra算法要简单，总的时间开销仍为$O(n^3)$。 设网络不含负耗费，用相邻矩阵 adj表示网络，Floyd算法的基本思想是递推地产生矩阵序列$adj^{(0)},adj^{(1)},\cdots,adj^{(k)},\cdots,adj^{(n)}$，其中 $adj^{(0)}$=adj，$adj^{(0)}[i][j]=adj[i][j] $可以解释为从顶点$V_i$到顶点$V_j$中间顶点序号不大于等于0(也就是说不允许任何顶点作为中间顶点)的最短路径长度(顶点编号从$V_1,V_2,\cdots,V_n $)。对于一般的$k(k=1,2,\cdots,n)$，定义$adj^{(k)}[i][j]$=允许$V_1,V_2,\cdots,V_n $作为中间顶点，从顶点$V_i$到$V_j$的最短路径长度。 显然，如果能递推地产生矩阵序列$adj^{(k)}$，则$adj^{(n)}$中记录了任意两顶点间的最短路径。由$adj^{(k)}[i][j](1\lt i\lt n,1\lt j\lt n)$的定义，不难得到由$adj^{(k-1)}$产生$adj^{(k)}$的方法。 $$ adj^{(k)}[i][j]= \begin{cases} adj^{(k-1)}[i][j], &从V_i到V_j允许V_1,V_2,\cdots,V_k作为中间结点的最短路径上不含V_k\\ adj^{(k-1)}[i][k], &从V_i允许V_1,V_2,\cdots,V_k作为中间结点的最短路径上含V_k \end{cases} $$ 下面给出算法，设网络用相邻矩阵$adj_{n\times n}$表示，路径用整型二维数组$P_{n\times n}$表示，用$D_{n\times n}$记录两顶点间的最短路径。 ```cpp int path[n][n]; void Floyd(int D[][n], int adj[][n]) { int max=32767,i,j,k; for(i=0;j<n;j++) { if(adj[i][j]!=max) path[i][j]=i+1; else path[i][j]=0; D[i][j]=adj[i][j]; } for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(D[i][j]>(D[i][k]+D[k][j])) { D[i][j]=D[i][k]+D[k][j]; path[i][j]=path[k][k] } } ``` ## 有向无回图 没学离散，先不学 Last modification：January 20, 2023 © Allow specification reprint Like 如果觉得我的文章对你有用，请留下评论。