欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关键路径(AOE)—基于拓扑排序(AOV)

程序员文章站 2024-03-25 21:32:16
...

数据结构讲到图的部分,实现一些比较经典的算法。测试数据是网上提供的。
关键路径的实现基于拓扑排序,同时用到了栈结构。

//Stack.h
#ifndef STACK_H
#define STACK_H

class Stack{
public:

    Stack(int n = 10);
    bool push(int a);
    int pop();
    bool isfull();//判断是否满
    bool isempty();
private:
    int size;//表示最大容量
    int *base, *top;//top指向栈顶前一个元素
};
#endif
//Path.h
/*
相较于拓扑排序,Path类多了 OppositeTopo,mainPath两个函数,TopologicalSort也加了几个计算的语句
*/
#ifndef PATH_H
#define PATH_H
class Stack;
class Node{
public:
    int vexNum;
    int dut;
    Node* next;

    Node(int vex = 0, Node* a = 0, int value=0);
};

class MGraph{
    //图的储存用邻接表,要求入度
public:
    int Vex;
    Node* vertices;//邻接表的表头数组

    MGraph(int num = 0);
    bool Inition();//初始化

};

class Path{

public:
     bool TopologicalSort(const MGraph& g, Stack& T);//拓扑排序
     bool OppositeTopo(const MGraph& g);//逆向输出拓扑排序,求出顶点最晚时间
     void mainPath(const MGraph& g);//关键路径

private:
     int maxtime;//工程所需总时间
     int* ve, *vl;
};

#endif
//Stack.cpp
#include"Stack.h"

#include<iostream>
using namespace std;

Stack::Stack(int n){
    size = n;
    top = base = new int[size];
}

bool Stack::push(int a){
    *top = a;
    top++;
    return true;
}

int Stack::pop(){
    /*if (top == base){
    exit(0);
    }*/
    return *(--top);
}

bool Stack::isfull(){
    if (top - base >= size)
        return true;
    else
        return false;
}

bool Stack::isempty(){
    if (top == base)
        return true;
    else
        return false;
}
//Path.cpp
#include<iostream>
#include"Path.h"
#include"Stack.h"
using namespace std;

/*
算法:
  1.利用拓扑排序,先计算每个顶点的最早发生时间,存入ve[i]且ve[0]=0;
     其中,ve[i]=max{ve[k]+dut<i,k>}(k->i)
    拓扑排序完成之后,如果顶点数目不全,则存在环,输出ERROR,退出程序
  2.计算每个顶点的最晚发生时间,存入vl[i],vl[n-1]=ve[n-1];
     其中,vl[i]=min{ve[k]+dut<i,k>}(i->k)
  3.计算每个活动(边)最早最晚发生时间,存入e[i],l[i]。
      其中e[i]=ve[i];   l[i]=vl[k]-dut<i,k>;
  4.判断 v[i]==l[i],若相等,则是关键路径,输出
*/

bool Path::TopologicalSort(const MGraph& g, Stack& T){
    //拓扑排序
    //如果最后有环,输出false,如果全部顶点都输出,则返回true
    /*算法:
    1.计算每个顶点的入度(初始化)
    初始化栈
    2.将入度为0的点压栈
    3.弹栈,并将以该顶点为弧尾的顶点入度-1
    4.重复2,3,直到栈空(有可能顶点都遍历,有可能存在环)
    */
    cout << "TopoOrder:";
    maxtime = 0; 
    ve = new int[g.Vex](); //++

    Stack S(g.Vex);//S用来储存入度为0的顶点
    int *count = new int[g.Vex]();
    for (int i = 0; i < g.Vex; i++){
        count[i] = g.vertices[i].vexNum;
        if (!count[i])
            S.push(i);
    }
    int flag = 0;
    while (!S.isempty()){
        int i = S.pop();flag++;
        T.push(i);//++
        for (Node* p = g.vertices[i].next; p; p = p->next){
            if (--count[p->vexNum] == 0){
                S.push(p->vexNum);
            }
            //更新ve[i]
            ve[p->vexNum] = ve[p->vexNum] > (ve[i] + p->dut) ? ve[p->vexNum] : (ve[i] + p->dut);//++++
        }
        maxtime = ve[i] > maxtime ? ve[i] : maxtime;//++记录关键路径的时间

        cout << i + 1 << "  ";
    }
    cout << endl;
    if (flag == g.Vex)
        return true;
    else
        return false;

}

//++求出顶点最晚时间
bool Path::OppositeTopo(const MGraph& g){
    Stack T(g.Vex);//记录拓扑排序的序号
    if(!TopologicalSort(g, T))
        return false;
    vl = new int[g.Vex]();
    for (int i = 0; i < g.Vex; i++){
        vl[i] = maxtime;
    }
    while (!T.isempty()){
        int j = T.pop(); //cout << "T:" << j << "  ";
        for (Node* p = g.vertices[j].next; p; p = p->next){
            vl[j] = vl[j] < (vl[p->vexNum] - p->dut) ? vl[j] : (vl[p->vexNum] - p->dut);
        }
    }
    /*for (int i = 0; i < g.Vex; i++){
        cout << vl[i] << '\t';
    }*/
    return true;
}

void Path::mainPath(const MGraph& g){
    OppositeTopo(g);
    for (int i = 0; i < g.Vex; i++){
        for (Node* p = g.vertices[i].next; p; p = p->next){
            int e = ve[i];
            int l = vl[p->vexNum] - p->dut;
            char tag = (e == l) ? '*' : ' ';
            cout << i+1 <<"->"<< p->vexNum +1<<"\tearly-begain:"<< e <<"\tlater-begain"<< l <<"\t" <<tag<<endl;
        }
    }
}


//Node
Node::Node(int vex, Node* a,int value){
    vexNum = vex;
    next = a;
    dut = value;
}


//MGraph
MGraph::MGraph(int num){
    Vex = num;
    vertices = new Node[Vex]();
    /*for (int i = 0; i < Vex; i++){
    cout << vertices[i].vexNum;
    }
    cout << endl;*/
}


bool MGraph::Inition(){
    if (!Vex) return false;
    int b, e, value;
    while (cin >> b&&b){
        cin >> e>>value;
        Node* p = vertices[b - 1].next;
        vertices[b - 1].next = new Node(e - 1, p,value);//前插
        vertices[e - 1].vexNum++;//记录入度
    }
    /*for (int i = 0; i < Vex; i++){
    for (Node* p = vertices[i].next; p; p = p->next){
    cout << p->vexNum << "  ";
    }
    cout << endl;
    }*/
    return true;
}
//main.cpp
#include<iostream>
#include"Path.h"
using namespace std;


int main(){
    int n;
    cin >> n;
    MGraph g(n);
    g.Inition();
    Path a;
    a.mainPath(g);
    system("pause");
    return 0;

}
/*测试数据
9 
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 9 4
*/


/*
6 
1 2 3
1 3 2
2 4 2
2 5 3
3 4 4
3 6 3
4 6 2
5 6 1
*/

关键路径(AOE)—基于拓扑排序(AOV)

相关标签: 数据结构 算法