图的应用--最小生成树、最短路径、拓扑排序、关键路径

2019-02-27 本文已影响0人 1nvad3r

1 最小生成树(minimum spanning tree)

(1)基本概念
生成树的概念：
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
最小生成树的概念：
带权连通图中代价最小的生成树。

构造最小生成树的算法有许多，基本原则是：
尽可能选取权值最小的边，但不能构成回路；
选取n-1条边构成最小生成树。

(2)Prim算法
假设 G=(V，E)为一网图，其中 V 为网图中所有顶点的集合，E 为网图中所有带权边的集合。设置两个新的集合 U 和 T，其中集合 U 用于存放 G 的最小生成树中的顶点，集合 T 存放 G 的最小生成树中的边。令集合 U 的初值为 U={ $v_1$ }(假设构造最小生成树时，从顶点 $v_1$ 出发)，集合 T 的初值为 T={}。

①算法思想
从所有u∈U,v∈V-U的顶点中，选取具有最小权值的边(u,v)，将顶点v加入到集合U中，将边(u,v)加入到集合T中，如此不断重复，直到U=V时，最小生成树构建完毕，这时集合T中包含了最小生成树的所有边。
Prim算法的时间复杂度为 $O(n^2)$ ，与网中的边数无关，因此适用于求边稠密的网的最小生成树。

Prim算法
下图演示了从出发，一步一步把结点k拉到U中。

Prim算法 adjvex 和 lowcost 的变化

②算法实现
使用邻接矩阵(二维数组)表示图，两个顶点之间不存在边的权值为机器内允许的最大值。
为便于算法实现，设置一个一维数组closedge[n]，用来保存(V-U)集合中各顶点到U中顶点具有权值最小的边。
数组元素的定义是:

#define MAX_EDGE 30
struct {
    int adjvex;//边所依附于U中权值最小的顶点
    int lowcost;//该边的权值
} closedge[MAX_EDGE];

closedge[j].adjvex = k，表明边 $(v_j,v_k)$ 是(V-U)中顶点 $v_j$ 到U中权值最小的边，顶点 $v_k$ 是该边所依附的U中的顶点。
closedge[j].lowcost存放该边的权值。

③算法步骤
1)从V中挑出一个顶点 $v_k$ 加到U中，初始化closedge数组，记录(V-U)中每一个顶点到 $v_k$ 的权值。
从closedge中选择一条权值不为0最小的边 $(v_j,v_k)$ ，然后做：
closedege[j].lowcost = 0; //将 $v_j$ 加入到U中
2)根据新加入的 $v_j$ 更新closedge中每个元素：遍历剩余的(V-U)所有顶点 $v_i$ 到顶点 $v_j$ 的权值是否小于到顶点 $v_k$ 的权值，如果小于则更新数组
closedge[i].adjvex = j;
closedge[i].lowcost = cost(i,j);
3)重复(1)-(2) ，就得到最小生成树。

在 Prim算法中，图采用邻接矩阵存储，所构造的最小生成树用一维数组存储其n-1条边，每条边的存储结构描述：

typedef struct MSTEdge {
    int vex1, vex2;//边所依附的图中两个顶点
    int weight;//边的权值
} MSTEdge;

算法实现：
贪心算法思想：局部最优+调整=全局最优

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30
#define INFINTY 65535//最大值

typedef enum {
    DG, AG, WDG, WAG  //{有向图，无向图，带权有向图，带权无向图}
} GraphKind;

typedef struct {
    GraphKind kind; /* 图的种类标志 */
    int verxtexNum, arcNum; /* 图的当前顶点数和弧数 */
    char vexs[MAX_VEX]; //顶点集合
    int edges[MAX_VEX][MAX_VEX];//邻接矩阵
} MGraph;/* 图的结构定义 */

typedef struct MSTEdge {
    int vex1, vex2;//边所依附的图中两个顶点
    int weight;//边的权值
} MSTEdge;//边的定义

#define MAX_EDGE 30
struct {
    int adjvex;//到U中权值最小的边所依附U的顶点
    int lowcost;//该边的权值
} closedge[MAX_EDGE];//数组下标代表V-U的顶点的编号

