数据结构之图

数据结构与算法

---

一、图的定义

图： 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图的定义与线性表定义的对比：

• 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点（Vertex）。
• 线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。但是在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。
• 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

1.1 各种图定义

无向边: 若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对(vi,vj)来表示。
无向图: 如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）。
对于无向图G1来说，G1=(V1,{E1})，其中顶点集合V1={A,B,C,D}；边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}。

有向边： 若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶来表示，vi称为弧尾（Tail），vj称为弧头（Head）。
有向图: 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。
对于下有向图G2来说，G2=(V2,{E2})，其中顶点集合V2={A,B,C,D}；弧集合E2={,,,}。

无向边用小括号“()”表示，而有向边则是用尖括号“<>”表示。

简单图: 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。
无向完全图: 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

含有n个顶点的无向完全图有n(n-1)/2条边。

有向完全图: 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

含有n个顶点的有向完全图有n×(n-1)条边。

对于具有n个顶点和e条边数的图，无向图$0≤e≤n(n-1)/2$，有向图$0≤e≤n(n-1)$。

稀疏图与稠密图： 有很少条边或弧的图称为稀疏图，反之称为稠密图。这里稀疏和稠密是模糊的概念，都是相对而言的。
权: 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。
网： 带权的图通常称为网（Network）。
子图： 设有两个图G=(V,{E})和G'=(V',{E'})，如果$V'∈V且E'∈E,则称G'为G的子图（Sub-graph）。

1.2 图的顶点与边间关系

邻接点: 对于无向图G=(V,{E})，如果边(v,v')∈E，则称顶点v和v'互为邻接点（Adjacent），即v和v'相邻接。

边(v,v')依附（incident）于顶点v和v'，或者说(v,v')与顶点v和v'相关联。

度： 顶点v的度（Degree）是和v相关联的边的数目，记为TD(v)。

对于有向图G=(V,{E})，如果弧∈E，则称顶点v**邻接到**顶点v'，顶点v'**邻接自**顶点v。弧和顶点v，v'相关联。以顶点v为
头弧的数目称为v的入度（InDegree），记为ID(v)；以v为尾的弧的数目称为v的出度（OutDegree），记为OD(v)；顶点v的度为TD(v)=ID(v)+OD(v)。

路径： 无向图G=(V,{E})中从顶点v到顶点v'的路径（Path）是一个顶点序列$(v=v_{i0},v_{i1},...,v_{im}=v')，其中(v_{i,j-1},v_{i,j})∈E，1≤j≤m$。如果G是有向图，则路径也是有向的，顶点序列应满足$<v_{i,j-1},v_{i,j}>∈E，1≤j≤m。$

路径的长度是路径上的边或弧的数目。

回路: 第一个顶点和最后一个顶点相同的路径称为回路或环（Cycle）。
简单路径: 序列中顶点不重复出现的路径称为简单路径。
简单回路: 除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

1.3 连通图相关术语

连通: 在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。
连通图: 如果对于图中任意两个顶点vi、vj∈V，vi和vj都是连通的，则称G是连通图（Connected Graph）。
连通分量: 无向图中的极大连通子图称为连通分量。连通分量的概念强调：

• 要是子图；
• 子图要是连通的；
• 连通子图含有极大顶点数；
• 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

强连通图: 在有向图G中，如果对于每一对vi、vj∈V、vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
强连通分量: 有向图中的极大强连通子图称做有向图的强连通分量。
下图左边的并不是强连通图，因为顶点A到顶点D存在路径，而D到A就不存在。右边就是强连通图，而且显然图2是图1的极大强连通子图，即是它的强连通分量。

连通图的生成树: 所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
比如下图中图1是一普通图，但显然它不是生成树，当去掉两条构成环的边后，比如图2或图3，就满足n个顶点n-1条边且连通的定义了。它们都是一棵生成树。

如果一个图有n个顶点和小于n-1条边，则是非连通图，如果它多于n-1边条，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2和图3，随便加哪两顶点的边都将构成环。不过有n-1条边并不一定是生成树，比如图4。

有向树: 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一个有向树。

对有向树的理解比较容易，所谓入度为0其实就相当于树中的根结点，其余顶点入度为1就是说树的非根结点的双亲只有一个。

有向图的生成森林: 一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

二、图的抽象数据类型

ADT 图(Graph)
Data
    顶点的有穷非空集合和边的集合。
Operation
    CreateGraph(*G, V, VR): 按照顶点集V和边弧集VR的定义构造图G。
    DestroyGraph(*G):       图G存在则销毁。
    LocateVex(G, u):        若图G中存在顶点u，则返回图中的位置。
    GetVex(G, v):           返回图G中顶点v的值。
    PutVex(G, v, value):    将图G中顶点v赋值value。
    FirstAdjVex(G, *v):     返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空。
    NextAdjVex(G, v, *w):   返回顶点v相对于顶点w的下一个邻接顶点，
                            若w是v的最后一个邻接点则返回“空”。
    InsertVex(*G, v):       在图G中增添新顶点v。
    DeleteVex(*G, v):       删除图G中顶点v及其相关的弧。
    InsertArc(*G, v, w):    在图G中增添弧<v,w>，若G是无向图，还需要增添对称弧<w,v>。
    DeleteArc(*G, v, w):    在图G中删除弧<v,w>，若G是无向图，则还删除对称弧<w,v>。
    DFSTraverse(G):         对图G中进行深度优先遍历，在遍历过程对每个顶点调用。
    HFSTraverse(G):         对图G中进行广度优先遍历，在遍历过程对每个顶点调用。
endADT

三、图的存储结构

3.1 邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

考虑到图是由顶点和边或弧两部分组成。合在一起比较困难，那就很自然地考虑到分两个结构来分别存储。顶点不分大小、主次，所以用一个一维数组来存储是很不错的选择。而边或弧由于是顶点与顶点之间的关系，一维搞不定，那就考虑用一个二维数组来存储。这就诞生了邻接矩阵。

设图G有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

$$arc[i][j] = \begin{cases} 1, & \text{若（vi,vj）∈E或<vi,vj>}∈E \\ 0, & \text{反之} \end{cases} \\ \\ $$
无向图的邻接矩阵：

$对于矩阵的主对角线的值，即arc[0][0]、arc[1][6]、arc[2][7]、arc[3][8]，全为0是因为不存在顶点到自身\\的边，比如v_0到v_0。arc[0][9]=1是因为v_0到v_1的边存在，而arc[1][10]=0是因为v_1到v_3的边不存在。并且由于\\是无向图，v_1到v_3的边不存在，意味着v_3到v_1的边也不存在。所以无向图的边数组是一个对称矩阵。$

根据这个矩阵， 可以知道很多信息：

• 要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行（或第i列）的元素之和。比如顶点v1的度就是1+0+1+0=2。
• 求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点。

有向图的邻接矩阵：

但因为是有向图，所以此矩阵并不对称，比如由v1到v0有弧，得到$arc[1][0]=1$，而v0到v1没有弧，因此$arc[0][12]=0$。
有向图讲究入度与出度，顶点v1的入度为1，正好是第v1列各数之和。顶点v1的出度为2，即第v1行的各数之和。
与无向图同样的办法，判断顶点vi到vj是否存在弧，只需要查找矩阵中$arc[i][j]$是否为1即可。要求vi的所有邻接点就是将矩阵第i行元素扫描一遍，查找$arc[i][j]$为1的顶点。

网的邻接矩阵：
设图G是网图，有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
这里$w_{ij}$表示$（v_i,v_j）$或$<v_i,v_j>$上的权值。∞表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。不为0的原因在于权值$w_{ij}$大多数情况下是正值，但个别时候可能就是0，甚至有可能是负值。因此必须要用一个不可能的值来代表不存在。下就是一个有向网图，右图就是它的邻接矩阵。

/* 顶点类型应由用户定义 */
typedef char VertexType;             
/* 边上的权值类型应由用户定义 */
typedef int EdgeType;                
/* 最大顶点数，应由用户定义 */
#define MAXVEX 100                   
/* 用65535来代表∞ */
#define INFINITY 65535               
typedef struct
{
    /* 顶点表 */
    VertexType vexs[MAXVEX];         
    /* 邻接矩阵，可看作边表 */
    EdgeType arc[MAXVEX][MAXVEX];    
    /* 图中当前的顶点数和边数 */
    int numVertexes, numEdges;       
} MGraph;

无向网图的创建代码：

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *G)
{
    int i, j, k, w;
    printf("输入顶点数和边数:\n");
    /* 输入顶点数和边数 */
    scanf("%d,%d", &G->numVertexes, &G->numEdges);    
    /* 读入顶点信息，建立顶点表 */
    for (i = 0; i < G->numVertexes; i++)              
        scanf(&G->vexs[i]);
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j <G->numVertexes; j++)
            /* 邻接矩阵初始化 */
            G->arc[i][j] = INFINITY;                  
    /* 读入numEdges条边，建立邻接矩阵 */
    for (k = 0; k < G->numEdges; k++)                 
    {
        printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
        /* 输入边(vi,vj)上的权w */
        scanf("%d,%d,%d", &i, &j, &w);                
        G->arc[i][j] = w;
        /* 因为是无向图，矩阵对称 */
        G->arc[j][i] = G->arc[i][j];                  
    }
}

从代码中也可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为$O(n+n^2+e)$，其中对邻接矩阵G.arc的初始化耗费了$O(n^2)$的时间。

3.2 邻接表

邻接矩阵对于边数相对顶点较少的图，存在对存储空间的极大浪费的现象。因此这种存储方式对于稀疏图来说不是很合适。借鉴于线性表的解决方案，可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。

使用数组与链表相结合的存储方式，就诞生了邻接表（Ad-jacency List）。

邻接表的处理办法是这样:
1. 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2. 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。比如v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2。

有向图的邻接表：

有向图由于有方向，以顶点为弧尾来存储边表，这样就很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi都建立一个链接为vi为弧头的表。如上图的第三幅图所示。

网图的邻接表
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如下图：

/* 顶点类型应由用户定义 */
typedef char VertexType;          
/* 边上的权值类型应由用户定义 */
typedef int EdgeType;             
/* 边表结点 */
typedef struct EdgeNode           
{
    /* 邻接点域，存储该顶点对应的下标 */
    int adjvex;                   
    /* 用于存储权值，对于非网图可以不需要 */
    EdgeType weight;              
    /* 链域，指向下一个邻接点　 */
    struct EdgeNode *next;        
} EdgeNode;
/* 顶点表结点 */
typedef struct VertexNode         
{
    /* 顶点域，存储顶点信息 */
    VertexType data;              
    /* 边表头指针 */
    EdgeNode *firstedge;          
} VertexNode, AdjList[MAXVEX];
typedef struct
{
    AdjList adjList;
    /* 图中当前顶点数和边数 */
    int numVertexes, numEdges;    
} GraphAdjList;

无向图的邻接表创建代码如下:

/* 建立图的邻接表结构 */
void  CreateALGraph(GraphAdjList *G)
{
    int i, j, k;
    EdgeNode *e;
    printf("输入顶点数和边数:\n");
    /* 输入顶点数和边数 */
    scanf("%d,%d", &G->numVertexes, 
          &G->numEdges);    
    /* 读入顶点信息，建立顶点表 */
    for (i = 0; i < G->numVertexes; i++)              
    {
        /* 输入顶点信息 */
        scanf(&G->adjList[i].data);                   
        /* 将边表置为空表 */
        G->adjList[i].firstedge = NULL;               
    }
    /* 建立边表 */
    for (k = 0; k < G->numEdges; k++)                 
    {
        printf("输入边(vi,vj)上的顶点序号:\n");
        /* 输入边(vi,vj)上的顶点序号 */
        scanf("%d,%d", &i, &j);                       
        /* 向内存申请空间， */
        /* 生成边表结点 */
        e = (EdgeNode *)malloc(sizeof(EdgeNode));     
        /* 邻接序号为j */
        e->adjvex = j;                                
        /* 将e指针指向当前顶点指向的结点 */
        e->next = G->adjList[i].firstedge;            
        /* 将当前顶点的指针指向e */
        G->adjList[i].firstedge = e;                  
        /* 向内存申请空间， */
        /* 生成边表结点 */
        e = (EdgeNode *)malloc(sizeof(EdgeNode));     
        /* 邻接序号为i */
        e->adjvex = i;                                
        /* 将e指针指向当前顶点指向的结点 */
        e->next = G->adjList[j].firstedge;            
        /* 将当前顶点的指针指向e */
        G->adjList[j].firstedge = e;                  
    }
}

本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。

3.3 十字链表

那么对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。

把邻接表与逆邻接表结合起来，这就是十字链表（Orthogonal List）。

顶点表结点结构：data —— firstin(入边表头指针) —— firstout(出边表头指针)
边表结点结构：

其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

如下图：

虚线箭头其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此v0的firstin指向顶点v1的边表结点中headvex为0的结点，如上图中的①。接着由入边结点的headlink指向下一个入边顶点v2，如图中的②。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如图中的③。顶点v2和v3也是同样有一个入边顶点，如图中④和⑤。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表是非常好的数据结构模型。

3.4 邻接多重表

如果在无向图的应用中，关注的重点是顶点，那么邻接表是不错的选择，但如果更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，却是比较繁琐的。因此可以仿照十字链表的方式，对边表结点的结构进行一些改造。
重新定义的边表结点结构：

其中ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。这就是邻接多重表结构。

邻接多重表构造过程
① 先把顶点与边表节点画出；如下图，由于是无向图，所以ivex是0、jvex是1还是反过来都是无所谓的，不过为了绘图方便，都将ivex值设置得与一旁的顶点下标相同。

② 开始连线，首先连线的①②③④就是将顶点的firstedge指向一条边，顶点下标要与ivex的值相同；

③ 接着，由于顶点v0的(v0,v1)边的邻边有(v0,v3)和(v0,v2)。因此⑤⑥的连线就是满足指向下一条依附于顶点v0的边的目标，注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。
④ 同样的道理，连线⑦就是指(v1,v0)这条边，它是相当于顶点v1指向(v1,v2)边后的下一条。v2有三条边依附，所以在③之后就有了⑧⑨。连线⑩的就是顶点v3在连线④之后的下一条边。
左图一共有5条边，所以右图有10条连线，完全符合预期。

邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了，若要删除左图的(v0,v2)这条边，只需要将右图的⑥⑨的链接指向改为∧即可。

3.5 边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成，如下图：

边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。

四、图的遍历

图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。

图的遍历要比树的遍历复杂的多，因为它的任一顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点却还没有遍历到的情况。因此需要在遍历过程中把访问过的顶点打上标记，以避免访问多次而不自知。具体办法是设置一个访问数组visited[n]，n是图中顶点的个数，初值为0，访问过后设置为1。

4.1 深度优先遍历

深度优先遍历（Depth_First_Search），也有称为深度优先搜索，简称为DFS。

遍历过程

    首先从顶点A开始，做上表示走过的记号后，面前有两条路，通向B和F，可以定一个原则，在没有碰到重复顶点的情况下，始终是向右手边走，于是走到了B顶点。整个行路过程，可参看上图的右图。此时发现有三条分支，分别通向顶点C、I、G，右手通行原则，使得我们走到了C顶点。就这样一直顺着右手通道走，一直走到F顶点。当依然选择右手通道走过去后，发现走回到顶点A了，因为在这里做了记号表示已经走过。此时退回到顶点F，走向从右数的第二条通道，到了G顶点，它有三条通道，发现B和D都已经是走过的，于是走到H，当面对通向H的两条通道D和E时，会发现都已经走过了。

    此时是否已经遍历了所有顶点呢？没有。可能还有很多分支的顶点没有走到，所以按原路返回。在顶点H处，再无通道没走过，返回到G，也无未走过通道，返回到F，没有通道，返回到E，有一条通道通往H的通道，验证后也是走过的，再返回到顶点D，此时还有三条道未走过，一条条来，H走过了，G走过了，I，哦，这是一个新顶点，没有标记，赶快记下来。继续返回，直到返回顶点A，确认已经完成遍历任务，找到了所有的9个顶点。

深度优先遍历其实就是一个递归的过程，就像是一棵树的前序遍历。从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。这里讲到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

如果用邻接矩阵的方式，代码如下：

/* Boolean是布尔类型，其值是TRUE或FALSE */
typedef int Boolean;             
/* 访问标志的数组 */
Boolean visited[MAX];            
/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph G, int i)
{
    int j;
    visited[i] = TRUE;
    /* 打印顶点，也可以其他操作 */
    printf("%c ", G.vexs[i]);    
    for (j = 0; j < G.numVertexes; j++)
        if (G.arc[i][j] == 1 && !visited[j])
            /* 对为访问的邻接顶点递归调用 */
            DFS(G, j);           
}
/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph G)
{
    int i;
    for (i = 0; i < G.numVertexes; i++)
        /* 初始所有顶点状态都是未访问过状态 */
        visited[i] = FALSE;      
    for (i = 0; i < G.numVertexes; i++)
        /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */
        if (!visited[i])         
            DFS(G, i);
}

