09_图

数据结构和算法

9.1 图的定义

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

• 对于图的定义，需要明确几个注意的地方：

  • 线性表中我们把数据元素叫元素，树中叫结点，在图中数据元素我们则称之为顶点（Vertex）。
  • 线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，而图结构在国内大部分教材中强调顶点集合V要有穷非空。
  • 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

• 无向边

  • 若顶点Vi到Vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶（Vi,Vj）来表示。

• 有向边

  • 若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧（Arc），用有序偶来表示，Vi称为弧尾，Vj称为弧头。

• 简单图

  • 在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

• 无向完全图

  • 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。

• 有向完全图

  • 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。

• 稀疏图和稠密图

  • 这里的稀疏和稠密是模糊的概念，都是相对而言的，通常认为边或弧数小于n*logn（n是顶点的个数）的图称为稀疏图，反之称为稠密图。

• 有些图的边或弧带有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight），带权的图通常称为网（Network)。

• 子图

  • 假设有两个图G1=(V1,E1)和G2=(V2,E2)，如果V2含于V1，E2含于E1，则称G2为G1的子图（Subgraph）

9.2 图的顶点与边之间的关系

• 邻接点、度

  • 对于无向图G=(V,E)，如果边(V1,V2)∈E，则称顶点V1和V2互为邻接点（Adjacent），即V1和V2相邻接。边（V1,V2)依附（incident）于顶点V1和V2，或者说边（V1,V2)与顶点V1和V2相关联。
  • 顶点V的度（Degree）是和V相关联的边的数目，记为TD(V)。
  • 对于有向图G=(V,E)，如果有∈E，则称顶点V1邻接到顶点V2，顶点V2邻接自顶点V1。
  • 以顶点V为头的弧的数目称为V的入度（InDegree）,记为ID(V)，以V为尾的弧的数目称为V的出度(OutDegree)，记为OD(V)，因此顶点V的度为TD(V)=ID(V)+OD(V)。

• 路径

  • 无向图G=(V,E)中从顶点V1到顶点V2的路径（Path）。
  • 如果G是有向图，则路径也是有向的。
  • 路径的长度是路径上的边或弧的数目。
  • 第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle)。
  • 序列中顶点不重复出现的路径称为简单路径，除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

• 连通图

  • 在无向图G中，如果从顶点V1到顶点V2有路径，则称V1和V2是连通的，如果对于图中任意两个顶点Vi和Vj都是连通的，则称G是连通图（ConnectedGraph)。
  • 无向图中的极大连通子图称为连通分量。
    
    • 首先要是子图，并且子图是要连通的；
    • 连通子图含有极大顶点数；
    • 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
  • 在有向图G中，如果对于每一对Vi到Vj都存在路径，则称G是强连通图。
  • 有向图中的极大强连通子图称为有向图的强连通分量。

• 连通图的生成树

  • 所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
  • 如果一个有向图恰有一个顶点入度为0，其余顶点的入度均为1，则是一棵有向树。

9.3 图的存储结构

9.3.1 邻接矩阵（无向图）

• 图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
• 可以设置两个数组，顶点数组为vertex[4]={V0,V1,V2,V3}，边数组arc[4][4]为对称矩阵（0表示不存在顶点间的边，1表示顶点间存在边）。

• 对称矩阵：n阶矩阵的元满足a[i][j]=a[j][i]（0<=i,j<=n)。即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的。

• 作用：

  • 可以判断任意两顶点是否有边。
  • 某个顶点的度是这个顶点Vi在邻接矩阵中第i行（或第i列）的元素之和。

// 邻接矩阵（无向图）
#include <stdio.h>
#define n 4
#define M 4
#define N 4
int main()
{
    int i=0, j=0, k=0;
    int c;
    int Vertex[n];
    int a[M][N];
    printf("请输入顶点： ，以-1作为结束标志！\n");
    scanf("%d", &c);
    while( c != -1 )
    {
        Vertex[++i] = c;
        Vertex[i] = '\0';
        scanf("%d", &c);
    }
    printf("请输入顶点之间边的关系： 1表示两个顶点之间有边，0表示两个顶点之间无边。\n");
    for( i=0; i < M; i++ )
    {
        for( j=0; j < N; j++ )
        {
            printf("%d 和 %d 之间的关系为: ", i, j);
            scanf("%d", &a[i][j]);
            printf("%d\n", a[i][j]);
        }
    }
    printf("邻接矩阵（无向图）为： \n");
    for( i=0; i < M; i++ )
    {
        for( j=0; j < N; j++ )
        {
            printf("%d\t", a[i][j]);
            k++;
        }
        if( k%4 == 0 )
        {
            printf("\n");
        }
    }
    return 0;
}

