数据结构方法(二)：关键路径

2018-12-19

× 文章目录

1. 一、关键路径
1. 1.1. 1.1 网络
2. 1.2. 1.2 名词解释
2. 二、计算关键路径的过程
3. 三、代码：
4. 四、文件格式
5. 五、输出结果：

一、关键路径

1.1 网络

AOV网络：有向图，用顶点表示活动，用弧表示活动的先后顺序
AOE网络：有向图，用顶点表示事件，用弧表示活动，用权值表示活动消耗时间

1.2 名词解释

活动：业务逻辑中的行为，用边表示

事件：活动的结果或者触发条件

关键路径：具有最大路径长度（权重）的路径，可能不止一条

活动的两个属性：

e(i)表示最早开始时间
l(i)表示最晚开始时间

事件的两个属性：

ve(j)最早开始时间
vl(j)最晚开始时间

在下面的计算过程中，就可以理解这些属性的概念了

二、计算关键路径的过程

原理：

先求出每个顶点的ve和vl值
通过这两个值就可以求出每条边的e和l值。
取e(i)=l(i)的边就是关键路径上的边，关键路径不止一条

2.1 求ve(i)的值

从前向后，直接前驱节点的ve值＋当前节点的边的权值（有可能多条，取最大值）
第一个顶点的ve等于0

ve(1) = 0
ve(2) = ve(1) + len(a1) = 0 + 3 = 3
ve(3) = ve(1) + len(a3) = 0 + 2 = 2
ve(4) = ve(1) + len(a2) = 0 + 6 = 6
ve(5) = min{ve(2) + len(a4),ve(4) + len(a8)} = max{7,7} = 7
ve(6) = ve(3) + len(a7) = 2 + 3 = 5
ve(7) = min{ve(a5) + len(a9),ve(6) + len(a10)} = max{10,9} = 10

下表为各顶点（事件）的ve值：

顶点	ve(1)	ve(2)	ve(3)	ve(4)	ve（5)	ve(6)	ve(7)
ve(i)	0	3	2	6	7	5	10

2.2 求vl(j)的值

从后向前，直接后继节点的vl值－当前节点的边的权值（有可能多条，取最小值）
终结点的vl等于它的ve

vl(7) = ve(7) = 10
vl(6) = vl(7) - len(a10) = 10 - 4 = 6
vl(5) = vl(7) - len(a9) = 10 - 3 = 7
vl(4) = vl(5) - len(a8) = 7 - 1 = 6
vl(3) = min{vl(6) - len(a7),vl(4) - len(a6)} = min{3,5} = 3
vl(2) = min{vl(5) - len(a4),vl(4) - len(a5)} = {3,4} = 3
vl(1) = min{vl(2) - len(a1),vl(4) - len(a2),vl(3) - len(a3)} = min{0,0,1} = 0

下表为各顶点（事件）的vl值：

顶点	vl(1)	vl(2)	vl(3)	vl(4)	vl(5)	vl(6)	vl(7)
vl(j)	0	3	3	6	7	6	10

2.3 求e(i)的值

e(i):活动ai是由弧表示，则活动的最早开始时间应该和事件vk的最早发生时间相等，因此，就有e(i)=ve(k)。即：边（活动）的最早开始时间等于它发出的顶点(事件)的的最早发生时间

参考之前的个顶点的ve和c：

顶点	ve	vl
v1	0	0
v2	3	3
v3	2	3
v4	6	6
v5	7	7
v6	5	6
v7	10	10

e(1)、e(2)、e(3) 活动（a1、a2、a3三条边）发出的顶点为v1，时间为0
e(4) 即为a4这条边发出的顶点 v2的发生的时间ve(2) = 3
e(5) 即为a5这条边发出的顶点 v2的发生的时间ve(2) = 3
e(6) 即为a6这条边发出的顶点 v3的发生的时间ve(3) = 2
e(7) 即为a7这条边发出的顶点 v3的发生的时间ve(3) = 2
e(8) 即为a8这条边发出的顶点 v4的发生的时间ve(4) = 6
e(9) 即为a9这条边发出的顶点 v5的发生的时间ve(5) = 7
e(10) 即为a10这条边发出的顶点 v6的发生的时间ve(6) = 5

得出的e(i)值：

边	a1(3)	a2(6)	a3(2)	a4(4)	a5(2)	a6(1)	a7(3)	a8(1)	a9(3)	a10(4)
e(i)	0	0	0	3	3	2	2	6	7	5

2.4 求l(i)的值

l(i):活动ai是由弧表示，则ai的最晚发生时间要保证vj的最迟发生时间不拖后（vj最迟发生时间为9的话，ai的最迟时间就必须是 9-活动耗时）。因此，l(i)=vl(i)-len，即：活动到达顶点的最晚发生时间减去边的权重

