图的关键路径算法 c语言实现

 main.c

#include"Path.h"
#include"stack.h"
int main()
{
    Hnode *hnode=(Hnode *)malloc(sizeof(Hnode));
    InitList(hnode);
    int Ve[N];
    int Vl[N];
    Topo(hnode,Ve,Vl);
}

Path.c

#include"Path.h"
#include"stack.h"
#include
void InitList(Hnode *hnode)
{
    int i,j;
    hnode->e=1;
  //  hnode->in=0;
    hnode->hnext=NULL;
    hnode->next=NULL;
    Hnode *p=hnode;
    Node *p_node;
    for(i=2;ie=i;
        htemp->hnext=NULL;
        htemp->next=NULL;
    //    htemp->in=0;
        while (p->hnext!=NULL)
        {
            p=p->hnext;
        }
        p->hnext=htemp;
    }
    int temp[N][N]=
    {
        {-1,6,4,5,-1,-1,-1,-1,-1},
        {-1,-1,-1,-1,1,-1,-1,-1,-1},
        {-1,-1,-1,-1,1,-1,-1,-1,-1},
        {-1,-1,-1,-1,-1,2,-1,-1,-1},
        {-1,-1,-1,-1,-1,-1,9,7,-1},
        {-1,-1,-1,-1,-1,-1,-1,4,-1},
        {-1,-1,-1,-1,-1,-1,-1,-1,2},
        {-1,-1,-1,-1,-1,-1,-1,-1,4},
        {-1,-1,-1,-1,-1,-1,-1,-1,-1}

    };//如果是-1，则不可通，不纳入邻接表
    for(i=0;inext;
        for(j=0;jnext=NULL;
                node->value=temp[i][j];
                node->e=j+1;
                if(p_node!=NULL)
                {
                    while (p_node->next!=NULL)
                    {
                        p_node=p_node->next;
                    }
                    p_node->next=node;
                }
                else
                {
                    hnode->next=node;
                    p_node=node;
                }

                
            }
        }
        hnode=hnode->hnext;
    }
}
void Topo(Hnode *hnode,int *Ve,int *Vl)
{
    int k=0;
    int topo[N];
    Ve[0]=0;
    SeqStack *stack=(SeqStack *)malloc(sizeof(SeqStack));
    InitSeqStack(stack);
    int i,j;
    int e;
    for(i=1;inext;
        while(node!=NULL)
        {
            //if(node->e==i)
            In[node->e-1]++;//入度加一  
            node=node->next;         
        }
        hnode=hnode->hnext;
    }
    //第一次把入度为0的点都进栈
    for(i=0;isize>0&&khnext;
            }   
            node=hnode->next;
            while(node!=NULL)
            {
                if(node->e==topo[k]&&Ve[k]< (Ve[i]+node->value) )
                Ve[k]=(Ve[i]+node->value);
                node=node->next;
            }     
        }
        k++;
        hnode=hnode_o;
        for(i=0;ihnext;
        }
        node=hnode->next;
        while(node!=NULL)//把以第e个点为前驱的点的入度都减一
        {
            In[node->e-1]--;
            if(In[node->e-1]==0)
            {
                SeqStackPush(stack,node->e);
                In[node->e-1]=-1;
            }
            node=node->next;
        }
    }//运行到此topo排序已经完成。
    //下面求Vl
    for(i=0;ie=topo[k]的点
    for(j=0;jhnext;
        }
        node=hnode->next;
        while(node!=NULL)
        {
            for(i=k;ie==topo[i]&&Vl[k-1]>Vl[i]-node->value)
            {
                Vl[k-1]=Vl[i]-node->value;
            }
            node=node->next;
        }  
        k--; 
    }

    Arc arc[10*N];
    int arc_i=0;
    hnode=hnode_o;
    for(i=0;inext;
        while (node!=NULL)
        {
            arc[arc_i].j=i+1;
            arc[arc_i].k=node->e;
            for(j=0;je)
                break;
            }
            arc[arc_i].l=Vl[j]-node->value;
            arc_i++;
            node=node->next;
        }
        hnode=hnode->hnext; 
    }
    for(i=0;i

Path.h

#define N 9
#include
typedef struct Node
{
    struct Node *next;
    int value;
    int e;
}Node;
typedef struct Hnode
{
    struct Hnode *hnext;
    Node *next;
    int e;
}Hnode;
typedef struct Arc
{
    int j;
    int k;
    int e;
    int l;
}Arc;

void InitList(Hnode *hnode);
void Topo(Hnode *hnode,int *Ve,int *Vl);

stack.c

#include"stack.h"
#include"stdlib.h"
void InitSeqStack(SeqStack *stack)
{
    stack->capacity=1000;
    stack->size=0;
    stack->e=(int *)malloc(sizeof(int)*stack->capacity);
}
void SeqStackPush(SeqStack *stack,int e)
{
    stack->size++;
    stack->e[stack->size-1]=e;
}
int SeqStackPop(SeqStack *stack)
{
    stack->size--;
    return stack->e[stack->size];
}

stack.h

typedef struct SeqStack
{
    int *e;
    int size;
    int capacity;
}SeqStack;
void InitSeqStack(SeqStack *stack);
void SeqStackPush(SeqStack *stack,int e);
int SeqStackPop(SeqStack *stack);
//void SeqStackTop(SeqStack *stack,int *e);