果图结构是邻接表结构，其DFSTraverse函数的代码是几乎相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下:

/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i)
{
    EdgeNode *p;
    visited[i] = TRUE;
    /* 打印顶点，也可以其他操作 */
    printf("%c ", GL->adjList[i].data);    
    p = GL->adjList[i].firstedge;
    while (p)
    {
        if (!visited[p->adjvex])
            /* 对为访问的邻接顶点递归调用 */
            DFS(GL, p->adjvex);            
        p = p->next;
    }
}
/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList GL)
{
    int i;
    for (i = 0; i < GL->numVertexes; i++)
        /* 初始所有顶点状态都是未访问过状态 */
        visited[i] = FALSE;                
    for (i = 0; i < GL->numVertexes; i++)
        /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */
        if (!visited[i])                   
            DFS(GL, i);
}

对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要$O(n^2)$的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

4.2 广度优先遍历

广度优先遍历（Breadth_First_Search），又称为广度优先搜索，简称BFS。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。如下图，把深度优先遍历图形案例变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与B和F有边的顶点C、I、G、E为第三层，再将这四个顶点有边的D、H放在第四层，此时在视觉上感觉图的形状发生了变化，其实顶点和边的关系还是完全相同的。

邻接矩阵结构的广度优先遍历算法：