MSTEdge *Prim_MST(MGraph *G, int u) {
    //从第u个顶点开始构造G的最小生成树
    MSTEdge *TE;//存放最小生成树n-1条边的数组指针
    int min,k;
    for (int i = 0; i < G->verxtexNum; i++) {//初始化数组closedge
        closedge[i].adjvex = u;//都依附于顶点u
        closedge[i].lowcost = G->edges[i][u];//到顶点u的权值
    }
    closedge[u].lowcost = 0;//把顶点u拉到集合U中
    TE = (MSTEdge *) malloc((G->verxtexNum - 1) * sizeof(MSTEdge));
    for (int i = 0; i < G->verxtexNum - 1; i++) {//循环n-1次，拉顶点到集合U中
        min = INFINTY;
        for (int j = 0; j < G->verxtexNum; j++) {//遍历closedge数组，找到最小权值的边及顶点
            if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) {
                min = closedge[j].lowcost;
                k = j;
            }
        }
        TE[i].vex1 = closedge[k].adjvex;
        TE[i].vex2 = k;
        TE[i].weight = closedge[k].lowcost;
        closedge[k].lowcost = 0;//把顶点k拉到U中
        for (int i = 0; i < G->verxtexNum; i++) { //修改closedge中各个元素的值
            if (G->edges[i][k] < closedge[i].lowcost) {
                closedge[i].lowcost = G->edges[i][k];
                closedge[i].adjvex = k;
            }
        }
    }
    return TE;
}

(3)Kruskal算法
①算法思想
设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是其最小生成树。
初值U=V,TE={}。
对G中的边按权值大小从小到大依次选取。
选取权值最小的边 $(v_i,v_j)$ ，若边 $(v_i,v_j)$ 加入到TE后形成回路，则舍弃改边，否则将该边并入到TE中。
重复上面步骤，直到TE中包含n-1条边。

Kruskal算法

②算法实现
Kruskal算法实现的关键是：当一条边加入到TE的集合后，如何判断是否构成回路？
简单的解决方法是:定义一个一维数组Vset[n]，存放图T中每个顶点所在的连通分量的编号。
初值：Vset[i] = i，表示每个顶点各自组成一个连通分量，连通分量的编号简单地使用顶点在图中的位置(编号)。
当往T中增加一条边 $(v_i,v_j)$ 时，先检查Vset[i]和Vset[j]的值：
若Vset[i] = Vset[j]：表明 $v_i$ 和 $v_j$ 处在同一个连通分量中，加入此边会形成回路；
若Vset[i] ≠ Vset[j]，则加入此边不会形成回路，将此边加入到生成树的边集中。
加入一条新边后，将两个不同的连通分量合并：将一个连通分量的编号换成另一个连通分量的编号。

MSTEdge *Kruskal_MST(MGraph *G){
    MSTEdge *TE;
    int *Vset = (int *) malloc(G->verxtexNum * sizeof(int));//Vset数组
    for (int i = 0; i < G->verxtexNum; i++) {
        Vset[i] = i;//初始化数组Vset[n]
    }
    MSTEdge * edgelist = getEdgeList(G);
    sort(edgelist);//对表权值按从小到大排序
    int j = 0, k = 0, s1, s2;
    while (j < G->arcNum && k < G->verxtexNum - 1) {
        s1 = Vset[edgelist[j].vex1];
        s2 = Vset[edgelist[j].vex2];
        if (s1 != s2) {//若边的两个顶点的连通分量编号不同，边加入到TE中
            TE[k].vex1 = edgelist[j].vex1;
            TE[k].vex2 = edgelist[j].vex2;
            TE[k].weight = edgelist[j].weight;
            k++;
            for (int i = 0; i < G->verxtexNum; i++) {
                if(Vset[i] == s2) {
                    Vset[i] = s1;//把连通分量改为较小的那一个
                }
            }
        }
        j++;
    }
    free(Vset);
    return TE;
}

时间复杂度为O(eloge + n^2)。

2 最短路径

(1)单源点最短路径 Dijkstra算法

