一、最小生成树

一个含有n个顶点的连通图G，若它的一棵带权生成树的各边权值之和最小，则称该生成树为图G的最小生成树，该树包含图的所有顶点，其边的个数为n-1；在生成最小生成树时可以选择不同的边，所以最小生成树不唯一（存在权值相同的边）；但若当图G的各边权值不同，则此时最小生成树是唯一的。

产生图的最小生成树主要有两个算法，分别是普里姆算法（Prim）和克鲁斯卡尔算法（Kruskal），由于连通图的最小生成树不一定唯一，所以通过这两种算法生成的最小生成树可能相同也可能不同。

（一）普里姆算法（Prim）

普里姆算法步骤

图G=（V，E）是一个含有n个顶点的连通图，普里姆算法的步骤如下：

1、从顶点集V中任意选取一个顶点，然后将与该顶点邻接的边中选取一条权值最小的边，将其并入，从而得到一棵树；

2、继续选取邻接的边中最短的边（权值最小），并入树中；

3、直到图中的所有顶点都被并入，得到最小生成树。

例如，下面是一个无向带权连通图，采用普里姆算法生成最小生成树：

1、任意选取一个顶点为起点开始，这里选取V1为例。

2、此时邻接的边的权值分别为2、3、6，取最小权值2，V1与邻接的顶点V4相连：

3、此时邻接的边的权值分别为1、4、5、5，以及加上前面的3、6，取最小权值1，V4与邻接的顶点V6相连：

4、此时邻接的边的权值分别为3、4，以及加上前面的3、6、4、5、5，取最小权值3，V6与邻接的顶点V5相连：

5、取此时最小权值，取的是当前图中剩余各边对应权值中最小的权值，即3，V1与V3相连：

6、取此时最小权值，即4，V4与V2相连，至此所有顶点都被访问到，得到最小生成树（该最小生成树的代价为3+1+4+2+3=13）：

✨图G=（V，E），在邻接矩阵的存储结构下，普里姆算法的时间复杂度为O(|V|2)，它适用于求解稠密图的最小生成树。

（二）克鲁斯卡尔算法（Kruskal）

克鲁斯卡尔算法中将图的所有边对应的权值按照从小到大的顺序依次开始选取，若选取的某边与先前的树构成回路，则舍去，一直进行下去，直到所有顶点被访问到，当生成树的边的个数为n-1时为止，即可得到最小生成树。

1、并查集

这里的判断是否构成回路，要使用到并查集，并查集中的树可以通过一个结点找到其双亲结点，从而找到根结点，即用到了树的双亲存储结构：

双亲表示法是通过采用一维数组来存储树中的结点，其中每个结点被赋予一个结构体类型，包含data域和parent域，分别存储结点的数据域和存储该结点双亲的数组下标，通过双亲表示法中可以很容易地找到每个结点的双亲和祖先。

通过这种表示法可以很快地找到两个含有多个元素的集合将其并为一个，两个集合相当于并查集中的两棵树，只需找到一棵树的根结点，然后将其作为另一颗树的某一结点的孩子结点，如下：

例如，将第二棵树的根结点作为第一颗树V4结点的孩子结点，即可得到：

从而可以在判断是否形成回路时，判断两个顶点是否属于同一棵树中的集合，即找到它们的根结点，若有相同的根结点，则说明是同一个集合，以此来完成克鲁斯卡尔算法。

2、克鲁斯卡尔算法步骤

例如，下面是一个无向带权连通图，采用普里姆算法生成最小生成树：

1、将图中所有边对应的权值，按从小到大排序如下：1，2，3，4，5，6，8。

2、可知权值1最小，首先连接V4和V6：

3、选择权值2，连接V6与V5：

4、选择权值3，选取V4与V1连接：

5、选择权值4，连接V1与V3：

6、选取权值5，连接V4与V2，最终得到最小生成树如下（该最小生成树的代价为4+3+1+5+2=15）：