/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G)
{
    int i, j;
    Queue Q;
    for (i = 0; i < G.numVertexes; i++)
        visited[i] = FALSE;
    /* 初始化一辅助用的队列 */
    InitQueue(&Q);                                   
    /* 对每一个顶点做循环 */
    for (i = 0; i < G.numVertexes; i++)              
    {
        /* 若是未访问过就处理 */
        if (!visited[i])                             
        {
            /* 设置当前顶点访问过 */
            visited[i]=TRUE;                         
            /* 打印顶点，也可以其他操作 */
            printf("%c ", G.vexs[i]);                
            /* 将此顶点入队列 */
            EnQueue(&Q,i);                           
            /* 若当前队列不为空 */
            while (!QueueEmpty(Q))                   
            {
                /* 将队中元素出队列，赋值给i */
                DeQueue(&Q, &i);                     
                for (j = 0; j < G.numVertexes; j++)
                {
                    /* 判断其他顶点若与当前顶点存在边且未访问过 */
                    if (G.arc[i][j] == 1 && !visited[j])
                    {
                        /* 将找到的此顶点标记为已访问 */
                        visited[j]=TRUE;             
                        /* 打印顶点 */
                        printf("%c ", G.vexs[j]);    
                        /* 将找到的此顶点入队列 */
                        EnQueue(&Q,j);               
                    }
                }
            }
        }
    }
}

对于邻接表的广度优先遍历，代码与邻接矩阵差异不大，代码如下:

/* 邻接表的广度遍历算法 */
void BFSTraverse(GraphAdjList GL)
{
    int i;
    EdgeNode *p;
    Queue Q;
    for (i = 0; i < GL->numVertexes; i++)
        visited[i] = FALSE;
    InitQueue(&Q);
    for (i = 0; i < GL->numVertexes; i++)
    {
        if (!visited[i])
        {
            visited[i] = TRUE;
            /* 打印顶点，也可以其他操作 */
            printf("%c ", GL->adjList[i].data);    
            EnQueue(&Q, i);
            while (!QueueEmpty(Q))
            {
                DeQueue(&Q, &i);
                /* 找到当前顶点边表链表头指针 */
                p = GL->adjList[i].firstedge;      
                while (p)
                {
                    /* 若此顶点未被访问 */
                    if (!visited[p->adjvex])       
                    {
                        visited[p->adjvex] = TRUE;
                        printf("%c ", GL->adjList[p->adjvex].data);
                        /* 将此顶点入队列 */
                        EnQueue(&Q, p->adjvex);    
                    }
                    /* 指针指向下一个邻接点 */
                    p = p->next;                   
                }
            }
        }
    }
}

对比图的深度优先遍历与广度优先遍历算法可知，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点访问的顺序不同。可见两者在全图遍历上是没有优劣之分的，只是视不同的情况选择不同的算法。
深度优先更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

五、最小生成树

最小生成树（Minimum Cost SpanningTree）: 一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边，我们把构造连通网的最小代价生成树称为最小生成树。

找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。

5.1 普里姆（Prim）算法

使用邻接矩阵存储网：

邻接矩阵中用65535代表∞

普里姆（Prim）算法代码如下，其中INFINITY为权值极大值，不妨是65535，MAXVEX为顶点个数最大值，此处大于等于9即可。

/* Prim算法生成最小生成树 */
  void MiniSpanTree_Prim(MGraph G)
  {
      int min, i, j, k;
      /* 保存相关顶点下标 */
      int adjvex[MAXVEX];                        
      /* 保存相关顶点间边的权值 */
      int lowcost[MAXVEX];                       
      /* 初始化第一个权值为0，即v0加入生成树 */
      /* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */
      lowcost[0] = 0;                            
      /* 初始化第一个顶点下标为0 */
      adjvex[0] = 0;                             
      /* 循环除下标为0外的全部顶点 */
      for (i = 1; i < G.numVertexes; i++)        
      {
         /* 将v0顶点与之有边的权值存入数组 */
         lowcost[i] = G.arc[0][i];              
         /* 初始化都为v0的下标 */
         adjvex[i] = 0;                         
     }
     for (i = 1; i < G.numVertexes; i++)
     {
         /* 初始化最小权值为∞， */
         /* 通常设置为不可能的大数字如32767、65535等 */
         min = INFINITY;                        
         j = 1; k = 0;
         /* 循环全部顶点 */
         while (j < G.numVertexes)              
         {
             /* 如果权值不为0且权值小于min */
             if (lowcost[j] != 0 && lowcost[j] < min)
             {                                  
                 /* 则让当前权值成为最小值 */
                 min = lowcost[j];              
                 /* 将当前最小值的下标存入k */
                 k = j;                         
             }
             j++;
         }
         /* 打印当前顶点边中权值最小边 */
         printf("(%d,%d)", adjvex[k], k);       
         /* 将当前顶点的权值设置为0，表示此顶点已经完成任务 */
         lowcost[k] = 0;                        
         /* 循环所有顶点 */
         for (j = 1; j < G.numVertexes; j++)    
         {
             /* 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
             if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
             {                                  
                 /* 将较小权值存入lowcost */
                 lowcost[j] = G.arc[k][j];      
                 /* 将下标为k的顶点存入adjvex */
                 adjvex[j] = k;                 
             }
         }
     }
 }

