【数据结构与算法】图的应用

最小生成树——无向连通图的所有生成树中有一棵边的权值总和最小的生成树

拓扑排序 ——由偏序定义得到拓扑有序的操作便是拓扑排序。建立模型是AOV网

关键路径——在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度，路径长度最长的路径叫做关键路径(Critical Path)。

最短路径——最短路径问题是图研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

最小生成树

连通图的【生成树】是包含图中全部顶点的一个 （若图中顶点数为n，则它的生成树含有n-1条边）。

• 构造无向图的生成树

如果无向连通图是一个网，那么它的所有生成树中必有一颗边的权值总和最小的生成树，我们称这颗生成树为【最小生成树】。

2. 性质

• 根据极小连通子图的性质，若砍去最小生成树的一条边，则会使生成树成为非连通图；若给它增加一条边，则会形成回路

• 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。

• •只有连通图才有生成树，非连通图只有生成森林。

  所以在最小生成树中研究的对象是带权的连通的无向图。

3. MST性质——构造性质

构造最小生成树的算法很多，其中多数算法都利用了MST的性质。

假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中u∈U，v∈V-U，则必存在一棵包含边（u,v）的最小生成树。

在生成树的构造过程中，图中n各顶点分属两个集合：

• 已落在生成树上的顶点集：U
• 尚未落在生成树上的顶点集：V-U

接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。（即在上图中，选取v_1到v_2,v_3或v_4之间权值最小的边为v_1->v_3）

下面介绍两种常用的构造最小生成树的算法：普利姆（Prim）和克鲁斯卡尔（Kruskal），他们都利用了最小生成树的性质，都基于贪心算法的策略。一个通用的最小生成树算法：

GENERIC_MST(G){
	T=NULL;
	while T 未形成一棵生成树;
		do 找到一条最小代价边(u, v)并且加入T后不会产生回路;
			T=T U (u, v);
}

通用算法每次加入一条边以逐渐形成一棵生成树，下面介绍两种实现上述通用算法的途径。

Prim算法

从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。此时T中必然有n-1条边。

具体过程如下：

时间复杂度为

【算法思想】

1. 设N=（V,E) 是连通网，TE是N上最小生成树中边的集合。
2. 初始令U={U_0},(U_0∈V)，TE={ }。
3. 在所有u∈U,v∈V-U的边（U,V）∈E中，找一条代价最小的边(u_0,v_0)
4. 将(u_0,v_0)并入集合TE，同时v_0并入U。
5. 重复上述操作直至U=V为止，则T=（V,TE）为N的最小生成树。

【具体操作】

1. 需要两个数组，一个数组标记该结点是否在生成树中，一个数组记录该结点到树的代价，如果没有与树直连，那么代价为∞。如下图，v0为初始结点，其他结点都不在生成树中：

此时其他结点到v0的代价为：

2. 循环遍历所有结点，找到 lowCast 最低的，且还没加入树的顶点（3号顶点），将其加入生成树中。

3. 再次循环遍历，更新还没加入的各个顶点的lowCast值。由于3号结点的加入，此时其他结点到生成树的代价更新为：

依次类推，从v0开始，每一轮都会选择新的顶点，将其放到生成树中，n个顶点就需要n-1轮处理，而每一轮的处理又需要两次循环遍历，即遍历所有的结点，并且处理他们的 lowcost（到生成树的代价），所以每一轮的处理时间复杂度为O(2n)，经过n-1轮处理，那么时间复杂度为O(n^2)，即O(v2)。

【算法过程】

