AOE算法——超详细，超通俗讲解

AOE算法应用和实现思路讲解可以参见其他数据结构教材或者网上相关博客文章，在这里，我就具体针对代码讲解具体含义：
首先是类头文件：

#pragma once
#define maxsize 100
#define MAX 999999999
class graph
{

public:
    //活动数量
    int possize;

    //邻接矩阵存储图
    int store[maxsize][maxsize];

    //构造函数
    graph(void);

    //析构函数
    ~graph(void);

    //图输入算法
    void graphin();

    //图关键路径算法
    bool aoe();

    //找到关键路径
    void findway(int *ve,int *vl,int cur);
};

然后是类实现的源文件：

#include "StdAfx.h"
#include "graph.h"
#include <iostream>
using namespace std;
//**********************************************
//函数名：graph
//函数参数：void
//函数返回类型：无
//函数功能：构造函数，用于邻接矩阵初始化和possize初始化
//备注：自身指向自身赋值为0，两点之间不连接赋值为无穷大（999999999）
//**********************************************
graph::graph(void)
{
    possize=0;

    int i,j;

    //利用双重循环给邻接矩阵初始化
    for(i=0;i<maxsize;i++)
    {
        for(j=0;j<maxsize;j++)
        {


            //自身指向自身赋值为0，两点之间不连接赋值为无穷大（999999999）
            if(i==j)
                store[i][j]=0;
            else 
                store[i][j]=MAX;


        }
    }
}

//**********************************************
//函数名：~graph
//函数参数：无
//函数返回类型：无
//函数功能：析构函数
//备注：由于没有用new申请空间，故不需要delete等清除操作
//**********************************************
graph::~graph(void)
{

}



//**********************************************
//函数名：graphin
//函数参数：无
//函数返回类型：无
//函数功能：用于输入
//备注：输入应按照提示语按照要求输入，输入end时结束输入
//**********************************************
void graph::graphin()
{
    cout<<"（提示语）请输入所有带权有向边，如<V1,V2>9，结束请输入end"<<endl;

    //输入存储用的字符串
    char str[100]={'\0'};

    //记录某一节点是否存在，并用于统计活动个数
    bool used[maxsize];

    //初始化，false表示所有节点都没有被用到
    int i;
    for(i=0;i<maxsize;i++)
    {
        used[i]=false;
    }


    possize=0;



    //利用循环进行输入
    while(cin>>str)
    {

        //因为结束标志是end，因此当下标为2的字符为d时，可以判断输入结束
        if(str[2]=='d') 
        {
            break;
        }

        //输入没有结束
        else
        {
            i=0;

            //分别表示边的头，尾和权值
            int head=0,tail=0,weight=0;



            //考虑到标号可能不只一位数
            //无论是n位数，第一个出现的数字肯定是头端点，第二个肯定为尾端点，第三个出现的数字肯定为权值


            //筛掉前边无用的字母
            while(str[i]<'0'||str[i]>'9')
                i++;

            //对第一个出现的数字进行处理，考虑这个数字不是一位数的情况
            while(str[i]>='0'&&str[i]<='9')
            {
                head=head*10+str[i]-'0';
                i++;
            }


            //继续筛选，找到第二个数字
            while(str[i]<'0'||str[i]>'9')
                i++;


            //进行同第一个数字一样的处理
            while(str[i]>='0'&&str[i]<='9')
                {
                    tail=tail*10+str[i]-'0';
                    i++;
                }


            //继续筛选，找到第三个数字
            while(str[i]<'0'||str[i]>'9')
                    i++;

            //进行同第一个数字一样的处理
            while(str[i]>='0'&&str[i]<='9')
                {
                    weight=weight*10+str[i]-'0';
                    i++;
                }

            //处理完毕后即得到某一条边的头，尾，权值
            store[head][tail]=weight;

            //标记这个点用过
            used[head]=true;
            used[tail]=true;

        }
    }


    //通过统计有多少个点用过找到点的总数
    for(i=1;i<=maxsize;i++)
    {
        if(used[i]==true) possize++;
    }


}



