6.图

图的基本概念

图由顶点集和边集组成，记为，其中表示图中顶点的有限非空集：表示图中顶点之间的关系(边)集合。若，则用表示图中顶点的个数，也称图的阶。，用表示图中边的条数。

图的顶点集一定非空，但边集可以为空，此时图中只有顶点而没有边。

若是有向边(也称弧)的有限集合时，则图为有向图。弧是顶点的有序对，记为，其中是顶点，称为弧尾，称为弧头，称为从到的弧，也称邻接到。

若是无向边(简称边)的有限集合时，则图为无向图。边是顶点的无序对，记为或。可以说和互为邻接点。边依附于和，或称边和相关联。

简单图满足两个必要条件：

  • 不存在重复边；

  • 不存在顶点到自身的边。

    若违反了其中一个条件，则图称为多重图。

 

在无向图中，顶点的度是指依附于顶点的边的条数，记为。无向图的全部顶点的度的和等于边数的倍，因为每条边和两个顶点相关联。

在有向图中，顶点的度分为入度和出度，入度是以顶点为终点的有向边的数目，记为；而出度是以顶点为起点的有向边的数目，记为。顶点的度等于其入度与出度之和，即。有向图的全部顶点的入度之和与出度之和相等，并且等于边数。

 

顶点到顶点之间的一条路径是指顶点序列，关联的边也可理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有个顶点，并且有大于条边，则此图一定有环。

路径的定义：由顶点和相邻顶点序偶构成的边所形成的序列。

在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

从顶点出发到顶点的最短路径若存在，则此路径的长度称为从到的距离。若从到根本不存在路径，则记该距离为无穷。

 

在无向图中，若从顶点到顶点有路径存在，则称和是连通的。若图中任意两个顶点都是连通的，则称图为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。

连通图最少有条边，若，则一定有回路。

非连通情况下边最多的情况：由个顶点构成一个完全图加上一个孤立的顶点，此时再任意加入一条边则变成连通图。边数为。

在有向图中，如果有一对顶点和，从到和从到之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。

有向图强连通情况下边最少的情况：至少需要条边，构成一个环路。

 

设有两个图和是的子集，且是的子图。若有满足，则称其为的生成子图。并非和的任何子集都能构成的子图，因为这样的子集可能不是图，即的子集中的某些边关联的顶点可能不在这个的子集中。

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为，则它的生成树含有条边。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

如果图本来就不是连通的，那么每个子部分若包含它本身的所有顶点和边，则它就是极大连通子图。

 

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

完全图(简单完全图)：在无向图中，任意两个顶点之间都存在边的图称为无向完全图，共有条边；在有向图中，任意两个顶点之间都存在方向相反的两条弧的图称为有向完全图，共有条边。

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图满足时，可以将视为稀疏图。

一个顶点的入度为、其余顶点的入度均为的有向图，称为有向树。

若一个具有个顶点，条边的无向图是一个森林，则该森林中必有棵树。

图的存储及基本操作

存储方式

邻接矩阵法：用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息(即各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。结点数为的图的邻接矩阵是的。将的顶点编号为。若，则，否则。对于带权图而言，若顶点和之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点和不相连，则用来代表这两个顶点之间不存在边。

#define MaxVertexNum 100        // 顶点数目的最大值
typedef char VertexType;        // 顶点的数据类型
typedef int EdgeType;            // 带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];                    // 顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];        // 邻接矩阵，边表
    int vexnum,arcnum;                                // 图的当前顶点数和弧数
}MGraph;

特点：

  • 无向图的邻接矩阵一定是一个对称矩阵(并且唯一)。在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。空间复杂度为——只和顶点数相关，和实际的边数无关。
  • 对于无向图，邻接矩阵的第行(或第列)非零元素(或非元素)的个数正好是顶点的度。
  • 对于有向图，邻接矩阵的第行非零元素(或非元素)的个数正好是顶点的出度；第列非零元素(或非元素)的个数正好是顶点的入度。
  • 用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
  • 稠密图适合使用邻接矩阵的存储表示。
  • 设图的邻接矩阵为(矩阵元素为)，的元素等于由顶点到顶点的长度为的路径的数目。