9.3.2 邻接矩阵（有向图）

• 可见顶点数组vertex[4]={V0,V1,V2,V3}，弧数组arc[4][4]也是一个矩阵，但因为是有向图，所以这个矩阵并不对称。
• 顶点Vi的入度为第Vi列的各数之和。
• 顶点Vi的出度为第Vi行的各数之和。

9.3.3 邻接矩阵（网）

• “∞” 表示一个计算机允许的，大于所有边上权值的值。

9.3.4 邻接表（无向图）

• 把数组和链表结合一起来存储，称为邻接表（AdjacencyList）。
  
  • 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。
  • 图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。

// 邻接表（无向图）
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct {
    int adjvex; //该边的另一个顶点的位置 
    struct ArcNode *nextarc; //指向下一条边 
} ArcNode;
typedef struct{
    int data; // 顶点的值 
    ArcNode *firstarc; // 指向第一条依附该顶点的边的指针 
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
    AdjList vertices; //顶点数组 
    int vexnum, arcnum;
} ALGraph;
//定位函数 
int LocateVex(ALGraph G, int v)
{
    int i=0;
    for( i=0; i < G.vexnum; i++ )
    {
        if( v == G.vertices[i].data ) 
            return i;
    } 
}
void CreateUDG( ALGraph G )
{
    ArcNode *p,*q;
    int i, j, k, v1, v2;
    printf("分别输入顶点个数和边的数目：\n");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    printf("分别输入各个顶点值：\n");
    for( i=0; i < G.vexnum; i++ )
    {
        scanf("%d", &G.vertices[i].data);
        G.vertices[i].firstarc = NULL;  //初始化 
    } 
    printf("分别输入各条边的两个顶点：\n");
    for( k=0; k < G.arcnum; k++ )
    {
        scanf("%d%d", &v1, &v2);
        //定位 
        i = LocateVex(G,v1);
        j = LocateVex(G,v2);
        //申请一个结点
        p = (ArcNode*)malloc(sizeof(ArcNode)); 
        //赋值
        p->adjvex = j;
        p->nextarc = NULL; 
        //连接结点
        p->nextarc = G.vertices[i].firstarc; 
        G.vertices[i].firstarc = p;
        q = (ArcNode*)malloc(sizeof(ArcNode));
        q->adjvex = i;
        q->nextarc = NULL;
        q->nextarc = G.vertices[j].firstarc;
        G.vertices[j].firstarc = q;
    }
}
//输出邻接表 
void PrintUDG(ALGraph G)
{
    int i, j;
    for( i=0; i < G.vexnum; i++ )
    {
        printf("%d:", i);
        ArcNode *p;
        p = G.vertices[i].firstarc;
        while( p != NULL )
        {
            printf("->%d", p->adjvex);
            p = p->nextarc;
        }
        printf("\n");
    }
}
int main()
{
    ALGraph G;
    CreateUDG(G);
    PrintUDG(G);
    return 0;
}

9.3.5 邻接表（有向图）

• 把顶点当弧尾建立的邻接表，可以得到每个顶点的出度。
• 为了确定顶点的入度或以顶点为弧头的弧，可以建立一个有向图的逆邻接表。

9.3.6 邻接表（网）

• 对于带权值的网图，可以在边表结点定义中再增加一个数据域来存储权值即可。

• 代码实现

9.3.7 十字链表（有向图的优化）

• 将邻接表和逆邻接表结合起来的十字链表（Orthogonal List)

• 代码实现

9.3.8 邻接多重表（无向图的优化）

• 如果在无向图的应用中，关注的重点是顶点的话，那么邻接表是不错的选择。但如果我们更关注的是边的操作，比如对已经访问过的边做标记，或者删除某一条边等操作，适合用邻接多重表。

• 其中iVex和jVex是与某条边依附的两个顶点在顶点表中的下标。iLink指向依附顶点iVex的下一条边，jLink指向依附顶点jVex的下一条边。即在邻接多重表里，边表存放的是一条边，而不是一个顶点。

• 代码实现

9.3.9 边集数组

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