//用邻接矩阵存储图
#define INFINITY INT_MAX    //最大值∞
#define MAX_VERTEX_NUM 20    //最大顶点个数
typedef enum{DG,DN,UDG,UDN} GraphKind;    //{有向图，有向网，无向图，无向网}
typedef struct ArcCell{
    VRType adj;    //权值
    InfoType *info;    //该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
 
typedef struct{
    VertexType vexs[MAX_VERTEX_NUM];    //顶点向量
    AdjMatrix arcs;    //邻接矩阵
    int vexnum,arcnum;    //顶点数和弧数
    GraphKind kind;    //图的种类
}MGraph;
bool isJoin[MAX_VERTEX_NUM]; // 记录顶点是否已加入最小生成树
 
int Locate(MGraph G,VertexType u){
    int k=-1;
    for(int i=0;i<G.vexnum;i++){
        if(G.vexs[i]==u){
            return i;
        }
    }
    return k;
}
 
void MiniSpanTree_PRIM(MGraph G,VertexType u){
    //从第u个顶点出发，构造网G的最小生成树T，输出T的各条边
    //记录从顶点集U到V-U的代价最小的边的辅助数组
    memset(isJoin, false, sizeof(isJoin));    //初始化isJoin数组
    struct{
        VerTexType adjvex;
        VRType lowcost;
    }closedge[MAX_VERTEX_NUM];
    k=Locate(G,u);
    
    for (j=0;j<G.vexnum;++j)
        if(j!=k)    closedge[j]={u,G.arc[k][j].adj};
    closedge[k].lowcost=0;
    for(i=1;i<G.vexnum;i++){
        k=minimum(closedge);    //求出T的下一个结点：第k顶点
        printf("%d %d\n", closedge[k].adjvex, G.vexs[k]);
        isJoin[k]=true;    //标记为已被访问
        closedge[k].lowcost=0;
        for(j=0;j<G.vexnum;++j)
            if(!isJoin[j] && G.arc[k][j].adj<closedge[j].lowcost)    
            //将新结点并入U后重新选择最小边
                close[j]={G.vexs[k],G.arcs[k][j].adj};
    }
 
}

Kruskal算法(构造最小生成树)

每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)，直到所有结点都连通。

具体过程如下：

【算法思想】

1. 设连通网N=（V,E），令最小生成树初始状态只有n个顶点而无边的非连通图T=（V,{ }），每个顶点自成一个连通分量。
2. 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。
3. 依此类推，直至T中所有顶点都在同一连通分量上为止。

【具体操作】

1.初始时，将各条边按权值排序。

2.接着，从上至下检查每条边的两个顶点是否连通（是否属于同一集合），若不连通，那么将两个点相连。

3.如上图的例子所示，下一条是v3和v5，但由于两个顶点已经属于同一个集合，所以跳过这条边，依次类推。

图中有E条边，那么总共需要进行E轮处理，在每一轮处理中，需要通过并查集判断两个顶点是否属于同一个集合，时间复杂度为,那么E轮处理，总的时间复杂度为。

【算法过程】