邻接表法：对图中的每个顶点建立一个单链表，第个单链表中的结点表示依附于顶点的边(对于有向图则是以顶点为尾的弧)，这个单链表就称为顶点的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点：

  • 顶点表结点：由顶点域和指向第一条邻接边的指针构成。

    typedef struct VNode{        // 顶点
    VertexType data;        // 顶点信息
    ArcNode *first;            // 指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];

  • 边表结点：由邻接点域和指向下一条邻接边的指针域构成。

    typedef struct ArcNode{
    int adjvex;                // 该弧所指向的顶点的位置
    struct ArcNode *next;    // 指向下一条弧的指针
    InfoType info;            // 网的边权值
}ArcNode;

typedef struct{
    AdjList vertices;        // 邻接表
    int vexnum,arcnum;        // 图的顶点数和弧数
}ALGraph;

特点：

  • 若为无向图，则所需的存储空间为；若为有向图，则所需的存储空间为。
  • 对于稀疏图，采用邻接表表示将极大地节省存储空间。
  • 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为。若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
  • 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。
  • 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

十字链表：对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。(只适用于存储有向图)

OjziNQ.md.png

  • 弧结点中有个域：

    • 尾域()和头域()分别指示弧尾和弧头这两个顶点在图中的位置；
    • 链域指向弧头相同的下一条弧；
    • 链域指向弧尾相同的下一条弧；
    • 域指向该弧的相关信息。

    这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。

  • 顶点结点中有个域：

    • 域存放顶点相关的数据信息，如顶点名称；
    • 和两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。

    顶点结点之间是顺序存储的。

在十字链表中，容易求得顶点的出度和入度。图的十字链表表示是不唯一的，但一个十字链表表示确定一个图。空间复杂度为。

邻接多重表：(只适用于存储无向图)

Ojz9HS.md.png

  • 边结点：

    • 为标志域，可用以标记该条边是否被搜索过；
    • 和为该边依附的两个顶点在图中的位置；
    • 指向下一条依附于顶点的边；
    • 指向下一条依附于顶点的边；
    • 为指向和边相关的各种信息的指针域。

  • 顶点结点：

    • 域存储该顶点的相关信息；
    • 域指示第一条依附于该顶点的边。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。空间复杂度为。图的邻接多重表表示是不唯一的。

图的基本操作

图的基本操作是独立于图的存储结构的。而对于不同的存储方式，操作算法的具体实现会有着不同的性能。

  • ：判断图是否存在边或。

  • ：列出图中与结点邻接的边。

  • ：在图中插入顶点。

  • ：从图中删除顶点。

  • ：若无向边或有向边不存在，则向图中添加该边。

  • ：若无向边或有向边存在，则从图中删除该边。

  • ：求图中顶点的第一个邻接点，若有则返回顶点号。若没有邻接点或图中不存在，则返回。

  • ：假设图中顶点是顶点的一个邻接点，返回除外顶点的下一个邻接点的顶点号，若是的最后一个邻接点，则返回。

  • ：获取图中边或对应的权值。

  • ：设置图中边或对应的权值为。

    此外，还有图的遍历算法：按照某种方式访问图中的每个顶点且仅访问一次。

图的遍历

图的任一顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组来标记顶点是否被访问过。

图的广度优先遍历

广度优先搜索()类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点，接着由出发，依次访问的各个未访问过的邻接顶点，然后依次访问邻接点的所有未被访问过的邻接顶点，再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。单源最短路径算法和最小生成树算法也应用了类似的思想。

广度优先搜索遍历图的过程是以为起始点，由近至远依次访问和有路径相通且路径长度为的顶点。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

广度优先搜索算法的伪代码如下：

bool visited[MaxVertexNum];            // 访问标记数组
void BFSTraverse(Graph G){            // 对图G进行广度优先遍历
    for(int i=0;i<G.vexnum;++i){
        visited[i]=FALSE;            // 访问标记数组初始化
    }
    InitQueue(Q);                    // 初始化辅助队列Q
    for(int i=0;i<G.vexnum;++i){    // 从0号顶点开始遍历
        if(!visited[i])                // 对每个连通分量调用一次BFS
            BFS(G,i);                // 若该顶点未被访问过，从该顶点开始BFS
    }
}
void BFS(Graph G,int v){            // 从顶点v出发，广度优先遍历图G
    visit(v);                        // 访问初始顶点v
    visited[v]=TRUE;                // 标记已访问
    Enqueue(Q,v);                    // 将顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);                // 队列Q出队一个顶点
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){    // 对出队的顶点的所有邻接点循环
            if(!visited[w]){        // 如果该邻接点未被访问
                visit[w];            // 访问邻接点w
                visited[w]=TRUE;    // 标记该点已访问
                EnQueue(Q,w);        // 对邻接点入队
            }
        }
    }
}

