自己动手写数据结构（9）——图的拓扑排序和关键路径_图 关键路径

自己动手写数据结构总目录

具体内容：

• 1.链表

• 2.栈和队列及其应用

• 3.串

• 4.二叉树

• 5.树

• 6.图及其五种存储方式

• 7.图的最小生成树

• 8.图的最短路径

• 9.图的拓扑排序和关键路径

• 10.有序表查找（详解斐波那契查找）

• 11.二叉排序树

• 12.平衡二叉树（详解结点删除）

该文章的源代码仓库为：https://github.com/MeteorCh/DataStructure/blob/master/Java/DataStructure/src/Graph/AdjListGraph.java

一、拓扑排序

1.定义

• AOV网： 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，成为AOV(Activity On Vertex Network)网。
• 拓扑序列 对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
  以下面的图为例：
  
  按照拓扑排序的定义，V1必须要在V0的后面，V2必须要在V0、V1的后面，V3必须要在V1、V2的后面，V4必须要在V2、V3的后面。那这个图的拓扑排序只有一种，就是V0,V1,V2,V3,V4。对于一个图，拓扑排序可能不唯一，而且，只有有向无环图才存在拓扑排序（如果有环，比如上面的图中，V3和V1之间的边改成V3指向V1，那按照拓扑排序的定义，V3必须在V2的后面，V2必须在V1的后面，那V3就必须在V1的后面，又因为V3->V1有边，那V1必须在V3的后面，这就矛盾了）。

2.拓扑排序算法

如何实现拓扑排序呢？具体步骤如下：

• 1.首先找到图中入度为0的节点，输出
• 2.将与该节点相连的以该点为起点的弧全部删除（该弧的终点所相连的顶点的入度减1），重复上面的步骤，指导所有节点均输出
• 3.如果图中的节点没有完全输出，说明图中存在环，不存在拓扑排序。

3.代码实现

我在以前实现的邻接表存储的图（博客在这里，源码在这里）来实现拓扑排序，我这里只写函数，具体的图的具体Java代码如下：
首先是拓扑排序的实现代码，函数参数earlistStartTime是在求解关键路径时，记录事件的最早开始时间的，在这个函数里有关earlistStartTime的代码暂时先不用管。

/**
     * 拓扑排序
     * @param earlistStartTime 事件的最早开始时间
     * @return 拓扑排序结果
 */