对于给定的有向图G=(V,E)及单个源点 $v_s$ ，求 $v_s$ 到G的其即余各顶点的最短路径。
Dijkstra提出了一种按路径长度递增次序产生最短路径的算法， Dijkstra算法。

基本思想：
从图中的给定源点到其它各个顶点之间客观上应存在一条最短路径，从这组最短路径中，按其长度的递增次序，依次求出到不同顶点的最短路径和路径长度。
即按长度递增的次序生成各顶点的最短路径，即先求出长度最小的一条最短路径，然后求出长度第二小的最短路径，以此类推，直到求出长度最长的最短路径。

算法思想说明：
设给定源点 $V_s$ ，S为已求得最短路径的终点集，开始时令S={ $V_s$ }。当求得第一条最短路径 $(V_s,V_i)$ 后，S为{ $V_s,V_i$ }。根据以下结论可求下一条最短路径。
设下一条最短路径终点为 $V_j$ ，则 $V_j$ 只有以下某一种情况：
1.源点到终点有直接的弧< $V_s$ , $V_j$ >;
2.从 $V_s$ 出发到 $V_j$ 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是S内某个顶点链接到S外的顶点 $V_j$ 。
若定义一个数组dist[n]，其每个dist[i]分量保存从 $V_s$ 出发中间只经过集合S中的顶点而到达 $V_i$ 的所有路径中长度最小的路径长度值，则下一条最短路径的终点 $V_j$ 必定是不在S中且值最小的顶点，即：
dist[i] = min{dist[k] | $V_k$ ∈ V-S}

算法设计：
如何存放最短路径长度：
用一维数组dist[j]存储，源点 $V_s$ 默认，dist[j]表示 $V_j$ 到 $V_s$ 的路径长度。
如何存放最短路径：
从源点到其它顶点的最短路径有n-1条，一条最短路径用一个一维数组表示，如从顶点0到5的最短路径为为0、2、3、5，表示为path[5]={0,2,3,5}，所有n-1条最短路径可以用二维数组path[][]存储。

算法步骤
①令S={ $V_s$ }，用带权的邻接矩阵表示有向图，对图中每个顶点 $V_i$ 按以下原则置初值：
dist[i] = 0 , i=s
dist[i] = $W_{si}$ ， i≠s且< $V_s,V_i$ >有路径
dist[i] = ， i≠s且< $V_s,V_i$ >没有路径
②选择一个顶点 $V_j$ ，使得：
dist[j] = min{dist[k] } $V_k$ ∈ V-S}
， $V_j$ 就是求得的下一条最短路径终点，将 $V_j$ 并入到S中。
③对V-S中的每个顶点 $V_k$ ，修改dist[k],方法是：
若dist[j] + $W_{jk}$ < dist[k],则修改为：dist[k] = dist[j] + $W_{jk}$
④ 重复②，③，直到S=V为止。

算法实现：
用带权的邻接矩阵表示有向图，对Prim算法略加改动就成了Dijkstra算法，将Prim算法中求每个顶点 $V_k$ 的lowcost值用dist[k]代替即可。
设数组path[n]保存从 $V_s$ 到其它顶点的最短路径。若path[i]=k，表示从 $V_s$ 到 $V_i$ 的最短路径中 $V_i$ 的前一个顶点为 $V_k$ 。
设数组final[n]，标识一个顶点是否已加入S中。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30
#define INFINITY 25535
typedef enum {
    DG, AG, WDG, WAG  //{有向图，无向图，带权有向图，带权无向图}
} GraphKind;
typedef struct {
    GraphKind kind; /* 图的种类标志 */
    int verxtexNum, arcNum; /* 图的当前顶点数和弧数 */
    char vexs[MAX_VEX]; //顶点集合
    int edges[MAX_VEX][MAX_VEX];//邻接矩阵
} MGraph;/* 图的结构定义 */

typedef enum {
    TRUE, FALSE
} boolean;

boolean final[MAX_VEX];
int path[MAX_VEX], dist[MAX_VEX];