/*Kruskar算法生成最小生成树*/
void MiniSpanTree_Kruskal(MGraph G){
	int i, n, m;
	Edge edges[MAXEDGE];	//定义边集数组
	int parent[MAXVEX];	//定义一数组用来判断边与边是否形成环路
	/*此处省略将邻接矩阵G转化为边集数组edges并按照权由小到大排序的代码*/
	for(i=0; i<G.numVertexes; i++){
		parent[i] = 0;	//初始化数组为0
	}
	for(i=0; i<G.numVertexes; i++){
		n = Find(parent, edges[i].begin);
		m = Find(parent, edge[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;
}

总结：

• Prim算法与Kruskal算法的比较
  
• 因为无向连通图的最小生成树不一定唯一，所以用不同算法生成的最小生成树可能不同，但当无向连通图的最小生成树唯一时，不同算法生成的最小生成树必定是相同的。因为最小生成树算法都是基于贪心策略的，每次总是选择权值最小且满足条件的边，若各边权值不同，则每次选择的新顶点也是唯一的，所以生成的最小生成树唯一。

最短路径(BFS算法)

最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。但最短路径一定是简单路径，即路径上的各顶点均不互相重复。

最短路径问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

看下面的例子， “G港”是个物流集散中心

经常需要往各个城市运东西怎么运送距离最近?这就是单源最短路径问题。

各个城市之间也需要互相往来，相互之间怎么走距离最近?这就是每对顶点间的最短路径。

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

单源最短路径

（无权图）

无权图可以视为一种特殊的带权图，只是每条边的权值都为1。

在BFS算法中，1号顶点，6号顶点与2号顶点的距离为1

5，3，7与2的距离为2

4，8与2的距离为3

实例：求2号顶点到其他顶点的最短路径：

【算法思想】
在无权图中，BFS保证从起点出发经过最少的边到达目标顶点的路径就是最短路径，因为边不带权或者说权值相等，那么最少边的路径就是最短路径。

对于上图这个无权图，我们若使用BFS遍历上图，以2为起点得到的其中一种遍历顺序是 2 6 7 8。

BFS我们可以看作是以起点开始，一层一层往外访问，规定起点是第0层，即第0层的距离为0，第N层的顶点距起点的距离为N。

【具体过程】

• 第0层：访问2,2到起点对的距离为0。从2号顶点出发，则将2号顶点出队，并且将2号顶点邻接的点的路径长度设为1(d[w]=d[u]+1)，也就是将d[1],d[6]=1，并且将path[1],path[6]=2，表示最短路径从2过来：

• 第1层：访问第0层顶点（2）的邻接点，且这些邻接点之前没有被访问过，即访问1,6，1,6到起点的距离为1。其余依次类推：
  

通过path数组可知，2到8的最短路径为：8<–7<–6<–2

【算法过程】

#define INFINITY INT_MAX    //最大值∞
 
void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;i++){
        d[i] = INT_MAX;    //初始化路径长度
        path[i]=-1;    //最短路径从哪个顶点过来
    }
    d[u] =0;
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)){
        DeQueue(Q,u);
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
            if(!visited[w]){
                d[w]=d[u]+1;    //路径长度+1
                path[w]=u;    //最短路径应从u到w
                visited[w]=TRUE;    //设为以访问标记
                EnQueue(Q,w);    //顶点w入队
            }//if
        }//for
    }//while
}

BFS算法只能用于无权图，对于带权图则不再适用。例如下图，若要求G港到R城的最短路径，用BFS算法得到的最短路径是10，其实从P城再到R城才是最短路径7。

Dijkstra算法就能解决这个问题！

Dijkstra算法（带权图，无权图）

【算法思想】

1. 初始化：先找出从源点v_0到各终点v_k的直达路径（v_0,v_k），即通过一条弧到达的路径。

2. 选择：从这些路径中找出一条长度最短的路径（v_0,u）。

3. 更新：然后对其余的各条路径进行适当调整：

   若在图中存在弧（u,v_k），且（v_0,u）+（u,v_k）<（v_0,v_k），则以路径（v_0,u,v_k）代替（v_0,v_k）。将路径（v_0,u,v_k）加入到S集合

4. 在调整剩余顶点集合T=V-S的各条路径长度中，再找长度最短的路径再加入到S集合中，依此类推，直至集合S=V，集合T为空集

MST性质

【算法步骤】

【具体过程】

1. 首先需要初始化三个数组：

2. 接着循环遍历所有结点，找到还没确定的最短路径，且dist 最小的顶点Vi(final=false,dis[i]最小)，令final[i]=ture。在v1，v2，v3，v4四个顶点中，最小的值是5。

3. 检查所有与v4相邻的顶点，若其final值为false，则更新dist和path的信息。由于v0到v4的路径是5，v4到v1的距离为3，所以找到了从v0到v1的更短的路径，即5+3=8。

4. 现在final=false的顶点当中，路径最小的是7，所以现在处理v3，将final[3]=true。检查可以从v3过去的顶点，若其final=false，则更新dist和path的信息。

继续以上步骤，最后得到：

v0到v2的最短（带权）路径长度为dist[2]=9

通过path[ ]可知，v0到v2的最短路径：v2<–v1<–v4<–v0

时间复杂度为O(n²)即O(|V|²)

因为从 final=false 的顶点中找到dist最小的顶点，并将其设为final[ i ]=false，时间复杂度为O(n)。并且需要更新与该点相邻的final=false的点的信息，若图为邻接矩阵存储，要找到与他相邻的所有的点，就是要扫描该点对应的行，时间复杂度为O(n)，所以每一轮处理需要的时间复杂度为O(n)+O(n)=2O(n)，总共需要n-1轮处理，所以算法的时间复杂度为O(|V|^2)。

【算法过程】

void DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D){
    //求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权长度D[v]
    //若P[v][w]为TRUE，则w为从v0到v当前求得最短路径的顶点
    for(v=0;v<G.vexnum;++v){
        final[v]=FALSE;    D[v]=G.arcs[v0][v];
        for(w=0;w<G.vexnum;++w)    p[v][w]=FALSE;    //设空路径
        if(D[v]<INFINITY){
            P[v][v0]=TRUE;
            p[v][v]=TRUE;
        }
    }
    D[v0]=0;    final[v0]=TRUE;    //初始化，v0顶点属于S集
    //开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集中 
    for(i=1;i<G.vexnum;++i){
        min=INFINITY;    //当前所知离v0顶点的最近距离
        for(w=0;w<G.vexnum;++w)
            if(!final[w]){
                if(D[w]<min){v=w;min=D[w];}    //w顶点离顶点更近
        final[v]=TRUE;
        for(w=0;w<G.vexnum;++w)
            if(!final[w] && (min+G.arcs[v][w])<D[w])){
                D[w]=min+G.arcs[v][w];
                P[w]=P[v];    P[w][w]=TRUE;    //P[w]=P[v]+P[w]
            }
    }
}

Dijkstra算法和Prim算法的区别：

Prim算法适用于带权的连通的无向图，而Dijkstra算法不仅可用于带权连通的无向图，也可用于带权连通的有向图。Prim算法数组记录的是顶点加入到目前生成树的最小代价，dist数组记录的是当前顶点到指定顶点的最短路径的值。

在Prim算法中，数组元素dis[i]表示未访问结点 i 到已访问结点集合的最短距离，所以此时需要len记录最短距离。而Dijkstra算法中，数组元素dis[i]表示未访问结点 i 到源点的最短距离。

若带权图中有负权值的边，那用Dijkstra算法找到的路径可能不是最短路径，所以Dijkstra算法不适用于有负权值的带权图。

但是Floyd算法可以用于负权图！

各顶点间的最短路径

方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次，时间复杂度为O(n^3)

方法二：

Floyd算法（带权图，无权图）

Floyd可以精简的概括为起点，中点与终点，很容易联系到arr[i][k]到arr[k][j]，i 为起点，k为中间点，j为终点。

（从v2到v1的路径为∞，表示从v2到v1没有路径可走）

【算法思想】

1. 逐个顶点试探
2. 从v_i到v_j的所有可能存在的路径中，选出一条长度最短的路径

【具体过程】

1.若允许从v0中转，则v2到v1的路径可变为v2–>v0–>v1，距离为11：

也就是：

广义化则变为：

2. 更新A和path后，矩阵为：

2.若允许在v0，v1中转，在更新的矩阵的基础上，扫描所有的元素，只有A[0][2]满足条件：

更新后的矩阵如下：

3.若允许在v0，v1，v2中转，在更新的矩阵的基础上，扫描所有元素，只有A[1][0]满足条件：

更新后的矩阵如下：

所以从和开始，经过n轮递推，得到和

时间复杂度为O(n³)即O(|V|³)

【算法过程】

void FLOYD(MGraph G,PathMatrix &P[],DistanceMatrix &D){
    //P[v][w]表示最短路径，D[v][w]表示带权路径长度
    //若P[v][w][u]为TRUE,则u是从v到w当前求得的最短路径
    for(v=0;v<G.vexnum;++v)
        for(w=0;w<G.vexnum;++w){
            D[v][w]=G.arcs[v][w];
            for(u=0;u<G.vexnum;++u)    P[v][w][u]=FALSE;
                if(D[v][w]<INFINITY){
                    P[v][w][u]=TRUE;p[v][w][w]=TRUE; 
                }
        }
    for(u=0;u<G.vexnum;++u)
        for(v=0;v<G.vexnum;++v)
            for(w=0;w<G.vexnum;++w)
                if(D[v][u]+D[u][w]<D[v][w]){
                    D[v][w]=D[v][u]+D[u][w];
                    for(i=0;i<G.vexnum;++i)
                        P[v][w][i]=P[v][u][i] || P[u][w][i];    //更新最短路径
                }
}

