自己初始化邻接表数据有问题 （注视是瞎写的）如果还有其他问题也请帮忙改一下

Question

#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;
}

Answer 1

https://blog.csdn.net/Wonz5130/article/details/80671569