论坛 › 数据结构与算法 › 关于AOE网的关键路径算法

Ayfkm 发表于 2014-12-19 10:49:48

关于AOE网的关键路径算法

// 边表结点声明
typedef struct EdgeNode
{
        int adjvex;
        struct EdgeNode *next;
}EdgeNode;

// 顶点表结点声明
typedef struct VertexNode
{
        int in;                        // 顶点入度
        int data;
        EdgeNode *firstedge;
}VertexNode, AdjList;

typedef struct
{
        AdjList adjList;
        int numVertexes, numEdges;
}graphAdjList, *GraphAdjList;

int *etv, *ltv;
int *stack2;                        // 用于存储拓扑序列的栈
int top2;                                // 用于stack2的栈顶指针

// 拓扑排序算法
// 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
Status TopologicalSort(GraphAdjList GL)
{
        EdgeNode *e;
        int i, k, gettop;
        int top = 0;                // 用于栈指针下标索引
        int count = 0;                // 用于统计输出顶点的个数
        int *stack;                        // 用于存储入度为0的顶点
       
        stack = (int *)malloc(GL->numVertexes * sizeof(int));
       
        for( i=0; i < GL->numVertexes; i++ )
        {
                if( 0 == GL->adjList.in )
                {
                        stack[++top] = i;        // 将度为0的顶点下标入栈
                }
        }
       
        // 初始化etv都为0
        top2 = 0;
        etv = (int *)malloc(GL->numVertexes*sizeof(int));
        for( i=0; i < GL->numVertexes; i++ )
        {
                etv = 0;
        }
        stack2 = (int *)malloc(GL->numVertexes*sizeof(int));
       
        while( 0 != top )
        {
                gettop = stack;                // 出栈
                // printf("%d -> ", GL->adjList.data);
                stack2[++top2] = gettop;        // 保存拓扑序列顺序 C1 C2 C3 C4 .... C9
                count++;                               
               
                for( e=GL->adjList.firstedge; e; e=e->next )
                {
                        k = e->adjvex;
                        // 注意：下边这个if条件是分析整个程序的要点！
                        // 将k号顶点邻接点的入度-1，因为他的前驱已经消除
                        // 接着判断-1后入度是否为0，如果为0则也入栈
                        if( !(--GL->adjList.in) )       
                        {
                                stack[++top] = k;
                        }
                       
                        if( (etv+e->weight) > etv )
                        {
                                etv = etv + e->weight;
                        }
                }
        }
       
        if( count < GL->numVertexes )        // 如果count小于顶点数，说明存在环
        {
                return ERROR;
        }
        else
        {
                return OK;
        }
}

// 求关键路径，GL为有向图，输出GL的各项关键活动
void CriticalPath(GraphAdjList GL)
{
        EdgeNode *e;
        int i, gettop, k, j;
        int ete, lte;
       
        // 调用改进后的拓扑排序，求出etv和stack2的值
        TopologicalSort(GL);
       
        // 初始化ltv都为汇点的时间
        ltv = (int *)malloc(GL->numVertexes*sizeof(int));
        for( i=0; i < GL->numVertexes; i++ )
        {
                ltv = etv;
        }
       
        // 从汇点倒过来逐个计算ltv
        while( 0 != top2 )
        {
                gettop = stack2;        // 注意，第一个出栈是汇点
                for( e=GL->adjList.firstedge; e; e=e->next )
                {
                        k = e->adjvex;
                        if( (ltv - e->weight) < ltv )
                        {
                                ltv = ltv - e->weight;
                        }
                }
        }
       
        // 通过etv和ltv求ete和lte
        for( j=0; j < GL->numVertexes; j++ )
        {
                for( e=GL->adjList.firstedge; e; e=e->next )
                {
                        k = e->adjvex;
                        ete = etv;
                        lte = ltv - e->weight;
                       
                        if( ete == lte )
                        {
                                printf("<v%d,v%d> length: %d , ", GL->adjList.data, GL->adjList.data, e->weight );
                        }
                }
        }
}
这是小甲鱼求关键路径的算法

本人刚接触数据结构，小白一个，虚心求教，求大神帮忙指导写一个创建AOE网的算法在以上的基础

xueying 发表于 2014-12-29 19:47:51

学习中

vanentu 发表于 2015-5-24 04:03:14

辛苦了

vank 发表于 2015-5-26 01:32:58

辛苦了

逆战时代 发表于 2015-5-26 22:10:18

LZ好人。。。。。。。。。。。。

EntU 发表于 2015-5-28 00:49:08

支持楼主！德玛西亚！

查看完整版本: 关于AOE网的关键路径算法