进一步我们考虑更加复杂的例子：

前面的步骤相同，直接考虑以v2作为中转：

可以更新的最短路径如下：

注意：A[0][3]的路径可以转化为A[0][2]+A[2][3]，其实A[2][3]之间是没有直接路径的，但是在v2进行中转 是在v0，v1也允许中转 的基础上进行的，之前已经更新了从v2到v3的路径,即：

v2->v1->v3

所以A[0][2]+A[2][3]实际经过的路径是v0->v2->v1->v3

以此类推，最终得到：

如何通过矩阵找完成的路径，例如，找v0到v4的最短路径，p[0][4]=3，v0->v3->v4:

由于p[0][4]不为-1，所以中间还有其他顶点。

依次看v0->v3和v3->v4，由于v0->v3的path[0][3]=2，说明中间还经过了其他结点:

v0->v2->v3。

p[3][4]=-1，说明中间没有经过任何顶点。

继续拆解v0->v2->v3，v0->v2的path[0][2]=-1，中间不经过其他顶点，v2->v3的path[2][3]=1，说明中间还经过了其他顶点，v2->v1->v3

继续拆解v2->v1->v3，v2->v1的path[2][1]=-1，中间不经过其他顶点，v1->v3的path[1][3]=-1，中间不经过任何顶点，至此拆解完毕，最后得到从v0到v4的完整路径为：
v0->v2->v1->v3->v4

Floyd算法可以用于负权图，例子如下：

但是Floyd 算法不能解决带有“负权回路”的图(有负权值的边组成回路)，这种图有可能没有最短路径。例如下图，可以观察到，如果回路走的次数越多，那么其带权路径会越来越小。

总结：

其实也可用 Dijkstra 算法求所有顶点间的最短路径，重复|V|次即可（也就是分别以图的各个顶点作为源顶点，求源顶点到达其他结点的最短路径），总的时间复杂度也是O(|V|^3)

有向无环图（DAG)

顾名思义，无环的有向图，简称DAG图(Directed Acyclic Graph)，常用作描述表达式。

有向无环图常用来描述一个工程或一个系统的进行过程。（通常把计划，施工，生产，程序流程等当成一个工程）。一个工程可以分为若干个子工程，只要完成了这些子工程（活动），就可以导致整个工程的完成。

两种有向无环图：

• 用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网。

• 用一个有向图表示一个工程的各子工程及其相互制约的关系，其中以弧表示活动，顶点表示活动的开始或结束事件，弧的权表示活动持续时间。称这种有向图为边表示活动的网，简称AOE网。事件表示在它之前的活动已经完成，在他之后的活动可以开始。

用AOV网解决拓扑排序问题，用AOV网解决关键路径问题。

AOV网的特点：

• 若从顶点i到顶点 j 之间存在一条有向路径，称顶点 i 是顶点j的前驱，或者称顶点 j 是顶点 i 的后继。
• 若<i,j>是图中的弧，则称顶点 i 是顶点 j 的直接前驱，顶点j 是顶点i 的直接后驱。
• AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

AOE网有以下两个性质：

① 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；

② 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。

拓扑排序

在AOV网没有回路的前提下，我们将全部活动（顶点）排列成一个线性序列，使得若AOV网中有弧<i,j>存在，则在这个序列中，i 一定排在 j 的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序序列排序的算法称为拓扑排序。

拓扑排序的实现

① 从AOV网中选择一个没有前驱(入度为0)的顶点并输出。
② 从网中删除该顶点和所有以它为起点的有向边。
③ 重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

上图所示为拓扑排序过程的示例。每一轮选择一个入度为0的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为 {1,2, 4, 3,5}。

下面介绍一个拓扑排序的重要应用：

检测AOV网中是否存在环

方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。因为环中的顶点都有前驱，无法在此过程中删除。

用AOV网解决拓扑排序问题时，应注意以下问题:

①入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
②若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
③由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

• 每个AOV网的拓扑序列不是唯一的：

  例如下图，可以先准备厨具，也可以先买菜。

• 若一个图中有回路，那么这个图就不能拓扑排序，例如下图，执行到某一步时会发现，当前所有顶点的入度都大于0，拓扑排序无法继续进行。