// 边集数组
#include <stdio.h>
#define VertexNum 4
#define EdgesNum  4
int main()
{
    int i=0, j=0, k=0, n=0, m=0;
    int c;
    int Vertex[VertexNum];
    int Begin[EdgesNum];
    int End[EdgesNum];
    int Weight[EdgesNum];
    // 存储顶点信息
    printf("请输入顶点： ，以-1作为结束标志！\n");
    scanf("%d", &c);
    while( c != -1 )
    {
        Vertex[++i]  = c;
        Vertex[i] = '\0'; 
        scanf("%d", &c);
    }
    // 存储边的begin数值
    for( j=0; j < EdgesNum; j++ )
    {
        printf("请输入第 %d 条边的起点下标begin：\n", j);
        scanf("%d", &Begin[j]);
    }
    // 存储边的end数值
    for( k=0; k < EdgesNum; k++ )
    {
        printf("请输入第 %d 条边的终点下标end：\n", k);
        scanf("%d", &End[k]);
    }   
    // 存储边的weight数值
    for( n=0; n < EdgesNum; n++ )
    {
        printf("请输入第 %d 条边的权值weight：\n", n);
        scanf("%d", &Weight[n]);
    }   
    // 打印边集数组
    printf("边集数组信息为： 起点下标 终点下标 权值\n");
    for( m=0; m < EdgesNum; m++ )
    {
        printf("Edges[%d]\t%d\t %d\t %d\n", m, Begin[m], End[m], Weight[m]);
    }
    return 0;
}

9.4 图的遍历

9.4.1 深度优先遍历

• 深度优先遍历（DepthFirstSearch)，也称为深度优先搜索，简称为DFS。
• 深度优先遍历其实就是一个递归的过程，整个遍历过程就像是一棵树的前序遍历。

9.4.2 马踏棋盘算法（骑士周游问题）

• 题目要求

  • 国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次，最终使得“马”走遍棋盘64个方格。
  • 编写代码，实现马踏棋盘的操作，要求用1~64来标注“马”移动的路径。
  • 对于在n*n的棋盘上，当n>=5且为偶数的时候，以任意点作起点都有解。

• 回溯法：一般和递归可以很好的搭配使用，还有深度优先搜索。

• 哈密尔顿路径：图G中的哈密尔顿路径指的是经过图G中每个顶点，且只经过一次的一条轨迹。如果这条轨迹是一条闭合的路径（从起点出发不重复地遍历所有点后仍能回到起始点），那么这条路径称为哈密尔顿回路。