参考之前的个顶点的ve和c：

顶点	ve	vl
v1	0	0
v2	3	3
v3	2	3
v4	6	6
v5	7	7
v6	5	6
v7	10	10

l(i) = 当前边的指向结点的最晚发生时间[vl(i)] - 当前时间（即边）所消耗的时间

l(1) = vl(2) - len(a1) = 3 - 3 = 0
l(2) = vl(4) - len(a2) = 6 - 6 = 0
l(3) = vl(3) - len(a3) = 3 - 2 = 1
l(4) = vl(5) - len(a4) = 7 - 4 = 3
l(5) = vl(4) - len(a5) = 6 - 2 = 4
l(6) = vl(4) - len(a6) = 6 - 1 = 5
l(7) = vl(6) - len(a7) = 6 - 3 = 3
l(8) = vl(5) - len(a8) = 7 - 1 = 6
l(9) = vl(7) - len(a9) = 10 - 3 = 7
l(10) = vl(7) - len(a10) = 10 - 4 = 6

边	a1(3)	a2(6)	a3(2)	a4(4)	a5(2)	a6(1)	a7(3)	a8(1)	a9(3)	a10(4)
l(i)	0	0	1	3	4	5	3	6	7	6

2.5 求出关键边和关键路径

列出总表：

顶点	ve	vl	活动	e	l	l - e	关键路径
v1	0	0	a1	0	0	0	√
v2	3	3	a2	0	0	0	√
v3	2	3	a3	0	1	1
v4	6	6	a4	3	3	0	√
v5	7	7	a5	3	4	1
v6	5	6	a6	2	5	3
v7	10	10	a7	2	3	1
			a8	6	6	0	√
			a9	7	7	0	√
			a10	5	6	1

其中e(i)==l(i)的边：a1 a2 a4 a8 a9

所组成的路径即为关键路径：a1->a4->a9 和 a2->a8->a9

三、代码：

#include "stdio.h"
#include "stdlib.h"
#define M 20 /*预定义图的最大顶点数*/
#include "string.h"

typedef struct node
{   //边表结点
    int adjvex; //邻接点
    int len;
    struct node *next;
} edgenode;

typedef struct vnode
{   //头节点类型
    char vertex;    //顶点信息
    edgenode *firstedge; //邻接表表头指针
    int id;
} vertexnode;

typedef struct
{   //邻接表类型
    vertexnode adjlist[M]; //存放头节点的顺序表
    int n, e;   //图的顶点数与边数
} linkedgraph;

int visited[M];

linkedgraph create(char *filename, int c) //c = 0表示创建无向图
{
    linkedgraph g;
    int i, j, k;
    int weight = 0; //边的权值
    edgenode *s;
    FILE *fp;
    fp = fopen(filename, "r");
    if (fp)
    {
        fscanf(fp, "%d%d\n", &g.n, &g.e);
        for (i = 0; i < g.n; i++)
        {
            fscanf(fp, "%c%d ", &g.adjlist[i].vertex, &g.adjlist[i].id);
            g.adjlist[i].firstedge = NULL;
        }
        for (k = 0; k < g.e; k++)
        {
            fscanf(fp, "%d%d%d", &i, &j, &weight);
            s = (edgenode *)malloc(sizeof(edgenode));
            s->adjvex = j;
            s->len = weight;
            s->next = g.adjlist[i].firstedge;
            g.adjlist[i].firstedge = s;
            if (c == 0) //无向图
            {
                s = (edgenode *)malloc(sizeof(edgenode));
                s->adjvex = i;
                s->len = weight;
                s->next = g.adjlist[j].firstedge;
                g.adjlist[i].firstedge = s;
            }
        }
        fclose(fp); //关闭文件流
    }
    else
    {
        g.n = 0;
        printf("文件打开失败！\n");
    }
    return g;
}