✨图G=（V，E），克鲁斯卡尔算法中由于要对所有的边的权值按从小到大进行排序，所以其时间复杂度取决于排序算法，其规模由图的边数E决定，相较于普里姆算法，它适用于求稀疏图或顶点较多的图的最小生成树。

二、最短路径

（一）最短路径的定义

在树中，一个结点和另一个结点之间的分支即为这两个结点之间的路径。

在带权图中，一个顶点到另一个顶点所经过边的权值之和称为该路径的带权路径长度，由于可能路径不止一条，所以将带权路径长度最短的那条路径称为最短路径，最短路径的求解问题可分为两类：求单源最短路径和求一对顶点之间最短路径，分别由广度优先搜索或迪杰斯特拉算法和弗洛伊德算法求解。

其中BFS算法只适用于不带权值的图，而Dijkstra算法和Floyd算法都适用。

（二）BFS算法

1、算法步骤

通过广度优先搜索算法可以求非带权图的单源最短路径（而对于带权值的图则不适合），一开始要设置三个数组d[ ]、path[ ]和visited[ ]，其中d[ ]数组用于存储顶点u到顶点w的最短路径（u到w的所有路径中最少的边数），若没有路径则用∞表示，该数组中一开始初始值都为∞；path[ ]数组初始值都为-1，该数组用于存放该最短路径的起始点，也就是由哪个顶点而来；

visited[ ]数组一开始所有顶点的初始值都为FALSE。

//BFS算法求最短路径
void BFS_MIN_Distance(Graph G,int u) {
  for(i=0; i<G.vexnum; ++i) {
  d[i]=∞;
  path[i]=-1;
  }
  visited[u]=TRUE;  //标识该顶点已被访问 
  d[u]=0;     
  EnQueue(Q,u);   //u入队
  while(!isEmpty(Q)) {  //若队列不为空 
  DeQueue(Q,u);  //队头元素u出队 
  for(w=FirstNeighbor(G,u); w>=0; w=NextNeighbor(G,u,w))  //寻找u的邻接顶点 
    if(!visited[w]) {  //w为u的邻接顶点且未被访问过 
    visited[w]=TRUE;  //设置已被访问 
    d[w]=d[u]+1;  //路径长度加1 
    path[w]=u;    //最短路径为u到w，即path[w]的相应的值为u 
    EnQueue(Q,w);  //顶点w入队 
    }
  }
}

当指定某一顶点u开始进行BFS算法时，将该顶点的d[u]置为0，并在visited[

]数组中将visited[u]标为TRUE，表示已访问该顶点。

然后，找到顶点u所有的邻接顶点w，将未访问的顶点入队，每次执行出队操作（队头元素出队），继续找出当前队头元素的邻接顶点，同时修改相应的d[w]、path[w]、visited[w]，……，由于w是u的邻接顶点（同样，u可能有多个邻接顶点w1、w2……），所以其中path[w]的值为u，当访问了所有顶点后（队列为空时），最后可以通过得到的各d[w]和path[w]来直接找到顶点u到各顶点w的最短路径、最短路径长度和经过的前驱顶点。

2、例题

例如，对于下面这个无向图，进行BFS算法求最短路径（设以顶点1开始）：

1、初始化数组【队列为空，左边为队头】，初始状态：

2、由于从顶点1开始，将d[1]=0，并将visited[1] =TRUE：

将该顶点入队列【1】，然后执行出队，查找队头元素顶点1的邻接顶点且未被访问，即2、4，将其标记，由于这两个顶点距顶点1路径长度为1，将其相应的d[ ]置为1，即d[w]=d[u]+1；另外，由于这两个顶点由顶点1而来，将其相应的path[ ]置为1 ，即path[w]=u，然后将这两个顶点依次入队【2、4】：

3、此时，队列非空，执行出队操作，查找队头元素顶点2的邻接顶点且未被访问，找到顶点1和顶点3，由于顶点1也被标记则不考虑，即只有3，将其标记，由于这个顶点距顶点2路径长度为2，即d[3]=d[2]+1=2；另外，由于这个顶点由顶点2而来，将其相应的path[ ]置为2 ，即path[3]=2，然后将这顶点入队【4、3】：