// 马踏棋盘算法 
#include <stdio.h>
#include <time.h>
#define X 8
#define Y 8
int chess[X][Y];
//找到基于(x,y)位置的下一个可走的位置
int nextxy(int *x, int *y, int count)
{
    switch(count)
    {
        case 0:
            if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 )
            {
                *x += 2;
                *y -= 1;
                return 1;
            }
            break;
        case 1:
            if( *x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 )
            {
                *x += 2;
                *y += 1;
                return 1;
            }
            break;
        case 2:
            if( *x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 )
            {
                *x += 1;
                *y -= 2;
                return 1;
            }
            break;
        case 3:
            if( *x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0 )
            {
                *x += 1;
                *y += 2;
                return 1;
            }
            break;
        case 4:
            if( *x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0 )
            {
                *x -= 2;
                *y -= 1;
                return 1;
            }
            break;
        case 5:
            if( *x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 )
            {
                *x -= 2;
                *y += 1;
                return 1;
            }
            break;
        case 6:
            if( *x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0 )
            {
                *x -= 1;
                *y -= 2;
                return 1;
            }
            break;
        case 7:
            if( *x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0 )
            {
                *x -= 1;
                *y += 2;
                return 1;
            }
            break;
        default:
            break;
    }
    return 0;
}
void print()
{
    int i, j;
    for( i=0; i < X; i++ )
    {
        for( j=0; j < Y; j++ )
        {
            printf("%2d\t", chess[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
//深度优先遍历棋盘
//(x,y)为位置坐标
//tag是标记变量，每走一步，tag+1
int TravelChessBoard(int x, int y, int tag)
{
    int x1=x, y1=y, flag=0, count=0;
    chess[x][y] = tag;
    if( X*Y == tag )
    {
        //打印棋盘
        print();
        return 1;
    }
    //找到马的下一个可走的坐标(x1,y1)，如果找到flag=1，否则为0
    flag = nextxy(&x1, &y1, count);
    while( 0==flag && count<7 )
    {
        count ++;
        flag = nextxy(&x1, &y1, count);
    }
    while( flag )
    {
        if( TravelChessBoard(x1, y1, tag+1) )
        {
            return 1;
        }
        //找到马的下一个可走的坐标(x1,y1)，如果找到flag=1，否则为0
        x1 = x;
        y1 = y;
        count++;
        flag = nextxy(&x1, &y1, count);
        while( 0==flag && count<7 )
        {
            count ++;
            flag = nextxy(&x1, &y1, count);
        }
    }
    if( 0 == flag )
    {
        chess[x][y] = 0;
    }
    return 0;
}
int main()
{
    int i, j;
    clock_t start, finish;
    start = clock();
    for( i=0; i < X; i++ )
    {
        for( j=0; j < Y; j++ )
        {
            chess[i][j] = 0;
        }
    }
    if( !TravelChessBoard(2, 0, 1) )
    {
        printf("抱歉，马踏棋盘失败了！\n");
    }
    finish = clock();
    printf("\n本次计算一共耗时： %f秒\n\n", (double)(finish-start)/CLOCKS_PER_SEC);
    return 0;
}

9.4.3 广度优先遍历

• 广度优先遍历（BreadthFirstSearch），又称为广度优先搜索，简称BFS。
• 可以利用队列来实现。类似树的层序遍历。

9.5 构造最小生成树

9.5.1 普利姆(Prim)算法

• 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能的小。
• 普利姆算法以某顶点为起点，逐步找各个顶点上最小权值的边来构建最小生成树。

// Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
{
    int min, i, j, k;
    int adjvex[MAXVEX];  // 保存相关顶点下标
    int lowcost[MAXVEX];  // 保存相关顶点间边的权值
    lowcost[0] = 0;  // V0作为最小生成树的根开始遍历，权值为0
    adjvex[0] = 0;  // V0第一个加入
    // 初始化操作
    for( i=0; i < G.numVertexes; i++ )
    {
        lowcost[i] = G.arc[0][i];  // 将邻接矩阵第0行所有权值先加入数组
        adjvex[i] = 0;  // 初始化全部先为V0的下标
    }
    // 真正构造最小生成树的过程
    for( i=0; i < G.numVertexes; i++ )
    {
        min = INFINITY; // 初始化最小权值为65535等不可能数值
        j = 1;
        k = 0;
        // 遍历全部顶点
        while( j < G.numVertexes )
        {
            // 找出lowcost数组已存储的最小权值
            if( lowcost[j] != 0 && lowcost[j] < min )
            {
                min = lowcost[j];
                k = j;  // 将发现的最小权值的下标存入k，以待使用
            }
            j++;
        }
        // 打印当前顶点边中权值最小的边
        printf("(%d, %d)", adjvex[k], k);
        lowcost[k] = 0;  // 将当前顶点的权值设置为0，表示此顶点已经完成任务，进行下一个顶点的遍历
        // 邻接矩阵k行逐个遍历全部顶点
        for( j=1; j < G.numVertexes; j++ )
        {
            if( lowcost[j] != 0 && G.arc[k][j] < lowcost[j] )
            {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
}

9.5.2 克鲁斯卡尔(Kruskal)算法

• 从边出发，直接去找最小权值的边来构建生成树。

// Kruskal算法生成最小生成树
int Find(int *parent, int f)
{
    while( parent[f] > 0 )
    {
        f = parent[f];
    }
    return f;
}
void MiniSpanTree_Kruskal(MGraph G)
{
    int i, n, m;
    Edge edges[MAGEDGE];  // 定义边集数组
    int parent[MAXVEX];   // 定义parent数组用来判断边与边是否形成环路
    for( i=0; i < G.numVertexes; i++ )
    {
        parent[i] = 0;
    }
    for( i=0; i < G.numEdges; i++ )
    {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if( n!= m )   // 如果n==m，不满足！
        {
            parent[n] = m;  // 将此边的结尾顶点放入下标为起点的parent数组中，表示此顶点已经在生成树集合中
            printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}

9.6 最短路径

• 在网图和非网图中，最短路径的含义是不同的。
  
  • 网图是两顶点经过的边上权值之和最少的路径。
  • 非网图是两顶点之间经过的边数最少的路径。
• 我们把路径起始的第一个顶点称为源点，最后一个顶点称为终点。

9.6.1 迪杰斯特拉(Dijkstra)算法

• 它并不是一下子求出V0到V8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到结果。

D: 0 1 4 7 5 8 10 12 16
P: 0 0 1 4 2 4 3 6 7
final: 1 1 1 1 1 1 1 1 1

// dijkstra算法求最短路径
#define MAXVEX 9
#define INFINITY 65535
typedef int Patharc[MAXVEX];         // 用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX];  // 用于存储到各点最短路径的权值和
void ShortestPath_Dijkstra(MGragh G, int V0, Patharc *P, ShortPathTable *D)
{
    int v, w, k, min;
    int final[MAXVEX];  // final[w] = 1 表示已经求得顶点V0到Vw的最短路径
    // 初始化数据
    for( v=0; v < G.numVertexes; v++ )
    {
        final[v] = 0;            // 全部顶点初始化为未找到最短路径
        (*D)[V] = G.arc[V0][v];  // 将与V0点有连线的顶点加上权值
        (*P)[V] = 0;             // 初始化路径数组P为0
    }
    (*D)[V0] = 0;   // V0至V0的路径为0
    final[V0] = 1;  // V0至V0不需要路径
    // 开始主循环，每次求得V0到某个v顶点的最短路径
    for( v=1; v < G.numVertexes; v++ )
    {
        min = INFINITY;
        for( w=0; w < G.numVertexes; w++ )
        {
            if( !final[w] && (*D)[w] < min )
            {
                k = w;
                min = (*D)[w];
            }
        }
        final[k] = 1;  // 将目前找到的最近的顶点置1
        for( w=0; w < G.numVertexes; w++ )
        {
            // 如果经过v顶点的路径比现在这条路径的长度短的话，更新
            if( !final[w] && (min+G.arc[k][w] < (*D)[w]) )
            {
                (*D)[w] = min + G.arc[k][w];   // 修改当前路径长度
                (*p)[w] = k;                   // 存放前驱顶点
            }
        }
    }
}

• 时间复杂度O(n^2)

9.6.2 弗洛伊德(Floyd)算法

• 迪杰斯特拉算法求的是一个顶点到所有顶点的最短路径，但弗洛伊德算法是求所有顶点到所有顶点的最短路径。
• 弗洛伊德算法非常简洁优雅。

// 弗洛伊德算法求最短路径
#define MAXVEX 9
#define INFINITY  65535
typedef int Pathmatirx[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
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] = G.matirx[v][w];
            (*P)[v][w] = w;
        }
    }
    // 优美的弗洛伊德算法
    for( k=0; k < G.numVertexes; k++ )
    {
        for( v=0; v < G.numVertexes; v++ )
        {
            if( (*D)[v][w] > (*D)[v][k] + (*D)[k][w] )
            {
                (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                (*P)[v][w] = (*P)[v][k];
            }
        }
    }
}

9.7 拓扑排序

9.7.1 概念

• DAG图
  
  • 一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。
• 活动
  
  • 所有的工程或者某种流程都可以分为若干个小的工程或阶段，我们称这些小的工程或阶段为“活动”。
• AOV网
  
  • 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为AOV网（Active On Vertex Network)。
  • AOV网中的弧表示活动之间存在某种制约关系。
  • AOV网不能存在回路。
• 拓扑序列
  
  • 设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1,V2,......,Vn满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。
• 拓扑排序
  
  • 对同一个有向图构造拓扑序列的过程。

9.7.2 拓扑排序算法

• 对AOV网进行拓扑排序的方法和步骤如下：
  
  • 从AOV网中选择一个没有前驱的顶点（该顶点的入度为0）并且输出它；
  • 从网中删去该顶点，并且删去从该顶点发出的全部有向边；
  • 重复上述两步，直到剩余网中不再存在没有前驱的顶点为止。

• 算法时间复杂度
  
  • 对一个具有n个顶点，e条边的网来说，初始建立入度为零的顶点栈，要检查所有顶点一次，执行时间为O(n)。
  • 排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个表结点被检查一次，因而执行时间是O(n+e)。
  • 所以，整个算法的时间复杂度是O(n+e)。

// 拓扑排序算法
// 边表结点声明
typedef struct EdgeNode
{
    int adjvex;
    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;
// 拓扑排序算法
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
    EdgeNode *e;
    int i, k, gettop;
    int top = 0;     // 用于栈指针下标索引
    int count = 0;   // 用于统计输出顶点的个数
    int *stack;      // 用于存储入度为0的顶点
    stack = (int *)malloc(GL->numVertexes * sizeof(int));
    for( i=0; i < GL->numVertexes; i++ )
    {
        if( 0 == GL->adjList[i].in )
        {
            stack[++top] = i;  // 将入度为0的顶点下标入栈
        }
    }
    while( 0 != top )
    {
        gettop = stack[top--];  // 出栈
        printf("%d -> ", GL->adjList[gettop].data);
        count++;
        for( e=GL->adjList[gettop].firstedge; e; e=e->next )
        {
            k =  e->adjvex;
            // 注意：下边这个if条件是分析整个程序的要点
            // 将k号顶点邻接点的入度为-1，因为它的前驱已经消除
            // 接着判断-1后入度是否为0，如果为0则也入栈
            if( !(--GL->adjList[k].in) )
            {
                stack[++top] = k;
            }
        }
    }
    if( count < GL->numVertexes )  //如果count小于顶点数，说明存在环
    {
        return ERROR;
    }
    else
    {
        return OK;
    }
}

9.8 关键路径

9.8.1 AOE网

• 在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网（Activity On Edge Network)。
• 我们把AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。

9.8.2 几个关键词

• etv(Earliest Time Of Vertex)
  
  • 事件最早发生时间，就是顶点的最早发生时间。
• ltv(Latest Time Of Vertex)
  
  • 事件最晚发生时间，就是每个顶点对应的事件最晚需要开始的时间，如果超出此时间将会延误整个工期。
• ete(Earliest Time Of Edge)
  
  • 活动的最早开工时间，就是弧的最早发生时间。
• lte(Latest Time Of Edge)
  
  • 活动的最晚发生时间，就是不推迟工期的最晚开工时间。

// 关键路径
// 边表结点声明
typedef struct EdgeNode
{
    int adjvex;
    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;
int *etv, *ltv; 
int *stack2;   // 用于存储拓扑序列的栈
int top2;      // 用于stack2的栈顶指针
// 拓扑排序算法
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
    EdgeNode *e;
    int i, k, gettop;
    int top = 0;     // 用于栈指针下标索引
    int count = 0;   // 用于统计输出顶点的个数
    int *stack;      // 用于存储入度为0的顶点
    stack = (int *)malloc(GL->numVertexes * sizeof(int));
    for( i=0; i < GL->numVertexes; i++ )
    {
        if( 0 == GL->adjList[i].in )
        {
            stack[++top] = i;  // 将度为0的顶点下标入栈
        }
    }
    // 初始化etv都为0
    top2 = 0; 
    etv = (int *)malloc(GL->numVertexes * sizeof(int));
    for( i=0; i < GL->numVertexes; i++ )
    {
        etv[i] = 0;
    }
    stack2 = (int *)malloc(GL->numVertexes * sizeof(int));
    while( 0 != top )
    {
        gettop = stack[top--];  // 出栈
        printf("%d -> ", GL->adjList[gettop].data);
        count++;
        for( e=GL->adjList[gettop].firstedge; e; e=e->next )
        {
            k =  e->adjvex;
            // 注意：下边这个if条件是分析整个程序的要点
            // 将k号顶点邻接点的入度为-1，因为它的前驱已经消除
            // 接着判断-1后入度是否为0，如果为0则也入栈
            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 )  //如果count小于顶点数，说明存在环
    {
        return ERROR;
    }
    else
    {
        return OK;
    }
}
// 关键路径，GL为有向图，输出GL的各项关键活动
void CriticalPath(GraphAdjList GL)
{
    EdgeNode *e;
    int i, gettop, k, j;
    int ete, lte;
    // 调用改进后的拓扑排序，求出etv和stack2的值
    TopologicalSort(GL);
    // 初始化ltv都为汇点的时间
    ltv = (int *)malloc(GL->numVertexes * sizeof(int));
    for( i=0; i < GL->numVertexes; i++ )
    {
        ltv[i] = etv[GL->numVertexes - 1];
    }
    // 从汇点倒过来逐个计算ltv
    while( 0 != top2 )
    {
        gettop = stack2[top2--];  // 注意，第一个出栈是汇点
        for( e=GL->adjList[gettop].firstedge; e; e=e->next )
        {
            k = e->adjvex;
            if( ltv[k] - e->weight < ltv[gettop] )
            {
                ltv[gettop] = ltv[k] - e->weight;           
            }
        }
    }
    // 通过etv和ltv求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);
            }
        }
    }
}