程序过程详解：

1．程序开始运行，由第4～5行，创建了两个一维数组lowcost和adjvex，    长度都为顶点个数9。它们的作用之后会说明。

2．第6～7行分别给这两个数组的第一个下标位赋值为0，adjvex[0]=0其实意思就是从顶点v0开始（事实上，最小生成树从哪个顶点开始计算都无所谓，这里假定从v0开始），lowcost[0]=0就表示v0已经被纳入到最小生成树中，之后凡是lowcost数组中的值被设置为0就是表示此下标的顶点被纳入最小生成树。

3．第8～12行表示读取上图的右图邻接矩阵的第一行数据。将数值赋值给lowcost数组，所以此时lowcost数组值为{0,10,65535,65535,65535,11,65535,65535,65535}，而adjvex则全部为0。此时，已经完成了整个初始化的工作，准备开始生成。

4．第13～36行，整个循环过程就是构造最小生成树的过程。

5．第15～16行，将min设置为了一个极大值65535，它的目的是为了之后找到一定范围内的最小权值。j是用来做顶点下标循环的变量，k是用来存储最小权值的顶点下标。

6．第17～25行，循环中不断修改min为当前lowcost数组中最小值，并用k保留此最小值的顶点下标。经过循环后，min=10，k=1。注意19行if判断的lowcost[j]!=0表示已经是生成树的顶点不参与最小权值的查找。

7．第26行，因k=1，adjvex[1]=0，所以打印结果为(0,1)，表示v0至v1边为最小生成树的第一条边。如下图所示。

   8．第27行，此时因k=1，将lowcost[k]=0就是说顶点v1纳入到最小生成树中。此时lowcost数组值为{0,0,65535,65535,65535,11,65535,65535,65535}。

9．第28～35行，j循环由1至8，因k=1，查找邻接矩阵的第v1行的各个权值，与low-cost的对应值比较，若更小则修改low-cost值，并将k值存入adjvex数组中。因第v1行有18、16、12均比65535小，所以最终lowcost数组的值为：{0,0,18,65535,65535,11,16,65535,12}。adjvex数组的值为：{0,0,1,0,0,0,1,0,1}。这里第30行if判断的lowcost[j]!=0也说明v0和v1已经是生成树的顶点不参与最小权值的比对了。

10．再次循环，由第15行到第26行，此时min=11，k=5，adjvex[5]=0。因此打印结构为(0,5)。表示v0至v5边为最小生成树的第二条边，如下图所示。

   11．接下来执行到36行，lowcost数组的值为：{0,0,18,65535,26,0,16,65535,12}。ad-jvex数组的值为：{0,0,1,0,5,0,1,0,1}。

   12．之后，通过不断的转换，构造的过程如下图中图1～图6所示。

假设N=(V,{E})是连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V)，TE={}开始。重复执行下述操作：在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。

由算法代码中的循环嵌套可得知此算法的时间复杂度为$O(n^2)$。

5.2 克鲁斯卡尔（Kruskal）算法

普里姆（Prim）算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的，同样的，也可以以边为目标去构建，因为权值是在边上，直接去找最小权值的边来构建生成树是很自然的想法，只不过构建时要考虑是否会形成环路。此时要用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码：

/* 对边集数组Edge结构的定义 */
typedef struct
{
    int begin;
    int end;
    int weight;
} Edge;

克鲁斯卡尔（Kruskal）算法代码如下:

/* Kruskal算法生成最小生成树 */
/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)     
{
    int i, n, m;
    /* 定义边集数组 */
    Edge edges[MAXEDGE];                
    /* 定义一数组用来判断边与边是否形成环路 */
    int parent[MAXVEX];                 
    /* 此处省略将邻接矩阵G转化为边集数组edges
       并按权由小到大排序的代码 */
    for (i = 0; i < G.numVertexes; i++)
        /* 初始化数组值为0 */
        parent[i] = 0;                  
    /* 循环每一条边 */
    for (i = 0; i < G.numEdges; i++)    
    {
       n = Find(parent, edges[i].begin);
       m = Find(parent, edges[i].end);
       /* 假如n与m不等，说明此边没有与现有生成树形成环路 */
       if (n != m)                     
       {
           /* 将此边的结尾顶点放入下标为起点的parent中 */
           /* 表示此顶点已经在生成树集合中 */
           parent[n] = m;              
           printf("(%d, %d) %d ", edges[i].begin, 
                  edges[i].end, edges[i].weight);
       }
    }
}
/* 查找连线顶点的尾部下标 */
int Find(int *parent, int f)            
{
    while (parent[f] > 0)
        f = parent[f];
    return f;
}

程序详解：

1．程序开始运行，第5行之后，省略掉颇占篇幅但却很容易实现的将邻接矩阵转换为边集数组，并按权值从小到大排序的代码，也就是说，在第5行开始，已经有了结构为edge，数据内容是上图的右图的一维数组edges。

2．第5～7行，声明一个数组parent，并将它的值都初始化为0。

3．第8～17行，开始对边集数组做循环遍历，开始时，i=0。

4．第10行，调用了第19～25行的函数Find，传入的参数是数组parent和当前权值最小边(v4,v7)的 begin:4。因为parent中全都是0所以传出值使得n=4。

5．第11行，同样作法，传入(v4,v7)的 end:7。传出值使得m=7。

6．第12～16行，很显然n与m不相等，因此parent[4]=7。此时parent数组值为{0,0,0,0,7,0,0,0,0}，并且打印得到“(4,7)7”。此时已经将边(v4,v7)纳入到最小生成树中，如下图所示。

8．再次执行10～16行，此时i=2，edge[2]得到边(v0,v1)，n=0，m=1，parent[0]=1，打印结果为“(0,1)10”，此时parent数组值为{1,0,8,0,7,0,0,0,0}，此时边(v4,v7)、(v2,v8)和(v0,v1)已经纳入到最小生成树，如下图：

9．当i=3、4、5、6时，分别将边(v0,v5)、(v1,v8)、(v3,v7)、(v1,v6)纳入到最小生成树中，如图下图所示。此时parent数组值为{1,5,8,7,7,8,0,0,6}，怎么去解读这个数组现在这些数字的意义呢？