4、此时，队列非空，执行出队操作，查找队头元素顶点4的邻接顶点且未被访问，找到顶点5和顶点6，将其标记，由于这个顶点距顶点4路径长度为1，即d[5]=d[6]=d[4]+1=2；另外，由于这个顶点由顶点4而来，将其相应的path[ ]置为4 ，即path[5]=path[6]=4，然后将这顶点入队【3、5、6】：

5、此时，队列非空，执行出队操作，查找队头元素顶点3的邻接顶点且未被访问，没有则继续for循环；执行出队操作，查找队头元素顶点5的邻接顶点且未被访问，顶点5的邻接顶点4和6都被访问，没有则继续for循环；顶点6也是一样，所以结束for循环，所有顶点都被访问完，队列为空【】。

6、由所得到的d[ ] 和path[ ] 信息，可以得到顶点1到图中任何一个顶点的最短路径长度，以及经过的前驱顶点：

例如，要求顶点1到顶点6的最短路径，通过d[6] 可知，最短路径长度为2，且其前驱顶点为顶点4，即路径为1→4→6，经过顶点4。

7、另外，可以通过广度优先搜索得到的序列从而得到一棵广度优先生成树，上面得到的广度优先生成树如下（由于是从顶点1开始的，为一棵以顶点1为根，高度最小的生成树）：

与DFS遍历一样，对一个连通图或非连通图进行BFS遍历后，若将在遍历过程中所经历过的顶点保留，则可以形成一棵树或森林，即广度优先生成树或广度优先生成森林；另外，基于邻接表存储的广度优先生成树或广度优先生成森林也是不唯一的；而对于邻接矩阵则是唯一的。

（三）Dijkstra算法

1、算法步骤

求带回路的带权有向图或一个顶点到其他顶点的最短路径，可以采用迪杰斯特拉算法，它和BFS算法一样，也是用于求单源最短路径。一开始要设置三个数组dist[ ]、path[ ]和final[ ]。首先Dijkstra算法中的path[ ]数组与前面的BFS算法中的数组的用途一样，也是存放该最短路径的起始点（前驱顶点），也就是由哪个顶点而来，该数组的初始值都为-1；dist[ ]数组中，若顶点u到顶点v的有弧，则存储弧上的权值，若没有则用∞表示，表示目前还暂时没有找到一条路径；final[ ]数组一开始所有顶点的初始值都为FALSE，它用于标记各顶点是否已经找到最短路径。

当指定某一顶点u开始进行Dijkstra算法时，将该顶点的dist[u]置为0，并将final[u]标为TRUE，且修改其对应的dist[ ]数组和path[ ]数组：

每次遍历寻找的是距离最近（带权值最小）且未被访问的邻接顶点，遍历到终点为止，最后得到的是一条带权路径长度之和最小的路径。

2、例题

例如，下面是一个带权有向图，通过迪杰斯特拉算法求其最短路径（若以图中顶点1为起始点，求到其余顶点的最短路径）：

1、初始化数组，初始状态：

2、以图中顶点1为起始点开始，所以dist[1]=0，由于顶点1和顶点2、顶点3之间有弧连接，可知弧上的权值分别为6、2，即dist[2]=6、dist[3]=2，由于其它顶点没有直接的弧，所以都置为∞，表示目前还暂时没有找到一条路径。另外，path[2]、path[3]有前驱顶点1，也就是由顶点1而来，所以path[2]=path[3]=1：

3、开始循环遍历所有的顶点，寻找还没有确定最短路径的顶点（final[ ]=FALSE）且dist[ ]数组值最小的顶点v（起始点不算），并令其final[v]=TRUE。可知dist[ ]当前数组值最小的顶点为顶点3，令final[3]=TRUE，由于其path[3]=1且dist[3]=3 ，从而此时就确定了顶点1到顶点3的最短路径为V1→V3：

4、检查与顶点3邻接的顶点，若邻接顶点的final[ ]=FALSE，则更新dist[ ]和path[ ]数组信息，即遍历寻找的是从顶点1到当前检查的邻接顶点的最短路径长度和经由的顶点。