• 若有向图的拓扑有序序列唯一，则图中入度为0和出度为0的顶点都仅有1个。
• 若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1。(x)

反例：

• 若有向图的拓扑有序序列唯一，并不能唯一确定该图。下面的两个有向无环图中，拓扑序列都为V1,V2,V3,V4。

• 若一个有向图的顶点不能排成一个拓扑序列，表明其中存在一个顶点数目大于1的回路，该回路构成一个强连通分量。

【算法思想】

使用邻接表存储，为了方便找没有前驱的结点，每个顶点加上它的入度信息，删去从该顶点出发的弧，就相当于把该顶点邻接的顶点的入度都减一。同时为了避免删去同一个顶点，设立辅助栈专门存放没有前驱的顶点。

【算法过程】

bool TopologicalSort(Graph G){
	InitStack(S);	//初始化栈，存储入度为0的顶点
	for(int i=0; i<G.vexnum; i++){
		if(indegree[i] == 0){
			Push(S, i);	//将所有入度为0的顶点进栈
		}
	}
	int count = 0;	//计数，记录当前已经输出的顶点数
	while(!IsEmpty(S)){	//栈不空，则存在入度为0的顶点
		Pop(S, i);	//顶点元素出栈
		printf("%d ", i);	//输出顶点i
		count++;
		for(p=G.vertices[i].finstarc; p; p=p->nextarc){
			//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
			v = p->adjvex;
			if(!--indegree[v]){
				Push(S, v);	//入度为0，则入栈
			}
		}
	}
	if(count < G.vexnum){
		return false;	//输出顶点少了，有向图中有回路，排序失败
	}else{
		return true;	//拓扑排序成功
	}
}

若采用邻接表，由于该算法中，每一个顶点都会被处理一次，每一条边也会被遍历一次，所以时间复杂度为O(|V|+|E|)，若采用邻接矩阵，把所有的边都遍历一遍，其实就是扫描整个邻接矩阵，所以时间复杂度为O(|V|^2)。

上面是基于BFS算法的拓扑排序，当然也可以基于DFS算法。因为图中无环，则由图中某点出发进行深度优先搜索遍历时，最先退出 DFS 函数的顶点即出度为零的顶点，是拓扑有序序列中最后一个顶点。由此，按退出 DFS 函数的先后记录下来的顶点序列(如同求强连通分量时 finished 数组中的顶点序列)即为逆向的拓扑有序序列。

*逆拓扑排序

逆拓扑排序和拓扑排序的步骤是一样的，只是每一次删除的是出度为0的顶点

具体过程如下：

① 从AOV网中选择一个没有后继(出度为0)的顶点并输出。

② 从网中删除该顶点和所有以它为终点的有向边。

③ 重复①和②直到当前的AOV网为空。

对于逆拓扑排序，不同的存储结构对逆拓扑排序的时间复杂度影响很大。因为删除某一个顶点，也需要删除指向这个顶点的边。若采用邻接表，要找到指向一个顶点的边，就意味着需要遍历整个表。而采用邻接矩阵，只需要遍历该点对应的列即可。

可以使用逆邻接表，邻接表中，每个结点的边表保存的是从这个结点出来的边的信息，而逆邻接表中，每个结点的边表是指向结点的边的信息。

可以用DFS算法实现逆拓扑排序：

#define MAX_VERTEX_NUM 100
bool visited[MAX_VERTEX_NUM]; //是否已被访问过
void DFSTraverse(Graph G){    //对图进行深度优先遍历
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G,v);
}
//用栈递归
void DFS(Graph G,int v){    //从顶点v出发，深度优先遍历图G
    int w;
    visited[v]=TRUE;
    for(w=FirstNeighbor(G,v);w>=0;w=Neighbor(G,v,w))
        if(!visited[w]){
            DFS(G,w);
        }
    print(v);    //各个顶点的信息在退栈时输出
}
//对于逆拓扑排序，各个顶点的信息在退栈时输出，那么也可以想到使用DFS实现拓扑排序的思想：
//在DFS调用过程中设定一个时间标记，当DFS调用结束时，对各结点计时，进而按结束时间从大到小排序，可以得到一个拓扑序列