//**********************************************
//函数名：aoe
//函数参数：无
//函数返回类型：bool true表示程序正常结束，实现功能，false表示不能正常结束
//函数功能：用于找到关键路径、关键活动并且输出
//备注：不考虑存在环的情况
//**********************************************
bool graph::aoe()
{
    //记录每个活动的入度
    int goin[maxsize];

    //记录拓扑排序
    int stack[maxsize];

    //记录最早开始时间
    int ve[maxsize];

    //记录最晚开始时间
    int vl[maxsize];

    //用n存储点的个数，防止possize被改变
    int n=possize;

    //top表示栈顶，可以取得到
    int top=0;
    int i,j,k,t;

    //对用到的各个数组进行初始化
    for(i=0;i<maxsize;i++)
    {
        goin[i]=0;
        stack[i]=0;
        ve[i]=0;
        vl[i]=0;
    }

    //通过遍历邻接矩阵找到每个点的入度
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {


            //当这个两个点联通时，尾节点入度加1
            if(store[i][j]>0&&store[i][j]<MAX)
                goin[j]++;
        }
    }


    //n个节点全部进行操作
    for(i=1;i<=n;i++)
    {

        //从第一个点开始找到一个入度为0的点
        j=1;

        while(goin[j]!=0)
        {
            j++;
            if(j>n) return false;


        }

        //找到的这个点入栈，栈用于拓扑排序
        stack[i]=j;
        top++;

        //对于每一个新入栈的点，从栈里这个点之前的位置找一个节点使得新入栈的点得到最早开始时间
        for(k=1;k<=top;k++)
        {
            if(store[stack[k]][j]>0&&store[stack[k]][j]<MAX)
            {
                if(ve[j]<ve[stack[k]]+store[stack[k]][j])
                {
                    ve[j]=ve[stack[k]]+store[stack[k]][j];
                }
            }
        }


        //更新每一个点的入度
        for(k=1;k<=n;k++)
        {
            if(store[j][k]>0&&store[j][k]<MAX)
                goin[k]--;
        }
        goin[j]=-1;

    }

    //活动终点的最早开始时间和最晚开始时间相同
    vl[stack[n]]=ve[stack[n]];

    //终点肯定用时最长，故把vl初始化为最长时间
    for(i=1;i<=n;i++)
        vl[i]=ve[stack[n]];

    //按照逆拓扑排序遍历
    for(t=top;t>0;t--)
        for(k=t;k<=top;k++)
        {

            //从后向前更新每一个点，求出最晚开始时间
            if(store[stack[t]][stack[k]]<MAX&&store[stack[t]][stack[k]]>0)
            {


                if(vl[stack[t]]>vl[stack[k]]-store[stack[t]][stack[k]])
                {
                    vl[stack[t]]=vl[stack[k]]-store[stack[t]][stack[k]];
                }
            }

        }


        //调用函数输出关键路径
        cout<<"关键路径:"<<endl;
        findway(ve,vl,1);


        //直接遍历寻找关键活动，满足时间余量为0的点即为关键活动
        cout<<"关键活动:"<<endl;
        /*for(i=2;i<n;i++)
        {
            if(ve[i]==vl[i])
            {
                cout<<"V"<<i<<',';
            }
        }*/

        //关键活动的前后点一定是时间余量为0的节点
        //以此为标准，遍历邻接矩阵，找到符合条件的活动
        //两重循环用于遍历
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(store[i][j]>0&&store[i][j]<MAX)
                {
                    if(ve[i]==vl[i]&&ve[j]==vl[j])
                        cout<<"<V"<<i<<",V"<<j<<'>'<<endl;
                }
            }
        }

        cout<<endl;
        return true;
}



//**********************************************
//函数名：findway
//函数参数：int *ve,int *vl,int cur 分别表示某一活动的最早开始时间，最晚开始时间和当前活动数
//函数返回类型：无
//函数功能：找到并且输出关键路径
//备注：对于存在有多条关键路径的图，路径重合处一起输出，从路径分叉点开始分两行继续输出后续关键路径
//**********************************************
void graph::findway(int *ve,int *vl,int cur)
{

    //当前节点是最后一个
    if(cur==possize) 
    {
        cout<<"V"<<cur<<endl;
    }
    int i;


    //当前节点不是最后一个
    for(i=1;i<=possize;i++)
    {


        //关键路径上的下一个节点应满足两个条件
        //1.ve[i]==vl[i]，即这个点是关键活动
        //2.当前点与这个点联通
        if(ve[i]==vl[i]&&(store[cur][i]>0&&store[cur][i]<MAX))
        {
            cout<<'V'<<cur<<'-';


            //递归找下一个点
            findway(ve,vl,i);
        }
    }
}

最后是测试程序（文末附上测试输入样例）：

// .cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "graph.h"
#include <iostream>
#include <cstdio>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{

    graph test;

    //输入图
    test.graphin();


    //寻找关键路径操作
    if(test.aoe()){}
    system("pause");
    return 0;
}

/*
<V1,V2>5
<V1,V3>8
<V2,V4>6
<V3,V4>7
*/
/*
<V1,V2>6
<V1,V3>4
<V1,V4>5
<V2,V5>1
<V3,V5>1
<V5,V7>9
<V5,V8>7
<V7,V9>2
<V8,V9>4
<V4,V6>2
<V6,V8>4

*/