与其相邻的顶点有2、4、5，其final[ ]=FALSE：

由源点经由顶点3至顶点2的路径长度为2+3=5，可以发现这是条最短路径，所以将dist[2]=5，经过顶点2，path[2] =3；

由源点经由顶点3至顶点4的路径长度为2+9=11，可以发现这是条最短路径，所以将dist[4]=11，经过顶点4，path[4] =3；

由源点经由顶点3至顶点5的路径长度为2+2=4，可以发现这是条最短路径，所以将dist[5]=4，经过顶点5，path[5] =3。

5、继续执行操作(3)的步骤，循环遍历所有的顶点，寻找还没有确定最短路径的顶点（final[ ]=FALSE）且dist[ ]数组值最小的顶点v（访问过的不算），并令其final[v]=TRUE。

可知dist[ ]当前数组值最小的顶点为顶点5，令final[5]=TRUE，由于其dist[3]=4且path[5]=3 ，从而此时就确定了顶点1到顶点5的最短路径为V1→V3→V5：

6、也是一样，检查与顶点5邻接的顶点，若邻接顶点的final[ ]=FALSE，则更新dist[ ]和path[ ]数组信息，与其相邻的顶点有顶点6，其final[ ]=FALSE：

由源点经由顶点5至顶点6的路径长度为2+2+3=7，可以发现这是条最短路径，所以将dist[6]=7，经过顶点5，path[6] =5：

7、重复以上操作，可知dist[ ]当前数组值最小的顶点为顶点2，令final[2]=TRUE，由于其dist[2]=5且path[2]=3，从而此时就确定了顶点1到顶点2的最短路径为V1→V3→V2：

也是一样，检查与顶点2邻接的顶点，若邻接顶点的final[ ]=FALSE，则更新dist[ ]和path[ ]数组信息，与其相邻的顶点有顶点3、4、5，其中由于顶点3和顶点5的final[ ]=TRUE，所以不考虑进去，只考虑顶点4：

由源点经由顶点2至顶点4的路径长度为6+2=8，可以发现这是条最短路径，所以将dist[4]=8，经过顶点2，path[4] =2。

8、继续重复以上操作，可知dist[ ]当前数组值最小的顶点为顶点6，令final[6]=TRUE，由于其dist[6]=7且path[6]=5，从而此时就确定了顶点1到顶点6的最短路径为V1→V3→V5→V6：

也是一样，检查与顶点6邻接的顶点，由于没有则不考虑。

9、继续重复以上操作，可知dist[ ]当前数组值最小的顶点为顶点4，令final[4]=TRUE，由于其dist[4]=8且path[4]=2，从而此时就确定了顶点1到顶点6的最短路径为V1→V3→V5→V6：

检查与顶点4邻接的顶点，若邻接顶点的final[ ]=FALSE，则更新dist[ ]和path[ ]数组信息，与其相邻的顶点有顶点6，由于顶点6的final[ ]=TRUE，所以不考虑进去，最终得到：

10、由所得到的dist[ ] 和path[ ] 信息，可以得到顶点1到图中任何一个顶点的最短路径长度，以及经过的前驱顶点：

例如顶点1到顶点4的最短路径，由dist[4] =8，可知最短路径长度为8，又由path[4] =2，经由顶点2，即最短路径为V1→V2→V4。

✨对于图G=（V，E），在邻接矩阵的存储结构下，迪杰斯特拉算法时间复杂度为O(|V|2)。

（四）Floyd算法

1、弗洛伊德算法步骤

弗洛伊德算法用于求一对顶点之间的最短路径，其步骤如下：

若对于图中的顶点vi和顶点vj，规定若两个顶点之间存在边，则将该边上的权值作为其最短路径长度，否则以∞表示其最短路径长度；

然后在每条路径中加入中间顶点，若加入后的路径长度减少了，则新路径替换旧路径，得到新的最短路径长度。

例如，对于下面这个带权有向图G，其邻接矩阵如下，对其进行弗洛伊德算法求每一对顶点之间的路径：