最坏的情况下，空间复杂度为。

采用邻接表存储时，每个顶点都需要搜索一次(入队一次)，故时间复杂度为，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为，算法总的时间复杂度为。

采用邻接矩阵时，查找每个顶点的邻接点所需时间为，算法总的时间复杂度为。

在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树。一给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。

图的深度优先遍历

深度优先搜索()类似于树的先序遍历。基本思想如下：首先访问图中某一起始顶点，然后由出发，访问与邻接且未被访问的任一项点，再访问与邻接且未被访问的任一顶点，重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

深度优先搜索算法的伪代码如下：

bool visited[MaxVertexNum];            // 访问标记数组
void DFSTraverse(Graph G){            // 对图G进行深度优先遍历
    for(int i=0;i<G.vexnum;++i){
        visited[i]=FALSE;            // 访问标记数组初始化
    }
    for(int i=0;i<G.vexnum;++i){    // 从0号顶点开始遍历
        if(!visited[i])                // 对每个连通分量调用一次DFS
            DFS(G,i);                // 若该顶点未被访问过，从该顶点开始DFS
    }
}
void DFS(Graph G,int v){            // 从顶点v出发，深度优先遍历图G
    visit(v);                        // 访问初始顶点v
    visited[v]=TRUE;                // 标记已访问
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){    // w为v的未访问的邻接顶点
        if(!visited[w]){        // 如果该邻接点未被访问
            DFS(G,w);            // 从该顶点开始DFS
        }
    }
}
void DFS_Non_RC(Graph G,int v){        // 深度优先遍历非递归算法
    int w;                            // 顶点序号
    InitStack(S);                    // 初始化栈S
    for(int i=0;i<G.vexnum;++i){
        visited[i]=FALSE;            // 访问标记数组初始化
    }
    Push(S,v);                        // v入栈
    visited[v]=TRUE;                // 标记已访问
    while(!IsEmpty(S)){
        k=Pop(S);                    // 取出栈顶元素
        visit(k);                    // 访问顶点k，将其子结点入栈
        for(w=FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w)){    // w为k的未访问的邻接顶点
            if(!visited[w]){        // 如果该邻接点未被访问
                Push(S,w);            // 入栈
                visited[w]=FALSE;    // 标记已访问
            }
        }
    }
}

图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的序列和序列是唯一的，基于邻接表的遍历所得到的序列和序列是不唯一的。

算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为。

采用邻接表存储时，访问顶点所需的时间为，查找所有顶点的邻接点所需的时间为，算法总的时间复杂度为。

采用邻接矩阵时，查找每个顶点的邻接点所需时间为，算法总的时间复杂度为。