从上图的右下方的图i=6的粗线连线可以得到，其实是有两个连通的边集合A与B中纳入到最小生成树中的，如下图所示。当parent[0]=1，表示v0和v1已经在生成树的边集合A中。此时将parent[0]=1的1改为下标，由par-ent[1]=5，表示v1和v5在边集合A中，par-ent[5]=8表示v5与v8在边集合A中，par-ent[8]=6表示v8与v6在边集合A中，par-ent[6]=0表示集合A暂时到头，此时边集合A有v0、v1、v5、v8、v6。我们查看parent中没有查看的值，parent[2]=8表示v2与v8在一个集合中，因此v2也在边集合A中。再由parent[3]=7、par-ent[4]=7和parent[7]=0可知v3、v4、v7在另一个边集合B中。

 10．当i=7时，第10行，调用Find函数，会传入参数edges[7].begin=5。此时第21行，parent[5]=8>0，所以f=8，再循环得par-ent[8]=6。因parent[6]=0所以Find返回后第10行得到n=6。而此时第11行，传入参数edges[7].end=6得到m=6。此时n=m，不再打印，继续下一循环。这就是说，因为边(v5,v6)使得边集合A形成了环路。因此不能将它纳入到最小生成树中，如上图所示。

 11．当i=8时，与上面相同，由于边(v1,v2)使得边集合A形成了环路。因此不能将它纳入到最小生成树中，如上图所示。

 12．当i=9时，边(v6,v7)，第10行得到n=6，第11行得到m=7，因此parent[6]=7，打印“(6,7)19”。此时parent数组值为{1,5,8,7,7,8,7,0,6}，如下图所示。

 13．此后边的循环均造成环路，最终最小生成树即为下图所示。

克鲁斯卡尔（Kruskal）算法的实现定义：

假设N=(V,{E})是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}}，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。

此算法的Find函数由边数e决定，时间复杂度为$O(loge)$，而外面有一个for循环e次。所以克鲁斯卡尔算法的时间复杂度为$O(eloge)$。

$\color{red}{克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大\\的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。}$

六、最短路径

最短路径：对于非网图来说，，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；对于网图来说，最短路径是指两顶点之间经过的边上权值之和最少的路径，并且称路径上的第一个顶点是源点，最后一个顶点是终点。

6.1 迪杰斯特拉（Dijkstra）算法

迪杰斯特拉算法是一个按路径长度递增的次序产生最短路径的算法，其大致思路：
比如下图

该算法并不是一下子就求出了v0到v8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到想要的结果。
算法的代码实现
首先构建邻接矩阵：

#define MAXVEX 9
#define INFINITY 65535
typedef int  /* 用于存储最短路径下标的数组 */
Patharc[MAXVEX];                       
typedef int  /* 用于存储到各点最短路径的权值和 */
ShortPathTable[MAXVEX];                
/* Dijkstra算法，求有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v] */
/* P[v]的值为前驱顶点下标，D[v]表示v0到v的最短路径长度和。 */
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
    int v, w, k, min;
    /* final[w]=1表示求得顶点v0至vw的最短路径 */
    int final[MAXVEX];                          
    /* 初始化数据 */
    for (v = 0; v < G.numVertexes; v++)         
    {
        /* 全部顶点初始化为未知最短路径状态 */
        final[v] = 0;                           
        /* 将与v0点有连线的顶点加上权值 */
        (*D)[v] = G.arc[v0][v];                 
        /* 初始化路径数组P为-1 */
        (*P)[v] = -1;                           
    }
    /* v0至v0路径为0 */
    (*D)[v0] = 0;                               
    /* v0至v0不需要求路径 */
    final[v0] = 1;                              
    /* 开始主循环，每次求得v0到某个v顶点的最短路径 */
    for (v = 1; v < G.numVertexes; v++)
    {
        /* 当前所知离v0顶点的最近距离 */
        min=INFINITY;                           
        /* 寻找离v0最近的顶点 */
        for (w = 0; w < G.numVertexes; w++)     
         {
            if (!final[w] && (*D)[w] < min)
            {
                k=w;
                /* w顶点离v0顶点更近 */
                min = (*D)[w];                  
            }
        }
        /* 将目前找到的最近的顶点置为1 */
        final[k] = 1;                           
        /* 修正当前最短路径及距离 */
        for (w = 0; w < G.numVertexes; w++)     
        {   
            /* 如果经过v顶点的路径比现在这条路径的长度短的话 */
            if (!final[w] && (min + G.arc[k][w] < (*D)[w]))
            {                                   
                /* 说明找到了更短的路径，修改D[w]和P[w],修改当前路径长度 */
                (*D)[w] = min + G.arc[k][w];    
                (*P)[w]=k;
            }
        }
    }
}

代码详解：

1．程序开始运行，第4行final数组是为了v0到某顶点是否已经求得最短路径的标记，如果v0到vw已经有结果，则fi-nal[w]=1。

2．第5～10行，是在对数据进行初始化的工作。此时final数组值均为0，表示所有的点都未求得最短路径。D数组为{65535,1,5,65535,65535,65535,65535,65535,65535}。因为v0与v1和v2的边权值为1和5。P数组全为0，表示目前没有路径。

3．第11行，表示v0到v0自身，权值和结果为0。D数组为{0,1,5,65535,65535,65535,65535,65535,65535}。第12行，表示v0点算是已经求得最短路径，因此final[0]=1。此时final数组为{1,0,0,0,0,0,0,0,0}。此时整个初始化工作完成。

4．第13～33行，为主循环，每次循环求得v0与一个顶点的最短路径。因此v从1而不是0开始。

5．第15～23行，先令min为65535的极大值，通过w循环，与D[w]比较找到最小值min=1，k=1。

6．第24行，由k=1，表示与v0最近的顶点是v1，并且由D[1]=1，知道此时v0到v1的最短距离是1。因此将v1对应的final[1]设置为1。此时final数组为{1,1,0,0,0,0,0,0,0}。

7．第25～32行是一循环，此循环甚为关键。它的目的是在刚才已经找到v0与v1的最短路径的基础上，对v1与其他顶点的边进行计算，得到v0与它们的当前最短距离，如下图所示。因为min=1，所以本来D[2]=5，现在v0→v1→v2=D[2]=min+3=4，v0→v1→v3=D[3]=min+7=8，v0→v1→v4=D[4]=min+5=6，因此，D数组当前值为{0,1,4,8,6,65535,65535,65535,65535}。而P[2]=1，P[3]=1，P[4]=1，它表示的意思是v0到v2、v3、v4点的最短路径它们的前驱均是v1。此时P数组值为：{0,0,1,1,1,0,0,0,0}。

 8．重新开始循环，此时v=2。第15～23行，对w循环，注意因为final[0]=1和fi-nal[1]=1，由第18行的!final[w]可知，v0与v1并不参与最小值的获取。通过循环比较，找到最小值min=4，k=2。

9．第24行，由k=2，表示已经求出v0到v2的最短路径，并且由D[2]=4，知道最短距离是4。因此将v2对应的final[2]设置为1，此时final数组为：{1,1,1,0,0,0,0,0,0}
。
10．第25～32行。在刚才已经找到v0与v2的最短路径的基础上，对v2与其他顶点的边，进行计算，得到v0与它们的当前最短距离，如下图所示。因为min=4，所以本来D[4]=6，现在v0→v2→v4=D[4]=min+1=5，v0→v2→v5=D[5]=min+7=11，因此，D数组当前值为：{0,1,4,8,5,11,65535,65535,65535}。而原本P[4]=1，此时P[4]=2，P[5]=2，它表示v0到v4、v5点的最短路径它们的前驱均是v2。此时P数组值为：{0,0,1,1,2,2,0,0,0}。

11．重新开始循环，此时v=3。第15～23行，通过对w循环比较找到最小值min=5，k=4。

12．第24行，由k=4，表示已经求出v0到v4的最短路径，并且由D[4]=5，知道最短距离是5。因此将v4对应的final[4]设置为1。此时final数组为：{1,1,1,0,1,0,0,0,0}。