以一个顶点为中间点（以0为例），对图中的所有顶点对{vi，vj}，即{V1，V2}，{V1，V3}，{V1，V2}，{V2，V1}，{V2，V3}，{V2，V4}，{V3，V1}，{V3，V2}，{V3，V4}，{V4，V1}，{V4，V2}，{V4，V3}，设当前访问的顶点对为{vi，vj}，若A[vi][vj]>A[i][0]+A[0][j]，则用A[i][0]+A[0][j]替换A[vi][vj]。

1、初始A-1为原邻接矩阵。以V1为中间点，未发现要替换的顶点，更新后的方阵标记为A0，所以A-1和A0都为如下：

我们另设一个矩阵Path，将开始时所有矩阵元素都置为1，所以在以V1为中间点后，得到的Path-1和Path0如下：

2、以V2为中间点，也是检查所有的顶点对，若A[vi][vj]>A[i][1]+A[1][j]，则用A[i][1]+A[1][j]替换A[vi][vj]。其中由于A[0][2]>A[0][1]+A[1][2]=5+4=9，所以将矩阵中的第一行第三列，即A[0][2]替换为A[0][1]+A[1][2]，∞替换为9，如下得到A1：

以V2为中间点，更改后的Path1如下（由于是在矩阵中，按从0开始，V2为中间点此时算1，也就是将-1替换为1）：

3、以V3为中间点，检查所有的顶点对，若A[vi][vj]>A[i][2]+A[2][j]，则用A[i][2]+A[2][j]替换A[vi][vj]。其中由于A[1][0]>A[1][2]+A[2][0]=4+3=7，A[3][1]>A[3][2]+A[2][1]=1+3=4，A[3][0]>A[3][2]+A[2][0]=1+3=4，所以将以上都替换为相应的值，如下得到A2：

以V3为中间点，更改后的Path2如下（由于是在矩阵中，按从0开始，V3为中间点此时算2，也就是将相应的值替换为2）：

4、以V4为中间点，检查所有的顶点对，若A[vi][vj]>A[i][3]+A[3][j]，则用A[i][3]+A[3][j]替换A[vi][vj]。其中由于A[0][2]>A[0][3]+A[3][2]=7+1=8，A[1][0]>A[1][3]+A[3][0]=2+4=6，A[1][2]>A[1][3]+A[3][2]=2+1=3，所以将以上都替换为相应的值，如下得到A3：

以V3为中间点，更改后的Path3如下（由于是在矩阵中，按从0开始，V4为中间点此时算3，也就是将相应的值替换为3）：

访问所以顶点完成，得到的两个矩阵A和Path如下：

2、求最短路径

通过弗洛伊德算法得到的两个矩阵，其中从矩阵A中可以直接得到图中任意两个顶点的最短路径。

例如，顶点V1到顶点V4的最短路径即为A[0][3]=7，顶点V2到顶点V4的最短路径即为A[1][3]=2（注：矩阵从0下标开始）。

由矩阵A和矩阵Path可以得到图在任意两个顶点之间最短路径上的顶点序列或边序列。

例如，要求顶点V2到顶点V1之间的最短路径顶点序列：

1、通过矩阵A可知，A[1][0]=6，所以顶点V2到顶点V1之间的最短路径为6；

2、由矩阵Path可知，Path[1][0]=3，所以顶点V2到顶点V1之间要经过顶点V4；

3、以V4作为起点，求顶点V4到顶点V1之间，由矩阵Path可知，Path[3][0]=2，所以顶点V4到顶点V1之间要经过顶点V3；

4、以V3作为起点，求顶点V3到顶点V1之间，由矩阵Path可知，Path[2][0]=-1，所以顶点V3到顶点V1之间有直接的边，到此结束；

5、得到顶点V2到顶点V1之间的最短路径顶点序列为：V2→V4→V3→V1。

✨对于图G=（V，E），由于其算法代码中有三个for循环嵌套，从而完成以某顶点为中间点时对所有的顶点对进行检查和替换操作，故弗洛伊德算法时间复杂度为O(|V|3)。