c语言实现拓扑排序和关键路径时关键路径打印不出来
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define InfoType int
#define MAX_VERTEX_NUM 20
#define VertexType char
#define StackElemType int
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT_SIZE 10
//-----栈的存储结构-----------
typedef struct Stack {
StackElemType* base;//栈底指针
StackElemType* top;//栈顶指针
int StackSize;
}Stack;
//----栈的基本操作------
int InitStack(Stack* S) {
//构造一个空栈
S->base = (StackElemType*)malloc(STACK_INIT_SIZE * sizeof(Stack));
if (!S->base) exit(0);
S->top = S->base;
S->StackSize = STACK_INIT_SIZE;
return OK;
}
int Push(Stack* S, StackElemType e) {
//入栈
if (S->top - S->base == S->StackSize) {
S->base = (StackElemType*)realloc(S->base, (S->StackSize + STACK_INCREMENT_SIZE) * sizeof(Stack));
S->top = S->base + S->StackSize;
S->StackSize += STACK_INCREMENT_SIZE;
}
*(S->top) = e;
S->top++;
return OK;
}
int Pop(Stack* S, StackElemType* e) {
if (S->base == S->top) return ERROR;
*e = *(--S->top);
return OK;
}
int GetSLength(Stack S) {
return S.top - S.base;
}
int StackIsEmpty(Stack S) {
if (S.base == S.top) return OK;
else return 0;
}
//------------------------------
//-----图的临接表储存结构-----
typedef struct ArcNode {
int adjvex;//该弧所指向的顶点的位置
struct ArcNode* nextarc;//指向下一条弧的指针
InfoType info;//弧相关信息的指针
}ArcNode;
typedef struct VNode {
VertexType data;//顶点信息
ArcNode* firstarc;//指向第一条依附于该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct ALGraph {
AdjList Vertices;//邻接表
int vexnum, arcnum;//图的当前顶点数和弧数
int kind;//图的种类标志
}ALGraph;
void FindIndegree(ALGraph G, int*& indegree) {
// 对各个顶点求入度
indegree = (int*)malloc(G.vexnum);
for (int i = 0; i < G.vexnum; i++) {
indegree[i] = 0;
}
for (int i = 0; i < G.vexnum; i++) {
ArcNode* p = G.Vertices[i].firstarc;
while (p)
{
indegree[p->adjvex]++;
p = p->nextarc;
}
}
printf("------顶点入度数组-----\n");
for (int i = 0; i < G.vexnum; i++) {
printf("\t%c的入度为：%d\n", G.Vertices[i].data, indegree[i]);
}
}
int LocateVex(ALGraph G, VertexType v) {
//返回顶点 V在顶点位置下标
for (int i = 0; i < G.vexnum; i++) {
if (v == G.Vertices[i].data)
return i;
}
return 0;
}
int CreateDG(ALGraph* G)
{//采用邻接表表示法，创建有向图G
printf("请输入总顶点数，总边数 :\n");
scanf_s("%d %d", &(G->vexnum), &(G->arcnum));
getchar(); //输入总顶点数，总边数
for (int i = 0; i < G->vexnum; ++i) //输入各点，构造表头结点表
{
printf("请输入顶点字符；\n");
cin >> G->Vertices[i].data;
getchar(); //输入顶点值
G->Vertices[i].firstarc = NULL; //初始化表头结点的指针域为NULL
}
for (int k = 0; k < G->arcnum; ++k) //输入各边，构造邻接表
{
VertexType v1, v2;
printf("输入一条边依附的两个顶点：\n");
cin >> v1 >> v2;
getchar(); //输入一条边依附的两个顶点
int i = LocateVex(*G, v1);
int j = LocateVex(*G, v2);
//确定v1和v2在G中位置，即顶点在G.Vertices中的序号
ArcNode* p1 = (ArcNode*)malloc(sizeof(ArcNode)); //生成一个新的边结点*p1
p1->adjvex = j; //邻接点序号为j
p1->nextarc = G->Vertices[i].firstarc; //前插法
G->Vertices[i].firstarc = p1;
//将新结点*p1插入顶点vi的边表头部
/*ArcNode* p2 = (ArcNode*)malloc(sizeof(ArcNode)); //生成另一个对称的新的边结点*p2
p2->adjvex = i; //邻接点序号为i
p2->nextarc = G->Vertices[j].firstarc; //前插法
G->Vertices[j].firstarc = p2;
//将新结点*p2插入顶点vj的边表头部 */
} //for
return OK;
}
int CreateDN(ALGraph* G)
{//采用邻接表表示法，创建有向图G
printf("请输入总顶点数，总边数 :\n");
scanf_s("%d %d", &(G->vexnum), &(G->arcnum));
getchar(); //输入总顶点数，总边数
for (int i = 0; i < G->vexnum; ++i) //输入各点，构造表头结点表
{
printf("请输入顶点字符；\n");
cin >> G->Vertices[i].data;
getchar(); //输入顶点值
G->Vertices[i].firstarc = NULL; //初始化表头结点的指针域为NULL
}
for (int k = 0; k < G->arcnum; ++k) //输入各边，构造邻接表
{
VertexType v1, v2;
int w;
printf("输入一条边依附的两个顶点和权重：\n");
cin >> v1 >> v2 >> w;
getchar(); //输入一条边依附的两个顶点
int i = LocateVex(*G, v1);
int j = LocateVex(*G, v2);
//确定v1和v2在G中位置，即顶点在G.Vertices中的序号
ArcNode* p1 = (ArcNode*)malloc(sizeof(ArcNode)); //生成一个新的边结点*p1
p1->adjvex = j;
p1->info = w; //邻接点序号为j
p1->nextarc = G->Vertices[i].firstarc; //前插法
G->Vertices[i].firstarc = p1;
//将新结点*p1插入顶点vi的边表头部
/*ArcNode* p2 = (ArcNode*)malloc(sizeof(ArcNode)); //生成另一个对称的新的边结点*p2
p2->adjvex = i; //邻接点序号为i
p2->nextarc = G->Vertices[j].firstarc; //前插法
G->Vertices[j].firstarc = p2;
//将新结点*p2插入顶点vj的边表头部 */
} //for
return OK;
}
int CreateUDG(ALGraph* G)
{//采用邻接表表示法，创建无向图G
printf("请输入总顶点数，总边数 :\n");
scanf_s("%d %d", &(G->vexnum), &(G->arcnum));
getchar(); //输入总顶点数，总边数
for (int i = 0; i < G->vexnum; ++i) //输入各点，构造表头结点表
{
printf("请输入顶点字符；\n");
cin >> G->Vertices[i].data;
getchar(); //输入顶点值
G->Vertices[i].firstarc = NULL; //初始化表头结点的指针域为NULL
}
for (int k = 0; k < G->arcnum; ++k) //输入各边，构造邻接表
{
VertexType v1, v2;
printf("输入一条边依附的两个顶点：\n");
cin >> v1 >> v2 ;
getchar(); //输入一条边依附的两个顶点
int i = LocateVex(*G, v1);
int j = LocateVex(*G, v2);
//确定v1和v2在G中位置，即顶点在G.Vertices中的序号
ArcNode* p1 = (ArcNode*)malloc(sizeof(ArcNode)); //生成一个新的边结点*p1
p1->adjvex = j; //邻接点序号为j
p1->nextarc = G->Vertices[i].firstarc; //前插法
G->Vertices[i].firstarc = p1;
//将新结点*p1插入顶点vi的边表头部
ArcNode* p2 = (ArcNode*)malloc(sizeof(ArcNode)); //生成另一个对称的新的边结点*p2
p2->adjvex = i; //邻接点序号为i
p2->nextarc = G->Vertices[j].firstarc; //前插法
G->Vertices[j].firstarc = p2;
//将新结点*p2插入顶点vj的边表头部
} //for
return OK;
}
int TopologicalSort(ALGraph G) {
//若G无回路，则输出G的顶点的拓扑排序序列并返回OK,否则返回ERROR
int* indegree;
Stack S;
int e = 0;
FindIndegree(G, indegree);
InitStack(&S);
for (int i = 0; i < G.vexnum; i++) {
if (indegree[i] == 0) Push(&S, i); //度为0的节点入栈
}
int count = 0;//对输出结点记数
printf("---------拓扑序列为-------\n");
while (!StackIsEmpty(S))
{
Pop(&S, &e);//e为对应顶点下标
printf("%c->", G.Vertices[e].data);
//选择一个没有前驱的顶点并输出
count++;
ArcNode* p;
for (p = G.Vertices[e].firstarc; p; p = p->nextarc) {
int k = p->adjvex;
if (!(--indegree[k])) Push(&S, k);
//删除顶点和所有以该顶点为尾的弧
//对i号顶点的每个邻接点的入度减一、如果减为0，则入栈
}
}
if (count < G.vexnum) return ERROR;
else return OK;
}
int TopologicalSortOrder(ALGraph G, Stack& T, int*& ve, int*& vl) {
//若G无回路，则输出G的顶点的拓扑排序序列并返回OK,否则返回ERROR
int* indegree;
Stack S;
int e = 0;
FindIndegree(G, indegree);
InitStack(&S);
for (int i = 0; i < G.vexnum; i++) {
if (indegree[i] == 0) Push(&S, i); //度为0的节点入栈
}
InitStack(&T);
int count = 0;//对输出结点记数
ve = (int*)malloc(G.vexnum);
vl = (int*)malloc(G.vexnum);
printf("---------拓扑序列为-------\n");
while (!StackIsEmpty(S))
{
Pop(&S, &e);//e为对应顶点下标
Push(&T, e);
printf("%c->", G.Vertices[e].data);
//选择一个没有前驱的顶点并输出
count++;
ArcNode* p;
for (p = G.Vertices[e].firstarc; p; p = p->nextarc) {
int k = p->adjvex;
if (!(--indegree[k])) Push(&S, k);
if (ve[e] + (p->info) > ve[k]) ve[k] = ve[e] + (p->info);
//删除顶点和所有以该顶点为尾的弧
//对i号顶点的每个邻接点的入度减一、如果减为0，则入栈
}
}
if (count < G.vexnum) return ERROR;// 该图为有向网
else return OK;
}
void Display(ALGraph G) {
printf("--------图的临接表----\n");
for (int i = 0; i < G.vexnum; i++) {
printf("\t%c", G.Vertices[i].data);
if (G.Vertices->firstarc == NULL)
printf("->^");
else {
ArcNode* p = G.Vertices[i].firstarc;
while (p) {
printf("->%d(%d)", p->adjvex, (p->info));
p = p->nextarc;
}
if (p == NULL)
printf("->^");
printf("\n");
}
}
}
int CriticalPath(ALGraph G, Stack T, int*& ve, int*& vl) {
if (!TopologicalSortOrder(G, T, ve, vl)) return ERROR;
int i, j, e, l;
for (i = 0; i < G.vexnum; i++)
ve[i] = 0;// 初始化顶点的最早发生时间
ArcNode* p;
for (i = 0; i < G.vexnum; i++) {
p = G.Vertices[i].firstarc;
while (p != NULL) { //根据k的邻接点，更新k的最迟发生时间
j = p->adjvex; //j为邻接顶点的序号
if (vl[i] > vl[j] - p->info) //更新顶点k的最早发生时间vl[k]
vl[i] = vl[j] - p->info; //应该取小的--->不然会延误工期，需要考虑其他路线
p = p->nextarc; //p指向k的下一个邻接顶点
}
}
/*-----------------判断每一活动是否为关键活动-----------------*/
printf("关键路径如下:\n");
for (i = 0; i < G.vexnum; i++) {
p = G.Vertices[i].firstarc; //p指向k的第一个邻接顶点
while (p != NULL) {
j = p->adjvex; //j为i的邻接顶点的序号
e = ve[i]; //计算活动<vi,vj>的最早开始时间 相当于弧的最早发生时间
l= vl[j] - p->info; //计算活动<vi,vj>的最迟开始时间
if (ve == vl) //若为关键活动则输出<vi,vj>
printf("<%c,%c>", G.Vertices[i].data, G.Vertices[j].data);
p = p->nextarc; //p指向i的下一个邻接顶点
}
}
printf(" \n");
return OK;
}
int main() {
ALGraph G;
Stack T;
InitStack(&T);
CreateDN(&G);
int* ve;
int* vl;
Display(G);
CriticalPath(G, T, ve, vl);
return 0;
}
只有关键路径的函数有错误
使他正确成功运行