递归过程如下：

① 以0号顶点作为入口，调用DFS函数，并把0号顶点的visited[ ]设为true：

② 从0号顶点出发，找到第一个与其邻接的顶点，也就是1号顶点，且1号顶点此时没有被访问过，进入下一级的DFS函数：

③ 依次类推，访问到4号顶点后，与4号相邻的顶点都被访问过了，所以不用执行更深一层的DFS了，直接将4号顶点打印输出。

④ 回溯到3号顶点，3号顶点也找不到与之相邻，且没有被访问过的顶点，所以直接打印输出3号顶点。1号和0号顶点同理。所以现在打印输出了4，3，1，0

⑤递归结束：

⑥ 继续回到for循环，找到下一个没有被访问的顶点，即2号顶点：

⑦ 将2号顶点入栈，由于其没有未访问过的邻接点，所以不需要进入更深层的DFS，直接输出打印2号顶点：

得到逆拓扑排序：4，3，1，0，2

和拓扑排序相同，拓扑排序和逆拓扑排序序列可能是不唯一的，若图中有环，则不存在拓扑排序/逆拓扑排序序列。

逆拓扑排序如何检测图中是否有环呢？

除了用 visited[ ]标记已访问的元素外，可以再增加一个flag[ ]数组判断当前结点是否还在递归栈中。

① 每次递归结束后，将当前结点flag[v]=0,也就是回溯。

② 如果某次访问遇到了visited[v]=1的点，判断flag[v]是否等于1（flag[v]=1），若是的话，说明环路存在。例如下图，递归到2号结点时，2号结点访问3号结点，发现其visited[3]=1，并且flag[3]=1，说明3还在递归栈中，则说明下图存在环路。

改进代码如下:

#define MAX_VERTEX_NUM 100
bool visited[MAX_VERTEX_NUM]; //是否已被访问过
bool flag[MAX_VERTEX_NUM];  //是否孩子递归栈中
void DFSTraverse(Graph G){    //对图进行深度优先遍历  
    for(int v=0; v<G.vexnum; ++v) {  
        visited[v] = FALSE;  
        flag[v] = FALSE;  
    }  
    for(int v=0; v<G.vexnum; ++v)  
        if(!visited[v])  
            DFS(G, v);  
} 
void DFS(Graph G, int v){    //从顶点v出发，深度优先遍历图G  
    int w;  
    visited[v] = TRUE;  
    flag[v] = TRUE; // 标记v在栈中  
    for(w=FirstNeighbor(G, v); w>=0; w=Neighbor(G, v, w)) { 
        if(!visited[w]){  
            DFS(G, w);  
        } else if(flag[w]) { // 如果w已被访问且仍在栈中，则存在环路  
            printf("存在环路！\n"); // 或者你可以设置一个全局变量来记录这个信息  
            return; // 可以选择立即返回或继续遍历（取决于你的需求）  
        }  
    }
    flag[v] = FALSE; // 在退栈时设置v不在栈中  
    print(v); // 各个顶点的信息在退栈时输出  
}

关键路径

在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始；网中也仅存在一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。

对于AOE网，我们关心两个问题：

（1）完成正向工程至少需要多少时间？

（2）哪些活动式影响工程进度的关键？

这样的问题可以归结为求解关键路径问题——

关键路径——从源点到汇点路径长度最长的路径

路径长度——路径上各活动持续时间（弧的权值）之和

完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。

如何确定关键路径，需要定义4个描述量：

由若干个关键活动所组成的这条路径就是关键路径。那么，我们如何根据这些描述量取确定关键路径呢？

例题：

最后，关于关键路径的几点讨论：

• 若网中有几条关键路径，要加快珍格格工程进度，则需加快同时在几条关键路径上的关键活动。
• 如果一个活动处于所有的关键路径上，那么提高这个活动的速度，就能缩短珍格格工程的完成时间。
• 处于所有的关键路径上的活动完成时间不能缩短太多，否则会是原来的关键路径变成不是关键路径。这是，必须重新寻找关键路径。