对连通图调用才能产生深度优先生成树，否则产生的将是深度优先生成森林，与类似，基于邻接表存储的深度优先生成树是不唯一的。

利用深度优先遍历可以判断图中是否存在回路。

  • 对于无向图来说，若深度优先遍历过程中遇到了回边，则必定存在环；若一次遍历就能够访问到个顶点和条边，则可断定此图是一棵树。
  • 对于有向图来说，这条回边可能是指向深度优先森林中另一棵生成树上的顶点的弧；但是从有向图的某个顶点出发进行深度优先遍历时，若在结束之前出现一条从顶点到顶点的回边，且在生成树上是的子孙，则有向图必定存在包含顶点和顶点的环。

图的遍历算法可以用来判断图的连通性。

  • 对于无向图来说，若无向图是连通的，则从任一结点出发，仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。调用搜索函数的次数等于该图的连通分量数。
  • 对于有向图来说，若从初始点到图中的每个顶点都有路径，则只需调用一次搜索函数就能够访问到图中的所有顶点，否则不能访问到所有顶点。非强连通分量一次调用搜索函数无法访问到该连通分量的所有顶点。对于强连通图，从任一顶点出发都只需调用一次搜索函数。

图的应用

最小生成树

带权连通无向图的所有生成树中，边的权值之和最小的生成树称为最小生成树。具有以下性质：

  • 最小生成树的树形不唯一。当图中的各边权值互不相等时，的最小生成树是唯一的；若无向连通图的边数比顶点数少，即本身是一棵树时，则的最小生成树就是它本身。
  • 最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的。
  • 最小生成树的边数为顶点数减。
  • 假设是一个带权连通无向图，是顶点集的一个非空子集。若是一条具有最小权值的边，其中，则必存在一棵包含边的最小生成树。基于该性质的最小生成树算法主要有算法和算法，它们都基于贪心算法的策略。
  1. (普里姆)算法：类似于寻找图的最短路径的算法。初始时从图中任取一顶点加入树，此时树中只含有一个顶点，之后选择一个与当前中顶点集合距离最近的顶点，并将该顶点和相应的边加入，每次操作后中的顶点数和边数都增。以此类推，直至图中所有的顶点都并入，得到的就是最小生成树。此时中必然有条边。 时间复杂度为，不依赖于，因此它适用于求解边稠密的图的最小生成树。
  2. (克鲁斯卡尔)算法：按权值的递增次序选择合适的边来构造最小生成树。初始时为只有个顶点而无边的非连通图，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在中不同的连通分量上，则将此边加入，否则舍弃此边而选择下一条权值最小的边。以此类推，直至中所有顶点都在一个连通分量上。 通常采用堆来存放边的集合，因此每次选择最小权值的边只需的时间。此外，由于生成树中的所有边可视为一个等价类，因此每次添加新的边的过程类似于求解等价类的过程，由此可以采用并查集的数据结构来描述，从而构造的时间复杂度为。因此，适合于边稀疏而顶点较多的图。

简记：电信(点线)

最短路径问题

当图是带权图时，把从一个顶点到图中其余任意一个顶点的一条路径(可能不止一条)所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。带权有向图的最短路径问题一般可分为两类：

  • 单源最短路径：求图中某一顶点到其他各顶点的最短路径。
  • 每对顶点间的最短路径。

解决单源最短路径问题的算法：算法(适用于无权图)

#define INFINITY 0x7fffffff
void BFS_MIN_Distance(Graph G,int u){
    for(int i=0;i<G.vexnum;++i){
        d[i]=INFINITY;                // 初始化路径长度
        path[i]=-1;                    // 最短路径从哪个顶点来
    }
    visited[u]=TRUE;d[u]=0;            // 标记u已访问，且距离自身距离为0
    EnQueue(Q,u);
    while(!isEmpty(Q)){
        DeQueue(Q,u);                // 队列Q出队一个顶点u
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){    // 对出队的顶点u的所有邻接点循环
            if(!visited[w]){        // 如果该邻接点未被访问
                visited[w]=TRUE;    // 标记该点已访问
                d[w]=d[u]+1;        // 路径长度加一
                path[w]=u;            // 最短路径应从u到w
                EnQueue(Q,w);        // 对邻接点入队
            }
        }
    }
}