//求AOE网络中时间的最早发生时间
/*
事件最早发生的事件向量ve[],AOE网络的拓扑排序向量seq[]
*/
int EarlistTime(linkedgraph *gout, int ve[], int seq[])
{
    int count = 0; //计数器
    int flag[M];   //定义标记数组
    int queue[M];  //定义队列
    int front = 0;
    int rear = 0;
    edgenode *p;
    for (int i = 0; i < gout->n; i++) //初始化每个顶点的最早开始时间ve[i]为0
        ve[i] = 0;
    for (int j = 0; j < gout->n; j++) //初始化标记数组
        flag[j] = 0;
    for (int i = 0; i < gout->n; i++)
        if (gout->adjlist[i].id == 0 && flag[i] == 0)
        {
            queue[rear++] = i;
            flag[i] = 1; //标记被访问过
        }
    while (front < rear)
    {
        int v = queue[front++]; //队首元素出栈
        printf("%c----->", gout->adjlist[v].vertex);
        seq[count] = v; //记录拓扑排序当前元素
        count++;		//计数器 + 1
        p = gout->adjlist[v].firstedge;
        while (p)
        {
            int j = p->adjvex;
            if (--gout->adjlist[j].id == 0 && flag[j] == 0) //若入度为0则将其入队
            {
                queue[rear++] = j;
                flag[j] = 1;
            }
            if (ve[v] + p->len > ve[j])
                ve[j] = ve[v] + p->len; //ve[j]的值是从源点到顶点j的最长距离
            p = p->next;
        }
    }
    return count;
}
//求AOE网络中时间的最晚发生时间
/*
Aov网的入边表gin，事件发生
*/
void LateTime(linkedgraph *gin, int ve[], int vl[], int seq[])
{
    int k = gin->n - 1;
    int j = 0;
    int v = 0;
    edgenode *p = NULL;
    for (int i = 0; i < gin->n; i++)
        vl[i] = ve[seq[gin->n - 1]];
    while (k > -1) //按照拓扑排序求个事件的最晚开始时间
    {
        //v = seq[k];
        p = gin->adjlist[k].firstedge;
        while (p)
        {
            j = p->adjvex;
            if (vl[j] - p->len < vl[k])
                vl[k] = vl[j] - p->len;
            p = p->next;
        }
        k--;
    }
}

void LateTime2(linkedgraph *gin, int ve[], int vl[], int seq[])
{
    int k = gin->n - 1;
    int j = 0;
    int v = 0;
    edgenode *p = NULL;
    for (int i = 0; i < gin->n; i++)
        vl[i] = ve[seq[gin->n - 1]];
    printf("\n拓扑排序序列：\n");
    for (int i = 0; i < 10; i++)
        printf("%d----->", seq[i]);
    printf("\n");
    while (k > -1) //按照拓扑排序求个事件的最晚开始时间
    {
        v = seq[k];
        p = gin->adjlist[v].firstedge;
        while (p)
        {
            j = p->adjvex;
            if ((vl[j] - p->len) < vl[v])
                vl[v] = vl[j] - p->len;
            p = p->next;
        }
        k--;
    }
}

int TopSort(linkedgraph *g)
{
    int k = 0, i, j, v, flag[M];
    int queue[M]; //定义队列
    int front, rear;
    edgenode *p;
    front = rear = 0; //初始化队列
    for (i = 0; i < g->n; i++)
        flag[i] = 0; //访问标记初始化
    for (i = 0; i < g->n; i++)
    {
        if (g->adjlist[i].id == 0 && flag[i] == 0)
        {
            queue[rear++] = i;
            flag[i] = 1;
        }
    }
    printf("\n该AOV网的拓扑排序为：\n");
    while (front < rear) // 如果当前队列不为空
    {
        v = queue[front++]; //队列首位元素出列
        printf("%c ", g->adjlist[v].vertex);
        k++; //计数器加1
        p = g->adjlist[v].firstedge;
        while (p) //将所有于v邻接的顶点的入度减1
        {
            j = p->adjvex;
            if (--g->adjlist[j].id == 0 && flag[j] == 0) //如果入度为0则将进队
            {
                queue[rear++] = j;
                flag[j] = 1; //标记已经被访问过
            }
            p = p->next;
        }
    }
    printf("\n");
    return k; //返回输出的结点个数
}

int main()
{
    int count = 0;
    int number = 0;
    int ve[10] = { 0 };  //时间最早发生时间向量
    int vl[10] = { 0 };  //时间晚发生时间向量
    int seq[10] = { 0 }; //拓扑排序向量
    char filename[30] = "D:\\Desktop\\Test.txt";
    linkedgraph h;
    h = create(filename, 1);
    number = EarlistTime(&h, ve, seq);
    LateTime2(&h, ve, vl, seq);
    printf("\n");
    printf("时间最早发生时间向量：\n");
    for (int i = 0; i < 10; i++)
        printf("%d----->", ve[i]);
    printf("\n");
    printf("时间最晚发生时间向量：\n");
    for (int i = 0; i < 10; i++)
        printf("%d----->", vl[i]);
    printf("\n");
    printf("关键路径为:\n");
    int m, i,n;
    int earlist[15] = { 0 };
    int late[15] = { 0 };
    m = 0;
    n = 0;
    vertexnode vert;
    for (i = 0; i < h.n; i++)
    {
        edgenode *p = h.adjlist[i].firstedge;
        vert = h.adjlist[i];
        while (p)
        {
            int k = p->adjvex;
            if (ve[i] == vl[k] - p->len)
                printf("%c-", vert.vertex);
            p = p->next;
        }
    }
    printf("%c", vert.vertex);
    printf("\n");
    system("pause");
    return 0;
}