void dijkstraPath(MGraph *G, int v) {  //从图G中的顶点v出发到其余各顶点的最短路径
    int m,min;
    for (int i = 0; i < G->verxtexNum; i++) {//各数组的初始化
        path[i] = v;
        final[i] = FALSE;
        dist[i] = G->edges[v][i];
    }
    //设置S={v}
    dist[v] = 0;
    final[v] = TRUE;
    for (int i = 0; i < G->verxtexNum - 1; i++) {//其余n-1个顶点
        while(final[m] == TRUE) {//找不在S中的顶点
            m++;
        }
        min = INFINITY;
        for (int i = 0; i < G->verxtexNum; i++) {//求出当前最小的dist[i]值
            if (final[i] == FALSE && dist[m] < min) {
                min = dist[m];
                m = i;
            }
        }
        final[m] = TRUE;
        for (int i = 0; i < G->verxtexNum; i++) {//修改dist和path数组的值
            if (final[i] == FALSE && dist[m] + G->edges[m][i] < dist[i]) {
                dist[i] = dist[m] + G->edges[m][i];
                path[i] = m;
            }
        }
    }
}

从 Vo 到其余各顶点的最短路径，以及运算过程中dist数组的变化状况，如下所示:

时间复杂度 $O(n^2)$ 。

(2)每一对顶点间的最短路径 Floyd算法

用Dijkstra算法重复对每一个顶点求最短路径，时间复杂度 $O(n^3)$ 。Floyd提出了另一种算法，形式步骤更为简单，时间复杂度仍是 $O(n^3)$ 。

算法思想：
设顶点集S(初值为空)，用数组A的每个元素A[i][j]保存从 $V_i$ 只经过S中的顶点到达 $V_j$ 的最短路径长度，其思想是：
①初始时令S={}，A[i][j]的赋初值方式是
A[i][j] = 0 , i = j时
A[i][j] = $W_{ij}$ , i ≠ j且 $V_i,V_j$ 有路径
A[i][j] = , i ≠ j时且 $V_i,V_j$ 没有路径
②将图中一个顶点且 $V_k$ 加入到S中，修正A[i][j]的值，因为从 $V_i$ 只经过S中的顶点 $V_k$ 到达 $V_j$ 的路径长度可能比原来不经过 $V_k$ 的路径更短，修改方法是：
A[i][j] = min{A[i][j],(A[i][k] + A[k][j])}
③重复②，直到G的所有顶点都加入到S中为止。

算法实现：
※定义二维数组Path[n][n]，元素Path[i][j]保存从 $V_i$ 到 $V_j$ 的最短路径所经过的顶点。
※若Path[i][j] = k，从 $V_i$ 到 $V_j$ 经过 $V_k$ ，最短路径序列是 $(V_i,\cdots,V_k,\cdots,V_j)$ ，则路径子序列： $(V_i,\cdots,V_k)$ 和 $(V_k,\cdots,V_j)$ 一定是从 $V_i$ 到 $V_k$ 和从 $V_k$ 到 $V_j$ 的最短路径。从而可以根据Path[i][k]和Path[k][j]的值再找到该路径上所经过的其它顶点，依此类推。
※初始化为Path[i][j] = -1，表示从 $V_i$ 到 $V_j$ 不经过任何S中的顶点。当某个顶点 $V_k$ 加入到S中后使A[i][j]变小时，令Path[i][j] = k。

下面是 Floyd 算法的一个例子，给出算法过程
初始A中为权值，Path中全为-1，S为{}
先把 $V_0$ 拉到S中，观察其余结点有没有经过 $V_0$ 使路径更短。从 $V_2$ 到 $V_1$ 经过 $V_0$ 路径为7，更改A[2][1] = 7，Path[2][1] = 0。
以此类推。

Floyd算法过程
V0到V1 :路径是{ 0, 1 } ，长度是2 ;
V0到V2 :路径是{ 0, 1, 2 } ，长度是6 ;
V1到V0 :路径是{ 1, 2, 0 } ，长度是9 ;
V1到V2 :路径是{ 1, 2 } ，路径长度是4 ;
V2到V0 :路径是{ 2, 0 } ，路径长度是5 ;
V2 到 V1 :路径是{ 2, 0,1}，路径长度是 7 ;

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30
typedef struct {
    int verxtexNum, arcNum; /* 图的当前顶点数和弧数 */
    char vexs[MAX_VEX]; //顶点集合
    int edges[MAX_VEX][MAX_VEX];//邻接矩阵
} MGraph;/* 图的结构定义 */