解决单源最短路径问题的算法：(迪杰斯特拉)算法

设置一个集合记录已求得的最短路径的顶点，初始时把源点放入，集合每并入一个新顶点都要修改源点到集合中顶点当前的最短路径长度值。在构造的过程中还设置了两个辅助数组：

  • ：记录从源点到其他各顶点当前的最短路径长度，它的初态为：若从到有弧，则为弧上的权值；否则置为。
  • ：表示从源点到顶点之间的最短路径的前驱结点。在算法结束时，可根据其值追溯得到源点到顶点的最短路径。

假设从顶点出发，即，集合最初只包含顶点，邻接矩阵表示带权有向图，表示有向边的权值，若不存在有向边，则为。算法的步骤如下(不考虑对的操作)：(贪心算法)

  1. 初始化：集合初始为，的初始值。
  2. 从顶点集合中选出满足，就是当前求得的一条从出发的最短路径的终点，令。
  3. 修改从出发到集合上任一顶点可达的最短路径长度：若，则更新。
  4. 重复步骤操作共次，直到所有的顶点都包含在中。

时间复杂度为。边上带有负权值时，算法并不适用。

简记：(单源-Dijkstra-顶点)

解决每对顶点间的最短路径问题的算法：(弗洛伊德)算法

递推产生一个阶方阵序列，其中表示从顶点到顶点的路径长度，表示绕行第个顶点的运算步骤。初始时，对于任意两个顶点和，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径。算法描述如下：(动态规划法)

是从顶点到、中间结点是的最短路径的长度，是从顶点到、中间顶点的序号不大于的最短路径的长度。算法是一个迭代的过程，每迭代一次，在从到的最短路径上就多考虑了一个顶点；经过次迭代后，所得到的就是到的最短路径长度，即方阵中就保存了任意一对顶点之间的最短路径长度。

// 准备工作，根据图的信息初始化矩阵A和path
// 核心代码
for(int k=0;k<n;k++)            // 考虑以k为中转点
    for(int i=0;i<n;i++)        // 遍历整个矩阵，i为行号，j为列号
        for(int j=0;j<n;j++)
            if(A[i][j]>A[i][k]+A[k][j]){    // 以k为中转点的路径更短
                A[i][j]=A[i][k]+A[k][j];    // 更新最短路径长度
                path[i][j]=k;                // 中转点
            }

时间复杂度为，空间复杂度为。允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。

有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称图。有向无环图是描述含有公共子式的表达式的有效工具。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间。压缩步骤如下：

  1. 根据表达式画出有向无环图(可以用二叉树来表示)；

    1. 把各个操作数不重复地排成一排；
    2. 标出各个运算符的生效顺序；
    3. 按顺序加入运算符，注意分层。

  2. 找到具有相同树结构的子树，将重复部分删去只保留一个子树，将指向被删去子树的指针指向。

    自底向上逐层检查同层的运算符是否可以合体。

    子树可能为一个单独的根结点，即叶子结点也有可能可以压缩存储。

    父结点的两个指针可以同时指向同一个结点。

拓扑排序

网：若用图表示一个工程，其顶点表示活动，用有向边表示活动必须先于活动进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为网。在网中，活动是活动的直接前驱，活动是活动的直接后继，这种前驱和后继关系具有传递性，且任何活动不能以它自己作为自己的前驱或后继。

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

  • 每个顶点出现且只出现一次。
  • 若顶点在序列中排在顶点的前面，则在图中不存在从顶点到顶点的路径。