13．第25～32行。对v4与其他顶点的边进行计算，得到v0与它们的当前最短距离，如下图所示。因为min=5，所以本来D[3]=8，现在v0→v4→v3=D[3]=min+2=7，本来D[5]=11，现在v0→v4→v5=D[5]=min+3=8，另外v0→v4→v6=D[6]=min+6=11，v0→v4→v7=D[7]=min+9=14，因此，D数组当前值为：{0,1,4,7,5,8,11,14,65535}。而原本P[3]=1，此时P[3]=4，原本P[5]=2，此时P[5]=4，另外P[6]=4，P[7]=4，它表示v0到v3、v5、v6、v7点的最短路径它们的前驱均是v4。此时P数组值为：{0,0,1,4,2,4,4,4,0}。

  4．之后的循环就完全类似了。得到最终的结果，如图7-7-11所示。此时final数组为：{1,1,1,1,1,1,1,1,1}，它表示所有的顶点均完成了最短路径的查找工作。此时D数组为：{0,1,4,7,5,8,10,12,16}，它表示v0到各个顶点的最短路径数，比如D[8]=1+3+1+2+3+2+4=16。此时的P数组为：{0,0,1,4,2,4,3,6,7}，这串数字可能略为难理解一些。比如P[8]=7，它的意思是v0到v8的最短路径，顶点v8的前驱顶点是v7，再由P[7]=6表示v7的前驱是v6，P[6]=3，表示v6的前驱是v3。这样就可以得到，v0到v8的最短路径为v8←v7←v6←v3←v4←v2←v1←v0，即v0→v1→v2→v4→v3→v6→v7→v8。

其实最终返回的数组D和数组P，是可以得到v0到任意一个顶点的最短路径和路径长度的。例如v0到v8的最短路径并没有经过v5，但我们已经知道v0到v5的最短路径了。由D[5]=8可知它的路径长度为8，由P[5]=4可知v5的前驱顶点是v4，所以v0到v5的最短路径是v0→v1→v2→v4→v5。也就是说，通过迪杰斯特拉（Dijkstra）算法解决了从某个源点到其余各顶点的最短路径问题。从循环嵌套可以很容易得到此算法的时间复杂度为O(n^2)。

如果还需要知道如v3到v5、v1到v7这样的任一顶点到其余所有顶点的最短路径怎么办呢？此时简单的办法就是对每个顶点当作源点运行一次迪杰斯特拉（Dijkstra）算法，等于在原有算法的基础上，再来一次循环，此时整个算法的时间复杂度就成了O(n^3)。

6.2 弗洛伊德（Floyd）算法

Floyd算法原理

先定义两个二维数组D[3][3]和P[3][3]，D代表顶点到顶点的最短路径权值和的矩阵。P代表对应顶点的最小路径的前驱矩阵，用来存储路径。在未分析任何顶点之前，将D命名为D-1，其实它就是初始的图的邻接矩阵。将P命名为P-1，初始化为图中所示的矩阵。

分析所有的顶点经过v0后到达另一顶点的最短路径。因为只有三个顶点，因此需要查看v1→v0→v2，得到D-1[1][0]+D-1[0][2]=2+1=3。D-1[1][2]表示的是v1→v2的权值为5，我们发现D-1[1][2]>D-1[1][0]+D-1[0][2]，通俗的话讲就是v1→v0→v2比直接v1→v2距离还要近。所以我们就让D-1[1][2]=D-1[1][0]+D-1[0][2]=3，同样的D-1[2][1]=3，于是就有了D0的矩阵。因为有变化，所以P矩阵对应的P-1[1][2]和P-1[2][1]也修改为当前中转的顶点v0的下标0，于是就有了P0。也就是说D0[v][w]=min{D-1[v][w],D-1[v][0]+D-1[0][w]}

接下来，其实也就是在D0和P0的基础上继续处理所有顶点经过v1和v2后到达另一顶点的最短路径，得到D1和P1、D2和P2完成所有顶点到所有顶点的最短路径计算工作。

Floyd算法的代码实现
针对下图的左网图准备两个矩阵$D_{-1}$和$P_{-1}$，$D_{-1}$就是网图的邻接矩阵，$P_{-1}$初设为$P[i][j]=j$这样的矩阵，它主要用来存储路径。

代码如下，注意因为是求所有顶点到所有顶点的最短路径，因此Pathmatirx和ShortPathTable都是二维数组。

typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
/* Floyd算法，求网图G中各顶点v到其余顶点w最短路径P[v][w]及带权长度D[v][w] */
void ShortestPath_Floyd(MGraph G, Pathmatirx *P, ShortPathTable *D)
{
    int v, w, k;
    /* 初始化D与P */
    for (v = 0; v < G.numVertexes; ++v)         
       for (w = 0; w < G.numVertexes; ++w)
        {
           /* D[v][w]值即为对应点间的权值 */
           (*D)[v][w] = G.matirx[v][w];        
           /* 初始化P */
           (*P)[v][w] = w;                     
        }
    }
    for (k = 0; k < G.numVertexes; ++k)
    {
        for (v = 0; v < G.numVertexes; ++v)
        {
            for (w = 0; w < G.numVertexes; ++w)
            {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w])
                {                               
                    /* 如果经过下标为k顶点路径比原两点间路径更短 */
                    /* 将当前两点间权值设为更小的一个 */
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    /* 路径设置经过下标为k的顶点 */
                    (*P)[v][w] = (*P)[v][k];    
                }
            }
        }
    }
}

1．程序开始运行，第4～11行就是初始化了D和P，使得它们成为上图的两个矩阵。从矩阵也得到，v0→v1路径权值是1，v0→v2路径权值是5，v0→v3无边连线，所以路径权值为极大值65535。

2．第12～25行，是算法的主循环，一共三层嵌套，k代表的就是中转顶点的下标。v代表起始顶点，w代表结束顶点。

3．当K=0时，也就是所有的顶点都经过v0中转，计算是否有最短路径的变化。可惜结果是，没有任何变化，如下图所示。

4．当K=1时，也就是所有的顶点都经过v1中转。此时，当v=0时，原本D[0][2]=5，现在由于D[0][1]+D[1][2]=4。因此由代码的第20行，二者取其最小值，得到D[0][2]=4，同理可得D[0][3]=8、D[0][4]=6，当v=2、3、4时，也修改了一些数据，请参考下图左图中虚线框数据。由于这些最小权值的修正，所以在路径矩阵P上，也要作处理，将它们都改为当前的P[v][k]值，见代码第21行。

5．接下来就是k=2一直到8结束，表示针对每个顶点做中转得到的计算结果，当然，我们也要清楚，D0是以D-1为基础，D1是以D0为基础，……，D8是以D7为基础，就像我们曾经说过的七个包子的故事，它们是有联系的，路径矩阵P也是如此。最终当k=8时，两矩阵数据如下图所示。

至此，最短路径就算是完成了，可以看到矩阵第v0行的数值与迪杰斯特拉（Dijkstra）算法求得的D数组的数值是完全相同，都是{0,1,4,7,5,8,10,12,16}。而且这里是所有顶点到所有顶点的最短路径权值和都可以计算出。

那么如何由P这个路径数组得出具体的最短路径呢？以v0到v8为例，从图7-7-16的右图第v8列，P[0][8]=1，得到要经过顶点v1，然后将1取代0得到P[1][8]=2，说明要经过v2，然后将2取代1得到P[2][8]=4，说明要经过v4，然后将4取代2得到P[4][8]=3，说明要经过v3，……，这样很容易就推导出最终的最短路径值为v0→v1→v2→v4→v3→v6→v7→v8。