protected LinkedList<Integer> topoSort(int[] earlistStartTime) throws Exception {
        int[] in=new int[vertexNum];//统计每个节点的入度的数组
        boolean[] visitFlag=new boolean[vertexNum];//标记节点是否已输出
        //初始化
        if (earlistStartTime!=null){
            for (int i=0;i<vertexNum;i++)
                earlistStartTime[i]=0;
        }
        for (int i=0;i<vertexNum;i++){
            visitFlag[i]=false;
            VertexNode node=vertexes[i];
            ArcNode arcNode=node.firstArc;
            while (arcNode!=null){
                in[arcNode.nodeIndex]++;
                arcNode=arcNode.next;
            }
        }
        LinkedList<Integer> stack=new LinkedList<>();
        LinkedList<Integer> result=new LinkedList<>();
        //将入度为0的下标入栈
        for (int i=0;i<vertexNum;i++)
            if (in[i]==0)
            {
                stack.add(in[i]);
                visitFlag[i]=true;
            }
        //开始拓扑排序
        while (!stack.isEmpty()){
            //弹栈
            int curIndex=stack.pop();
            result.push(curIndex);
            visitFlag[curIndex]=true;
            //将curIndex相连的节点的入度减1
            ArcNode curArc=vertexes[curIndex].firstArc;
            while (curArc!=null){
                if (!visitFlag[curArc.nodeIndex])
                {
                    in[curArc.nodeIndex]--;
                    //需要计算事件的最早开始时间
                    if (earlistStartTime!=null){
                        if (curArc.weight instanceof Integer){
                            Integer weight=(Integer)curArc.weight;
                            if (earlistStartTime[curIndex]+weight>earlistStartTime[curArc.nodeIndex])
                                earlistStartTime[curArc.nodeIndex]=earlistStartTime[curIndex]+weight;
                        }else
                            throw new Exception("暂时只支持整形权重");

                    }
                    //如果入度变为0,则入栈
                    if (in[curArc.nodeIndex]==0){
                        stack.add(curArc.nodeIndex);
                        visitFlag[curArc.nodeIndex]=true;
                    }
                }
                curArc=curArc.next;
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

在上面的代码里，用in这个数组来存储顶点的入度（因为邻接表求解入度不方便，所以在程序开始的时候先通过遍历图来求解每个顶点的入度并记录在数组中）。然后上面主要是用了栈实现拓扑排序的，代码比较简单，我就不细说了。还有一个就是，为了支持多种数据类型，我使用了泛型了表示权重，这个泛型继承Numbers，结果发现在比较大小的时候，泛型是个大坑。。。然后没办法，在这里我就只能对权重进行强制规定成整形的（这里可能是我的知识储备不够，如果有同学知道这种情况应该怎么解决，可以在评论区跟我说一下）。
然后是提供的供外界调用的函数：

	/**
     * 拓扑排序
     */
    public void topoSort(){
        try {
            LinkedList<Integer> result=topoSort(null);
            if (result.size()==vertexNum)
            {
                System.out.print("该图的拓扑排序结果为：");
                for (int i:result)
                    System.out.print(vertexes[i].data+",");
                System.out.println();
            }
            else
                System.out.println("图中存在环，不存在拓扑排序");
        }catch (Exception e){
            System.out.println("目前拓扑排序只支持整形权重");
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

可以看到这里对图中是否存在环做了一个判断。
以最上面的那个图为例，对其进行拓扑排序，调用代码为

		AdjListGraph graph=AdjListGraph.getTestInstance();
        System.out.println(graph.toString());
        graph.topoSort();
1
2
3

上面的AdjListGraph.getTestInstance函数就是生成最上面的示例图，输出结果为：

二、关键路径

1.定义

• AOE网： 在一个表示工程的带权有向图中，用顶点表示事件，用有限边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，称之为AOE网（Aactivity On Edge Network）。其中，网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。
• 关键路径： 我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

2.关键路径的求解算法

首先做一些定义：

• 1.事件的最早发生时间： 一个事件最早发生的时间。因为事件能否发生，决定于指向它的活动是否完成，所以一个事件的最早发生时间要从源点顺推。 源点的最早发生时间肯定是0，以上面的图为例，与V1相连的只有V0V1一个活动，那V1的最早发生时间就是0+1=1，V2有两个活动相连，V1到V2，时间为1+3=4，V0到V2，时间为0+2=2。因为只有V1V2、V0V2两个活动同时完成后，V2事件才能开始，所以V2的最早发生时间应该取大值，即4。我们可以得到，一个事件的最早发生时间的计算公式为（我们用etv[k]表示k顶点的最早发生时间）：
  
  根据上面的公式，我们计算得到上面的图中的所有事件的最早发生时间为：
  
• 2.事件的最晚发生时间： 一个事件最晚发生的时间，如果迟于这个时间，就会拖进度。由于在上面我们已经得到了时间的最早开始时间，而且每个事件的最早开始时间都是所有相关的活动都完成后开始算的，所以一个事件的最晚开始时间要从汇点逆推。 V4的最晚发生时间是16，因为V3只有一条出边，那V3的最晚发生时间为16-7=9。再看V2，V2有V2V3、V2V4两条出边，通过V2V3计算，V2的最晚发生时间为9-5=4；通过V2V4计算，V2的最晚发生时间为16-6=10。那V2的最晚发生时间应该取多少呢？如果取10，那V2->V3->V4所需要的时间就是10+5+7=22，明显大于V4的发生时间，所以取10是不对的。我们想一想应该知道，这时应该取较小的值4，这样算下来才能腾出足够的时间来完成活动。所以一个事件的最晚发生时间的计算公式为（我们用ltv[k]表示k顶点的最晚发生时间）：
  
  根据公式，我们计算得到各个事件的最晚开始时间为：
  
  可以看到上面每个事件的最早开始时间和最晚开始时间是相等的。但这只是因为这个图是这样，并不是每个事件的最早开始时间和最晚开始时间是相等的。而且一个事件的最早开始时间和最晚开始时间相等和这个是否是关键事件没有任何关系。
• 3.活动的最早开始时间： 这个没什么说的，每个活动（即图中的每条边）的最早开始时间为该边的起点活动的最早开始时间。如V0V2、V0V2的最早开始时间都是0，V1V2、V1V3的最早开始时间都是1。
• 4.活动的最晚开始时间： 一个活动的最晚开始时间应该怎么算呢？比如活动V2V3，V3的最晚开始时间是9，不能再晚了，那活动V2V3的最晚开始时间就是9-5=4。所以对于活动ViVj，其最晚开始时间为etv[j]-W(ViVj)，其中W(ViVj)表示活动ViVj这个活动耗费的时间。

根据上面的计算方法，将每个活动的最早开始和最晚开始时间计算如下：

==其中最早开始时间和最晚开始时间相等的活动为关键活动，==那关键活动为V0V1,V1V2,V2V3,V3V4，关键路径为V0->V1->V2->V3->V4

3.代码实现

我在以前实现的邻接表存储的图（博客在这里，源码在这里）来实现拓扑排序，我这里只写函数，具体的图的具体Java代码如下：

public void keyPath(){
        try{
            int[] etv=new int[vertexNum];//事件的最早发生时间
            LinkedList<Integer> topoResult=topoSort(etv);//拓扑排序结果
            if (topoResult.size()==vertexNum){
                int[] ltv=new int[vertexNum];//事件的最晚发生时间
                //初始化ltv
                for (int i=0;i<vertexNum;i++)
                    ltv[i]=etv[vertexNum-1];
                //求解ltv
                while (!topoResult.isEmpty()){
                    int curIndex=topoResult.pop();
                    ArcNode curArc=vertexes[curIndex].firstArc;
                    while (curArc!=null){
                        Integer weight=(Integer)curArc.weight;
                        if (ltv[curArc.nodeIndex]-weight<ltv[curIndex])
                            ltv[curIndex]=ltv[curArc.nodeIndex]-weight;
                        curArc=curArc.next;
                    }
                }
                //求解每个活动的最早开始时间和最晚开始时间
                System.out.print("AOE网中的关键活动为：");
                for (int i=0;i<vertexNum;i++){
                    ArcNode curArc=vertexes[i].firstArc;
                    while (curArc!=null){
                        int ete=etv[i];//活动的最早开始时间
                        int lte=ltv[curArc.nodeIndex]-(Integer) curArc.weight;//活动的最晚开始时间
                        if (ete==lte)
                            System.out.print(vertexes[i].data.toString()+vertexes[curArc.nodeIndex].data+",");
                        curArc=curArc.next;
                    }
                }
                System.out.println();

            }else {
                System.out.println("图中存在环！");
            }

        }catch (Exception e){
            System.out.println("目前关键路径只支持整形权重");
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

上面的代码中，先调用开始讲的拓扑排序获得图的拓扑排序和每个事件的最早发生时间，然后再逆推得到每个时间的最晚发生时间，再遍历边得到每个活动的最早和最晚开始时间，判断是否相等来判断活动是否为关键活动。
调用下面的代码，通过getTestInstance创建上面的AOE网，然后计算关键路径

		AdjListGraph graph=AdjListGraph.getTestInstance();
        System.out.println(graph.toString());
        graph.keyPath();
1
2
3

计算结果输出为：