数据结构关键路径问题求解代码 c语言
时间: 2023-12-19 09:31:01 浏览: 36
以下是使用C语言实现数据结构关键路径问题求解的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define OK 1
#define ERROR 0
#define INFINITY 65535 // 用65535来代表无穷大
typedef int Status;
typedef int VRType; // 弧上的权值类型
typedef char VertexType; // 顶点类型
// 边表结点
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
VRType weight; // 弧的权值
} ArcNode;
// 顶点表结点
typedef struct VNode {
VertexType data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 图
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的当前顶点数和弧数
} ALGraph;
// 存储拓扑序列的栈
typedef struct {
int *base; // 栈底指针
int *top; // 栈顶指针
int stacksize; // 栈可用的最大容量
} SqStack;
// 初始化栈
Status InitStack(SqStack *S, int size) {
S->base = (int *)malloc(size * sizeof(int));
if (!S->base) {
return ERROR;
}
S->top = S->base;
S->stacksize = size;
return OK;
}
// 判断栈是否为空
Status StackEmpty(SqStack *S) {
if (S->top == S->base) {
return OK;
}
return ERROR;
}
// 入栈
Status Push(SqStack *S, int e) {
if (S->top - S->base == S->stacksize) {
return ERROR;
}
*(S->top) = e;
S->top++;
return OK;
}
// 出栈
Status Pop(SqStack *S, int *e) {
if (S->top == S->base) {
return ERROR;
}
S->top--;
*e = *(S->top);
return OK;
}
// 拓扑排序
Status TopologicalSort(ALGraph *G, SqStack *T) {
int i, j, k, count = 0;
int ve[MAX_VERTEX_NUM] = {0}; // 存储各个顶点的最早开始时间
ArcNode *p;
SqStack S;
// 初始化栈
InitStack(&S, G->vexnum);
// 计算ve数组
for (i = 0; i < G->vexnum; i++) {
p = G->vertices[i].firstarc;
while (p) {
if (ve[i] + p->weight > ve[p->adjvex]) {
ve[p->adjvex] = ve[i] + p->weight;
}
p = p->nextarc;
}
}
// 将入度为0的顶点入栈
for (i = 0; i < G->vexnum; i++) {
if (!ve[i]) {
Push(&S, i);
}
}
// 拓扑排序
while (!StackEmpty(&S)) {
Pop(&S, &j);
Push(T, j);
count++;
p = G->vertices[j].firstarc;
while (p) {
k = p->adjvex;
if (--G->vertices[k].data == 0) {
Push(&S, k);
}
if (ve[j] + p->weight > ve[k]) {
ve[k] = ve[j] + p->weight;
}
p = p->nextarc;
}
}
if (count < G->vexnum) {
return ERROR;
}
return OK;
}
// 计算关键路径
Status CriticalPath(ALGraph *G) {
int i, j, k, e, l;
int vl[MAX_VERTEX_NUM] = {0}; // 存储各个顶点的最晚开始时间
ArcNode *p;
SqStack T;
InitStack(&T, G->vexnum);
if (!TopologicalSort(G, &T)) {
return ERROR;
}
// 计算vl数组
for (i = 0; i < G->vexnum; i++) {
vl[i] = ve[G->vexnum - 1];
}
while (!StackEmpty(&T)) {
Pop(&T, &j);
p = G->vertices[j].firstarc;
while (p) {
k = p->adjvex;
if (vl[k] - p->weight < vl[j]) {
vl[j] = vl[k] - p->weight;
}
p = p->nextarc;
}
}
// 输出关键路径
for (j = 0; j < G->vexnum; j++) {
p = G->vertices[j].firstarc;
while (p) {
k = p->adjvex;
e = p->weight;
l = ve[j];
if (l + e == vl[k]) {
printf("%c -> %c\n", G->vertices[j].data, G->vertices[k].data);
}
p = p->nextarc;
}
}
return OK;
}
int main() {
ALGraph G;
int i, j, k, w;
ArcNode *p;
// 输入顶点数和弧数
printf("请输入顶点数和弧数:");
scanf("%d%d", &G.vexnum, &G.arcnum);
// 输入顶点信息
printf("请输入顶点信息:");
for (i = 0; i < G.vexnum; i++) {
scanf(" %c", &G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
// 输入弧信息
printf("请输入弧信息:");
for (k = 0; k < G.arcnum; k++) {
printf("请输入第%d条弧的起点、终点和权值:", k + 1);
scanf("%d%d%d", &i, &j, &w);
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = w;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
G.vertices[j].data++;
}
CriticalPath(&G);
return 0;
}
```