求最短路径的显示代码:

for (v = 0; v < G.numVertexes; ++v)
{
    for (w = v + 1; w < G.numVertexes; w++)
    {
        printf("v%d-v%d weight: %d ", v, w, D[v][w]);
        /* 获得第一个路径顶点下标 */
        k = P[v][w];                
        /* 打印源点 */
        printf(" path: %d", v);     
        /* 如果路径顶点下标不是终点 */
        while (k != w)              
        {
            /* 打印路径顶点 */
            printf(" -> %d", k);    
            /* 获得下一个路径顶点下标 */
            k = P[k][w];            
        }
        /* 打印终点 */
        printf(" -> %d\n", w);      
    }
    printf("\n");
}

$弗洛伊德（Floyd）算法时间复杂度为O(n^3)，适合求所有顶点至所有顶点的最短路径问题。$

七、拓扑排序

7.1 拓扑排序介绍

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为AOV网（ActivityOn Vertex Network）。AOV网中的弧表示活动之间存在的某种制约关系。比如演职人员确定了，场地也联系好了，才可以开始进场拍摄。另外就是AOV网中不能存在回路。

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1，v2，……，vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列。

上图这样的AOV网的拓扑序列不止一条。序列v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 是一条拓扑序列，而v0 v1 v4 v3 v2 v7 v6 v5 v8 v10 v9 v12 v11 v14 v13 v15 v16也是一条拓扑序列。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环（回路）的AOV网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环（回路），不是AOV网。

7.2　拓扑排序算法

对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

由于拓扑排序的过程中，需要删除顶点，所以邻接表会更加方便。为AOV网构建一个邻接表。考虑到算法过程中始终要查找入度为0的顶点，所以在原来顶点表结点结构中，增加一个入度域in，结构为：in|data|first|edge

因此对于上图的AOV网，我们可以得到如下的邻接表数据结构：

在拓扑排序算法中，涉及的结构代码如下：

/* 边表结点 */
typedef struct EdgeNode          
{
    /* 邻接点域，存储该顶点对应的下标 */
    int adjvex;                  
    /* 用于存储权值，对于非网图可以不需要 */
    int weight;                  
    /* 链域，指向下一个邻接点 */
    struct EdgeNode *next;       
} EdgeNode;
/* 顶点表结点 */
typedef struct VertexNode        
{
    /* 顶点入度*/
    int in;                      
    /* 顶点域，存储顶点信息 */
    int data;                    
    /* 边表头指针 */
    EdgeNode *firstedge;         
} VertexNode, AdjList[MAXVEX];
typedef struct
{
    AdjList adjList;
    /* 图中当前顶点数和边数 */
    int numVertexes,numEdges;    
} graphAdjList, *GraphAdjList;

在算法中，需要辅助的数据结构—栈，用来存储处理过程中入度为0的顶点，目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点。

/* 拓扑排序，若GL无回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR */
Status TopologicalSort(GraphAdjList GL)
{
    EdgeNode *e;
    int i, k, gettop;
    /* 用于栈指针下标 */
    int top = 0;                                       
    /* 用于统计输出顶点的个数 */
    int count = 0;                                     
    /* 建栈存储入度为0的顶点 */
    int *stack;                                        
    stack = (int *)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++)
       if (GL->adjList[i].in == 0)
           /* 将入度为0的顶点入栈 */
           stack[++top] = i;                          
    while (top != 0)
    {
        /* 出栈 */
        gettop = stack[top--];                         
        /* 打印此顶点 */
        printf("%d -> ", GL->adjList[gettop].data);    
        /* 统计输出顶点数 */
        count++;                                       
        /* 对此顶点弧表遍历 */
        for (e = GL->adjList[gettop].firstedge; e; e = e->next)
        {                                              
            k = e->adjvex;
            /* 将k号顶点邻接点的入度减1 */
            if (!(--GL->adjList[k].in))                
                /*若为0则入栈，以便于下次循环输出 */
                stack[++top] = k;                      
        }
    }
    /*如果count小于顶点数，说明存在环 */
    if (count < GL->numVertexes)                       
        return ERROR;
    else
        return OK;
}

1．程序开始运行，第3～7行都是变量的定义，其中stack是一个栈，用来存储整型的数字。

2．第8～10行，作了一个循环判断，把入度为0的顶点下标都入栈，从下图的右图邻接表可知，此时stack应该为：{0,1,3}，即v0、v1、v3的顶点入度为0，如图所示。

3．第12～23行，while循环，当栈中有数据元素时，始终循环。

4．第14～16行，v3出栈得到gettop=3。并打印此顶点，然后count加1。

5．第17～22行，循环其实是对v3顶点对应的弧链表进行遍历，即下图中的灰色部分，找到v3连接的两个顶点v2和v13，并将它们的入度减少一位，此时v2和v13的in值都为1。它的目的是为了将v3顶点上的弧删除。 

 6．再次循环，第12～23行。此时处理的是顶点v1。经过出栈、打印、count=2后，对v1到v2、v4、v8的弧进行了遍历。并同样减少了它们的入度数，此时v2入度为0，于是由第20～21行知，v2入栈，如下图所示。

7．接下来，就是同样的处理方式了。图7-8-6展示了v2 v6 v0 v4 v5 v8的打印删除过程。

8．最终拓扑排序打印结果为3->1->2->6->0->4->5->8->7->12->9->10->13->11。当然这结果并不是唯一的一种拓扑排序方案。

分析整个算法，对一个具有n个顶点e条弧的AOV网来说，第8～10行扫描顶点表，将入度为0的顶点入栈的时间复杂为O(n)，而之后的while循环中，每个顶点进一次栈，出一次栈，入度减1的操作共执行了e次，所以整个算法的时间复杂度为O(n+e)。

八、关键路径

拓扑排序主要是为解决一个工程能否顺序进行的问题，而关键路径是解决工程完成需要的最短时间问题。

AOE网: 在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网为AOE网（Activity On Edge Net-work）。AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。正常情况下，AOE网只有一个源点一个汇点。

关键路径： AOE网路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

8.1 关键路径算法原理

找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径。如果不等，则就不是。

为此，需要定义如下几个参数

• 1. 事件的最早发生时间etv（earliest time ofvertex）：即顶点vk的最早发生时间；
• 1. 事件的最晚发生时间ltv（latest time ofvertex）：即顶点vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期；
• 1. 活动的最早开工时间ete（earliest time ofedge）：即弧ak的最早发生时间；
• 1. 活动的最晚开工时间lte（latest time ofedge）：即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间。

由1和2可以求得3和4，然后再根据ete[k]是否与lte[k]相等来判断ak是否是关键活动。

8.2 关键路径算法

把AOE网转化为邻接表结构，如下图，这里弧链表增加了weight域，用来存储弧的权值。


求事件的最早发生时间etv的过程，就是从头至尾找拓扑序列的过程，因此，在求关键路径之前，需要先调用一次拓扑序列算法的代码来计算etv和拓扑序列列表。为此，首先在程序开始处声明几个全局变量。

int *etv, *ltv;    /* 事件最早发生时间和最迟发生时间数组 */
int *stack2;       /* 用于存储拓扑序列的栈 */
int top2;          /* 用于stack2的指针 */

其中stack2用来存储拓扑序列，以便后面求关键路径时使用。

下面是改进过的求拓扑序列算法