int A[MAX_VEX][MAX_VEX];
int Path[MAX_VEX][MAX_VEX];
void floydPath (MGraph *G) {
    for (int i = 0; i < G->verxtexNum; i++) {//各数组的初始化
        for (int j = 0; j < G->verxtexNum; j++) {
            A[i][j] = G->edges[i][j];
            Path[i][j] = -1;
        }
    }
    for (int i = 0; i < G->verxtexNum; i++) {//如果i到k经过j距离更短的话，更改A和Path
        for (int j = 0; j < G->verxtexNum; j++) {
            for (int k = 0; k < G->verxtexNum; k++) {
                if (A[i][j] + A[j][k] < A[i][k]) {
                    A[i][k] = A[i][j] + A[j][k];
                    Path[i][k] = j;
                }
            }
        }
    }
}

3 拓扑排序

一个工程都可分为若干个称为活动的子工程，各个子工程受到一定的条件约束：
某个子工程必须开始于另一个子工程完成之后；
整个工程有一个起点和一个重点。
对工程的活动加以抽象：图中顶点表示活动，有向边表示活动之间的优先关系，这样的有向图称为AOV网(Activity On Vertex Network)。
在AOV网中，若有有向边<i,j>，则i是j的直接前驱，j是i的直接后继。
AOV网不能有环。
检查方法：对有向图的顶点进行拓扑排序，若所有顶点都在其拓扑有序序列中，则无环。

有向图的拓扑排序：
构造AOV网中顶点的一个拓扑线性序列 $(v_1,v_2,\cdots,v_n)$ ，使得该线性序列不仅保持原来有向图中顶点之间的优先关系，而且对原图中没有优先关系的顶点之间也建立一种人为的优先关系。

算法思想：
①在AOV网中选择一个没有前驱的顶点且输出；
②在AOV网中删除该顶点以及从该顶点出发的所有有向边；
③重复①、②，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)。

拓扑排序过程

算法实现说明
采用正邻接链表作为AOV网的存储结构；
设立堆栈，用来暂存入度为0的顶点；
删除顶点以它为尾的弧，弧头顶点的入度减1。

算法实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30
typedef enum {
    DG, AG, WDG, WAG
} GraphKind;

typedef struct LinkNode {
    int adjvex;//邻接点在头结点数组中的位置(下标)
    int weight;//权值
    struct LinkNode *nextarc;//指向下一个表结点
} LinkNode;/*表结点类型定义 */

typedef struct VexNode {
    char data; // 顶点信息
    int indegree; //入度
    LinkNode *firstarc; // 指向第一个表结点
} VexNode;/* 顶点结点类型定义 */

typedef struct {
    GraphKind kind;/*图的种类标志 */
    int vexnum;//顶点数
    VexNode AdjList[MAX_VEX];//邻接表
} ALGraph;/* 图的结构定义 */

void countIndegree(ALGraph *G) {
    LinkNode *p;
    for (int i = 0; i < G->vexnum; i++) {//顶点入度初始化
        G->AdjList[i].indegree = 0;
    }
    for (int i = 0; i < G->vexnum; i++) {
        p = G->AdjList[i].firstarc;
        while (p != NULL) {//顶点入度统计
            G->AdjList[p->adjvex].indegree++;
            p = p->nextarc;
        }
    }
}