每个网都有一个或多个拓扑排序序列。对一个网进行拓扑排序的步骤：

  1. 从网中选择一个没有前驱(入度为)的顶点并输出。

  2. 从网中删除该顶点和所有以它为起点的有向边。

  3. 重复步骤直到当前的网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

    bool TopologicalSort(Graph G){        // 基于邻接表存储结构，indegree[]记录当前顶点入度；print[]记录拓扑序列，初始化为-1
    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);            // 栈顶元素出栈
        print[count++]=i;    // 输出顶点i
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){        // 将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);        // 入度为0入栈
        }
    }
    if(count<G.vexnum)
        return false;        // 排序失败，有回路
    else
        return true;        // 排序成功
}

    时间复杂度为。若采用邻接矩阵，时间复杂度为。

逆拓扑排序的步骤如下：(采用邻接矩阵或逆邻接表更方便)

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

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

  3. 重复步骤直到当前的网为空。

    // 除了和拓扑排序类似的算法外，还可以采用 DFS算法 实现(未实现回路判断)
void DFSTraverse(Graph G){            // 对图G进行深度优先遍历
    for(int i=0;i<G.vexnum;++i){
        visited[i]=FALSE;            // 访问标记数组初始化
    }
    for(int i=0;i<G.vexnum;++i){    // 从0号顶点开始遍历
        if(!visited[i])                // 对每个连通分量调用一次DFS
            DFS(G,i);                // 若该顶点未被访问过，从该顶点开始DFS
    }
}
void DFS(Graph G,int v){            // 从顶点v出发，深度优先遍历图G
    visited[v]=TRUE;                // 标记已访问
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){    // w为v的未访问的邻接顶点
        if(!visited[w]){        // 如果该邻接点未被访问
            DFS(G,w);            // 从该顶点开始DFS
        }
    }
    print(v);                        // 输出顶点v
}

用拓扑排序算法处理网时，应该注意：

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

关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销，称之为用边表示活动的网络，简称网。网和网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，网中的边有权值；网中的边无权值，仅表示顶点之间的前后关系。

网具有以下两个性质：

  • 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
  • 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

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

在网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

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

事件的最早发生时间：从源点到顶点的最长路径长度。事件的最早发生时间决定了所有从开始的活动能够开工的最早时间。计算值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算：

  1. 初始时，令。
  2. 输出一个入度为的顶点时，计算它所有直接后继顶点的最早发生时间，若，则，以此类推，直至输出全部顶点。

事件的最迟发生时间：在不推迟整个工程完成的前提下，即保证它的后继事件在其最迟发生时间能够发生时，该事件最迟必须发生的时间。计算值时，按从后往前的顺序进行，可以在逆拓扑排序的基础上计算，在上述拓扑排序中，增设一个栈以记录拓扑序列，拓扑排序结束后从栈顶至栈底便为逆拓扑有序序列：

  1. 初始时，令。
  2. 栈顶顶点出栈，计算其所有直接前驱顶点的最迟发生时间，若，则，以此类推，直至输出全部栈中顶点。

活动的最早开始时间：该活动弧的起点所表示的事件的最早发生时间。若边表示活动，则有。

活动的最迟开始时间：该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边表示活动，则有。

一个活动的最迟开始时间和其最早开始时间的差额：该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称即的活动是关键活动。

求关键路径的算法步骤如下：

  1. 从源点出发，令，按拓扑有序求其余顶点的最早发生时间。
  2. 从汇点出发，令，按逆拓扑有序求其余顶点的最迟发生时间。
  3. 根据各顶点的值求所有弧的最早开始时间。
  4. 根据各顶点的值求所有弧的最迟开始时间。
  5. 求网中所有活动的差额，找出所有的活动构成关键路径。

对于关键路径，需要注意以下几点：

  • 关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
  • 关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。
  • 网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
Last modification：May 26, 2023
© Allow specification reprint
希望能帮到你(＾－＾)V