#include "stdafx.h"
#include"malloc.h"
typedef int Status;
typedef int InfoType;
typedef int VertexType;
typedef int SElemType;
#define OK 1
#define ERROR -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex;
int weight;//该边所关联的另一顶点的位置
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)return(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack &S,SElemType e){
if(S.top-S.base>=S.stacksize){
S.base=(SElemType )realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)return(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e){
if(S.top==S.base)return ERROR;
e=--S.top;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.top==S.base)
return OK;
else
return ERROR;
}
int indegree[20];
void FindInDegree(ALGraph G,int indegree[])
{
int i,j,w,k=0,n=0;
ArcNode *p;
int i;
for(i=0; i
for(j=0;j
{
for(i=0;i
{
p=G.vertices[i].firstarc;
while (p)
{
w=p->adjvex;
if(w=i) n++;
p=p->nextarc;
}
}
indegree[k++]=n;
printf("%d",indegree[k]);
n=0;
}
}
int ve[20],vl[20];
SqStack S;
Status TopologicalOrder(ALGraph G,SqStack &T){
int count,j,k;
FindInDegree(G,indegree);
InitStack(T);count=0;
int i;
for(i=0; i<G.vexnum; i++) ve[i] = 0;
/*ve[0..G.vexnum-1]=0 ;*/
while(!StackEmpty(S)){
Pop(S,j);Push(T,j);++count;
ArcNode *p;
for(p=G.vertices[j].firstarc;p;p=p->nextarc){
k=p->adjvex;
if(--indegree[k]==0) Push(S,k);
if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info);
}
}
if(count<G.vexnum) return ERROR;
else return OK;
}
SqStack &T;
Status CriticalPath(ALGraph G){
int j; char tag;int k;int dut;
int ee;int el;
ArcNode p;
if(!TopologicalOrder(G,T)) return ERROR;
int i;
for(i=0; i
while(!StackEmpty(T))
for (Pop(T,j),p=G.vertices[j].firstarc; p; p=p->nextarc){
k=p->adjvex; dut=(p->info);
if (vl[k]-dut
}
for(j=0;j
for(p=G.vertices[j].firstarc; p; p=p->nextarc){
k=p->adjvex; dut= (p->info);
ee=ve[j]; el=vl[k]-dut;
tag=(ee==el)? '':' ';
printf("%d %d %d %d %d %c\n",j,k,dut,ee,el,tag);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
ALGraph G;
printf("以下是查找图的关键路径的程序。\n");
TopologicalOrder(G,T);
CriticalPath(G);
return 0;
}