/* 拓扑排序，用于关键路径计算 */
Status TopologicalSort(GraphAdjList GL)
 {
    EdgeNode *e;
    int i, k, gettop;
    /* 用于栈指针下标 */
    int top = 0;                                              
    /* 用于统计输出顶点的个数 */
    int count = 0;                                            
    /* 建栈将入度为0的顶点入栈 */
    int *stack;                                               
    stack = (int *)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++)
       if (0 == GL->adjList[i].in)
           stack[++top] = i;
    /* 初始化为0 */
    top2 = 0;                                                 
    /* 事件最早发生时间 */
    etv = (int *)malloc(GL->numVertexes * sizeof(int));       
    for (i = 0; i < GL->numVertexes; i++)
        /* 初始化为0 */
        etv[i] = 0;                                           \
    /* 初始化 */
    stack2 = (int *)malloc(GL->numVertexes * sizeof(int));    
    while (top != 0)
    {
        gettop = stack[top--];
        count++;
        /* 将弹出的顶点序号压入拓扑序列的栈 */
        stack2[++top2] = gettop;                              
        for (e = GL->adjList[gettop].firstedge; e; e = e->next)
        {
            k = e->adjvex;
            if (!(--GL->adjList[k].in))
                stack[++top] = k;
            /* 求各顶点事件最早发生时间值 */
            if ((etv[gettop] + e->weight) > etv[k])           
                etv[k] = etv[gettop] + e->weight;
        }
    }
    if (count < GL->numVertexes)
        return ERROR;
    else
        return OK;
}

第11～15行为初始化全局变量etv数组、top2和stack2的过程。第21行就是将本是要输出的拓扑序列压入全局栈stack2中。第27～28行很关键，它是求etv数组的每一个元素的值。比如说，假如已经求得顶点v0对应的etv[0]=0，顶点v1对应的etv[1]=3，顶点v2对应的etv[2]=4，现在需要求顶点v3对应的etv[3]，其实就是求etv[1]+len<v1,v3>与etv[2]+len<v2,v3>的较大值。显然3+5<4+8，得到etv[3]=12，如图所示。在代码中e->weight就是当前弧的长度。

求关键路径的算法代码

/* 求关键路径，GL为有向网，输出GL的各项关键活动 */
void CriticalPath(GraphAdjList GL)
{
    EdgeNode *e;
    int i, gettop, k, j;
    /* 声明活动最早发生时间和最迟发生时间变量 */
    int ete, lte;                                          
    /* 求拓扑序列，计算数组etv和stack2的值 */
    TopologicalSort(GL);                                   
    /* 事件最晚发生时间 */
    ltv = (int *)malloc(GL->numVertexes * sizeof(int));    
    for (i = 0; i < GL->numVertexes; i++)
        /* 初始化ltv */
        ltv[i] = etv[GL->numVertexes - 1];                 
    /* 计算ltv */
    while (top2 != 0)                                      
    {
        /* 将拓扑序列出栈，后进先出 */
        gettop = stack2[top2--];                           
        for (e = GL->adjList[gettop].firstedge; e; e = e->next)
        {                                                  
            /* 求各顶点事件的最迟发生时间ltv值 */
            k = e->adjvex;
            /* 求各顶点事件最晚发生时间ltv */
            if (ltv[k] - e->weight < ltv[gettop])          
                ltv[gettop] = ltv[k] - e->weight;
        }
    }
    /* 求ete，lte和关键活动 */
    for (j = 0; j < GL->numVertexes; j++)                  
    {
        for (e = GL->adjList[j].firstedge; e; e = e->next)
        {
            k = e->adjvex;
            /* 活动最早发生时间 */
            ete = etv[j];                                  
            /* 活动最迟发生时间 */
            lte = ltv[k] - e->weight;                      
            * 两者相等即在关键路径上 */
            if (ete == lte)                                /
                printf("<v%d,v%d> length: %d , ",
                    GL->adjList[j].data, GL->adjList[k].data, e->weight);
        }
    }
}

1．程序开始执行。第5行，声明了ete和lte两个活动最早最晚发生时间变量。

2．第6行，调用求拓扑序列的函数。执行完毕后，全局变量数组etv和栈stack的值如下图所示，top2=10。也就是说，每个事件的最早发生时间已经计算出来了。

  3．第7～9行为初始化全局变量ltv数组，因为etv[9]=27，所以数组ltv当前的值为：{27,27,27,27,27,27,27,27,27,27}

4．第10～19行为计算ltv的循环。第12行，先将stack2的栈头出栈，由后进先出得到gettop=9。根据邻接表中，v9没有弧表，所以第13～18行循环体未执行。

5．再次来到第12行，gettop=8，在第13～18行的循环中，v8的弧表只有一条<v8,v9>，第15行得到k=9，因为ltv[9]-3<ltv[8]，所以ltv[8]=ltv[9]-3=24，如图所示。  

6．再次循环，当gettop=7、5、6时，同理可算出ltv相对应的值为19、13、25，此时ltv值为：{27，27，27，27，27，13，25，19，24，27}

7．当gettop=4时，由邻接表可得到v4有两条弧<v4,v6>、<v4,v7>，通过第13～18行的循环，可以得到ltv[4]=min(ltv[7]-4,ltv[6]-9)=min(19-4,25-9)=15，如图7-9-8所示。

此时可以发现，在计算ltv时，其实是把拓扑序列倒过来进行的。因此可以得出计算顶点vk即求ltv[k]的最晚发生时间的公式是：

$$ltv[k] = \begin{cases} etv[k], & \text{当k=n-1时} \\ min(ltv[j]-len<vk,vj>), & \text{当k<n-1且<vk,vj>∈S[K]时} \end{cases} \\ $$

其中S[K]表示所有从顶点vk出发的弧的集合。比如上图的S4就是和两条弧，en是弧上的权值。

当程序执行到第20行时，相关变量的值如下图所示，比如etv1=3而ltv1=7，表示的意思就是如果时间单位是天的话，哪怕v1这个事件在第7天才开始，也可以保证整个工程的按期完成，可以提前v1事件开始时间，你最早也只能在第3天开始。

8．第20～31行是来求另两个变量活动最早开始时间ete和活动最晚开始时间lte，并对相同下标的它们做比较。两重循环嵌套是对邻接表的顶点和每个顶点的弧表遍历。

9．当j=0时，从v0点开始，有<v0,v2>和<v0,v1>两条弧。当k=2时，ete=etv[j]=etv[0]=0。lte=ltv[k]-e->weight=ltv[2]-len<v0,v2>=4-4=0，此时ete=lte，表示弧<v0,v2>是关键活动，因此打印。当k=1时，ete=etv[j]=etv[0]=0。lte=ltv[k]-e->weight=ltv[1]-len<v0,v1>=7-3=4，此时ete≠lte，因此<v0,v1>并不是关键活动，如图所示。

ete本来是表示活动的最早开工时间，是针对弧来说的。但只有此弧的弧尾顶点vk的事件发生了，它才可以开始，因此ete=etv[k]。而lte表示的是活动的最晚开工时间，但此活动再晚也不能等vj事件发生才开始，而必须要在vj事件之前发生，所以lte=ltv[j]-len。

所以最终，其实就是判断ete与lte是否相等，相等意味着活动没有任何空闲，是关键活动，否则就不是。

10．j=1一直到j=9为止，做法是完全相同的，关键路径打印结果为“<v0,v2>4,<v2,v3>8,<v3,v4>3,<v4,v7>4,<v7,v8>5,<v8,v9>3,”，最终关键路径如下图所示。

分析整个求关键路径的算法，第6行是拓扑排序，时间复杂度为O(n+e)，第8～9行时间复杂度为O(n)，第10～19行时间复杂度为O(n+e)，第20～31行时间复杂也为O(n+e)，根据我们对时间复杂度的定义，所有的常数系数可以忽略，所以最终求关键路径算法的时间复杂度依然是O(n+e)。