int topologicSort(ALGraph *G, int topol[]) {
    //顶点的拓扑序列保存在一维数组topol中
    int stack[MAX_VEX];
    int top = -1, count = 0, boolean, no,vexNo;
    LinkNode *p;
    countIndegree(G);
    for (int i = 0; i < G->vexnum; i++) {
        if (G->AdjList[i].indegree == 0) {
            stack[++top] = G->AdjList[i].data;
        }
    }
    do {
        if (top == -1) {
            boolean = 0;
        } else {
            no = stack[top--];//栈顶元素出栈
            topol[count++] = no;//记录顶点序列
            p = G->AdjList[no].firstarc;
            while (p != NULL) {//删除以顶点为尾的弧
                vexNo = p->adjvex;
                G->AdjList[vexNo].indegree--;
                if (G->AdjList[vexNo].indegree == 0) {
                    stack[++top] = vexNo;
                }
                p = p->nextarc;
            }
        }
    } while (boolean == 0);
    if(count < G->vexnum) {
        return -1;
    } else {
        return 1;
    }
}

算法分析：
设 AOV 网有 n 个顶点，e 条边，则算法的主要执行是:
统计各顶点的入度:时间复杂度是 O(n+e) ;
入度为 0 的顶点入栈:时间复杂度是 O(n) ;
拓扑排序过程:顶点入栈和出栈操作执行 n 次，入度减 1 的操作共执行 e 次，时间复杂度是 O(n+e) ;
因此，整个算法的时间复杂度是 O(n+e) 。

4 关键路径

AOE(Activity On Edge)是边表示活动的有向无环图。顶点表示事件(Event)，每个事件表示在其前的所有活动已经完成，其后的活动可以开始；弧表示活动，弧上的权值表示相应活动所需的时间或费用。
由于 AOE 网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为源点到终点的最大路径长度。
具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动。关键路径长度是整个工程所需的最短工期。

利用AOE 网进行工程管理时要需解决的主要问题是:
①计算完成整个工程的最短路径。
②确定关键路径，以找出哪些活动是影响工程进度的关键。

设 $v_0$ 是起点，从 $v_0$ 到 $v_i$ 的最长路径长度称为事件 $v_i$ 的最早发生时间，即是以 $v_i$ 为尾的所有活动的最早发生时间。若活动 $a_i$ 是弧<j, k>，持续时间是 dut(<j, k>)
e(i):表示活动 $a_i$ 的最早开始时间；
l(i):在不影响进度的前提下，表示活动 $a_i$ 的开始时间；
则l(i) - e(i)表示活动 $a_i$ 的时间余量，若l(i) - e(i) = 0，表示活动 $a_i$ 是关键活动。
ve(i):表示事件 $v_i$ 的最早发生时间，即从起点到顶点 $v_i$ 的最长路径长度；
vl(i):表示事件 $v_i$ 的最晚发生时间。
则有以下关系：

最早发生时间 ve(j)的计算:
源点事件的最早发生时间设为 0;除源点外，只有进入顶点 vj 的所有弧所代表的活动全部结束后，事件 vj 才能发生。即只有 vj 的所有前驱事件 vi 的最早发生时间 ve(i)计算出来后，才能计算 ve(j) 。
方法是:对所有事件进行拓扑排序，然后依次按拓扑顺序计算每个事件的最早发生时间。

最晚发生时间 vl(j)的计算:
只有 vj 的所有后继事件 vk 的最晚发生时间 vl(k)计算出来后，才能计算 vl(j) 。
方法是:按拓扑排序的逆顺序，依次计算每个事件的最晚发生时间。

求 AOE 中关键路径和关键活动
算法思想
1 利用拓扑排序求出 AOE 网的一个拓扑序列;
2 从拓扑排序的序列的第一个顶点(源点)开始，按拓扑顺序依次计算每个事件的最早发生时间 ve(i) ;
3 从拓扑排序的序列的最后一个顶点(汇点)开始，按逆拓扑顺序依次计算每个事件的最晚发生时间 vl(i) ;

AOE网

拓扑排序的序列 :( v 0 , v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 , v 8 )
计算各个事件的 ve(i)和 vl(i)值:

其次计算e和l

根据关键路径的定义，知该 AOE 网的关键路径是: (v0, v2, v4, v7 , v8) 和(v0, v2,v5 , v7,v8) 。
关键路径活动是:<v0, v2>，<v2, v4>，<v2, v5>，<v4, v7>，<v5, v7>，<v5, v8> 。