#include"stdio.h"
#include"stdlib.h"
#define MAX_VERTEX_NUM 20
#define InfoType int
#define VertexType char
#define MaxSize 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define SElemType int
#define Status int
#define OVERFLOW -1
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)
exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return 1;
}
Status GetTop(SqStack S, SElemType &e)
{
if (S.base == S.top)return 0;
e = (S.top - 1);
return 1;
}
Status Push(SqStack &S, SElemType e)
{
if (S.top - S.base == 0)
{
S.base = (SElemType)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType));
if (!S.base)exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize = STACK_INIT_SIZE + STACKINCREMENT;
}
(S.top++) = e;
return 1;
}
Status Pop(SqStack &S, SElemType &e)
{
if (S.base == S.top) return 0;
e = *--S.top;
return 1;
}
Status StackEmpty(SqStack S)
{
if (S.top - S.base == 0)
return 1;
else
return 0;
}
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
int weight;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertex;
int vexnum, arcnum;
int kind;
}ALGraph;
int indegree[MaxSize];
int ve[MaxSize];//定义事件最早发生 (vertex earliest)
int vl[MaxSize];//定义事件最迟发生 (vertex lastest)
void CreateDGAOV(ALGraph *G)
{
int i, j, k;
ArcNode *e;
printf("输入顶点和边:\n");
scanf_s("%d,%d", &G->vexnum, &G->arcnum);
getchar();
printf("请初始化顶点\n");
for (i = 0; i < G->vexnum; i++)
{
printf("输入顶点字符:\n");
scanf_s("%c", &G->vertex[i].data);
G->vertex[i].firstarc = NULL;
getchar();
}
for (k = 0; k < G->arcnum; k++)
{
printf("输入边(vi,vj)上的顶点序号:\n");
scanf_s("%d,%d", &i, &j);
e = (ArcNode)malloc(sizeof(ArcNode));
e->adjvex = j;
e->nextarc = G->vertex[i].firstarc;
G->vertex[i].firstarc = e;
}
}
Status CreateDGAOE(ALGraph *G)
{
VNode v1, v2;
int i, j, sign1, sign2;
int value;
printf("创建AOE\n");
printf("请输入顶点数和边数:");
scanf_s("%d,%d", &G->vexnum, &G->arcnum);
getchar();
printf("请初始化顶点\n");
for (i = 0; i < G->vexnum; i++)
{
printf("输入顶点字符:\n");
scanf_s("%c", &G->vertex[i].data);
G->vertex[i].firstarc = NULL;
getchar();
}
printf("请初始化弧\n");
printf("输入格式:顶点1 顶点2 权值(表示顶点1邻接到顶点2)\n\n");
for (i = 0; i < G->arcnum; i++)
{
ArcNode *p, *q;
sign1 = -1;
sign2 = -1;
scanf_s("%c%c%d", &v1.data, &v2.data, &value);
getchar();
for (j= 0; j< G->vexnum; j++)
{
if (v1.data == G->vertex[j].data)
sign1 = j;
if (v2.data == G->vertex[j].data)
sign2 = j;
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (!p)
exit(OVERFLOW);
p->nextarc = NULL;
p->weight = value;
p->adjvex = sign2;
q = G->vertex[sign1].firstarc;
if (!q)
G->vertex[sign1].firstarc = p;
else
{
while (q->nextarc != NULL)
q = q->nextarc;
q->nextarc = p;
}
}
return 1;
}
void FindInDegree(ALGraph G)//计算每个节点的入度;
{
ArcNode *p;
int i, k;
for (i = 0; i < G.vexnum; i++)
indegree[i] = 0;
for (i = 0; i < G.vexnum; i++)
{
p = G.vertex[i].firstarc;
while (p != NULL)
{
k = p->adjvex;
indegree[k]++;
p = p->nextarc;
}
}
}
int TopologicalSort(ALGraph &G)//拓扑排序的实现
{
int i, k, count = 0;
SqStack S;
ArcNode *p;
FindInDegree(G);
InitStack(S);
printf("TopologicalSort:");
for (i = 0; i < G.vexnum; i++)//将入度为0的顶点的下标号压入顺序栈S
if (!indegree[i])
Push(S, i);
while (!StackEmpty(S))//如果栈不为空
{
Pop(S, i);//弹出栈顶存储的顶点的下标号
printf("%3c", G.vertex[i].data);//输出下标号为i的顶点中的数据;
count++;//每弹出一次,count就加一,全部输出后应该是vexnum的值,可由这个来判断G有没有环;
for (p = G.vertex[i].firstarc; p; p = p->nextarc)//令p指向顶点的firstarc也就是指向顶点节点后的第一个边结点,等到p指向NULL时循环结束
{
k = p->adjvex;//令k指向p节点的下标号;
if (--indegree[k] == 0)//先将这个节点的入度-1如果=0,那么就将它入栈
Push(S, k);
}
}
if (count < G.vexnum)
{
printf("The directed graph has a loop\n");
return 0;
}
else
return 1;
}
Status TopologicalOrder(ALGraph G, SqStack &T)
{
SqStack S;
ArcNode *p;
int i, x, k, count = 0;
FindInDegree(G);
InitStack(T);
for (i = 0; i < G.vexnum; i++)//将时间最早发生初始化
ve[i] = 0;
for (i = 0; i < G.vexnum; i++)//将入度为0的顶点入栈;
{
if (indegree[i] == 0)
Push(S, i);
}
while (!StackEmpty(S))
{
Pop(S, x);
Push(T, x);//将弹出来的顶点下标压入栈T
count++;
for (p = G.vertex[x].firstarc; p; p = p->nextarc)//注意p指向的是边节点
{
k = p->adjvex;
if (--indegree[k] == 0)
{
Push(S, k);
}
if (ve[x] + (p->weight) > ve[k])//取最早完成时间里的最大值
{
ve[k] = ve[x] + (p->weight);
}
}
if (count < G.vexnum)
return 0;
else
return 1;
}
}
Status CriticalPath(ALGraph G)
{
int i, k, x;
int ee, el;
ArcNode *p;
SqStack T;
InitStack(T);
TopologicalOrder(G, T);
for (i = 0; i < G.vexnum; i++)
vl[i] = ve[G.vexnum - 1];
while (!StackEmpty(T))
{
Pop(T, x);
for (p = G.vertex[i].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
if (vl[x] > vl[k] - p->weight)//取最迟时间中最小值
vl[x] = vl[k] - p->weight;
}
}
for (i = 0; i < G.vexnum; i++);
{
for (p = G.vertex[i].firstarc; p; p = p->nextarc)
{
k = p->adjvex;
ee = ve[i];
el = vl[k] - p->weight;
}
printf("Criticalpath:<%d,%d>length:%d\n", i, k, p->weight);
}
return 1;
}
int main()
{
//ALGraph G;
//CreateDGAOV(&G);
//TopologicalSort(G);
//printf("\n");
ALGraph N;
CreateDGAOE(&N);
CriticalPath(N);
return 0;
}