c语言：求解图的关键路径问题

Question

编写一个c语言程序，解决下面的问题：
问题描述：研究一项大型工程中的子工程关系图，编程判断工程完成的最大天数，以及工程进度控制关键点，保证工期不延期。 试编写利用深度优先遍历有向图实现求关键路径的算法，向链表中插入弧时，要求在链表头插入。
输入：输入包含若干行： 第一行是一个非负整数n，代表顶点数量。已知2＜=n＜=20。 第二行为n个字母，代表每个项点的名称。 第三行是一个非负整数a，代表弧的数量。 第四行到第a+3行，每行均为两个字母和一个整数，分别代表弧的初始点和终端点以及执行该活动所需的时间。
输出：输出若干行。 第一行为工程完成的最大天数。第二行到最后一行为利用深度优先遍历有向图获得的所有关键路径，每条路径占一行。
输入示例1：
6
ABCDEF
8
AB3
AD2
BE1
CA3
CF2
DE2
FD4
FE3
输出示例1：
8
C->F->D->E
输入示例2：
4
ABCD
4
CA2
AD3
СВ3
BD2
输出示例2：
5
C->B->D
C->A->D
数据范围：
输入输出均为 int 范围的整数和字符。

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

问题分析：

这是一个关键路径问题，需要使用深度优先遍历有向图来求解。给定的有向图表示了工程中各子工程的关系，每个子工程之间有弧相连，并且每个弧都有一个执行时间。要求找出工程完成的最大天数，并输出所有的关键路径。

解决方案：

1. 首先，我们需要定义一个结构体来表示有向图中的顶点（子工程）以及弧（关系）。

typedef struct ArcNode {
    int adjvex; // 弧的终点
    int weight; // 弧的执行时间
    struct ArcNode* next; // 下一个弧
} ArcNode;

typedef struct {
    char data; // 顶点的名称
    int earliest; // 最早开始时间
    int latest; // 最晚开始时间
    ArcNode* firstarc; // 第一条弧
} VertexNode;

1. 根据输入，创建有向图的邻接表表示。

int n; // 顶点数量
char vertexNames[20]; // 顶点名称
int a; // 弧的数量

VertexNode vertices[20]; // 存储顶点的数组，最多有20个顶点

// 初始化顶点
for (int i = 0; i < n; i++) {
    vertices[i].data = vertexNames[i];
    vertices[i].earliest = 0;
    vertices[i].latest = INT_MAX;
    vertices[i].firstarc = NULL;
}

// 创建有向图的邻接表表示
for (int i = 0; i < a; i++) {
    char start, end;
    int weight;
    scanf(" %c %c %d", &start, &end, &weight);

    // 在链表头插入弧
    ArcNode* arc = (ArcNode*)malloc(sizeof(ArcNode));
    arc->adjvex = end - 'A';
    arc->weight = weight;
    arc->next = vertices[start - 'A'].firstarc;
    vertices[start - 'A'].firstarc = arc;
}

1. 定义函数 DFS 进行深度优先遍历。

void DFS(int v, int* ve) {
    ArcNode* arc = vertices[v].firstarc;

    while (arc != NULL) {
        int w = arc->adjvex;
        if (ve[w] < ve[v] + arc->weight) {
            ve[w] = ve[v] + arc->weight;
        }

        DFS(w, ve);
        arc = arc->next;
    }
}

1. 找出关键路径。

int vl[20]; // 存储每个顶点的最晚开始时间

// 初始化最晚开始时间
for (int i = 0; i < n; i++) {
    vl[i] = INT_MAX;
}

// 计算每个顶点的最晚开始时间
for (int i = n-1; i >= 0; i--) {
    ArcNode* arc = vertices[i].firstarc;
  
    while (arc != NULL) {
        int w = arc->adjvex;
        if (vl[i] > vl[w] - arc->weight) {
            vl[i] = vl[w] - arc->weight;
        }

        arc = arc->next;
    }
}

// 找出关键路径
for (int i = 0; i < n; i++) {
    ArcNode* arc = vertices[i].firstarc;

    while (arc != NULL) {
        int w = arc->adjvex;
        int e = vertices[i].earliest;
        int l = vl[w] - arc->weight;

        if (e == l) {
            printf("%c->%c ", vertices[i].data, vertices[w].data);
        }

        arc = arc->next;
    }
}

1. 计算工程完成的最大天数。

int maxTime = 0;

for (int i = 0; i < n; i++) {
    if (vertices[i].earliest > maxTime) {
        maxTime = vertices[i].earliest;
    }
}

printf("%d", maxTime);

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct ArcNode {
    int adjvex; // 弧的终点
    int weight; // 弧的执行时间
    struct ArcNode* next; // 下一个弧
} ArcNode;

typedef struct {
    char data; // 顶点的名称
    int earliest; // 最早开始时间
    int latest; // 最晚开始时间
    ArcNode* firstarc; // 第一条弧
} VertexNode;

VertexNode vertices[20]; // 存储顶点的数组，最多有20个顶点

void DFS(int v, int* ve) {
    ArcNode* arc = vertices[v].firstarc;

    while (arc != NULL) {
        int w = arc->adjvex;
        if (ve[w] < ve[v] + arc->weight) {
            ve[w] = ve[v] + arc->weight;
        }

        DFS(w, ve);
        arc = arc->next;
    }
}

int main() {
    int n; // 顶点数量
    char vertexNames[20]; // 顶点名称
    int a; // 弧的数量

    scanf("%d", &n);
    getchar(); // 读取换行符
    for (int i = 0; i < n; i++) {
        scanf("%c", &vertexNames[i]);
    }
    scanf("%d", &a);

    // 初始化顶点
    for (int i = 0; i < n; i++) {
        vertices[i].data = vertexNames[i];
        vertices[i].earliest = 0;
        vertices[i].latest = INT_MAX;
        vertices[i].firstarc = NULL;
    }

    // 创建有向图的邻接表表示
    for (int i = 0; i < a; i++) {
        char start, end;
        int weight;
        scanf(" %c %c %d", &start, &end, &weight);

        // 在链表头插入弧
        ArcNode* arc = (ArcNode*)malloc(sizeof(ArcNode));
        arc->adjvex = end - 'A';
        arc->weight = weight;
        arc->next = vertices[start - 'A'].firstarc;
        vertices[start - 'A'].firstarc = arc;
    }

    int ve[20]; // 存储每个顶点的最早开始时间

    // 初始化最早开始时间
    for (int i = 0; i < n; i++) {
        ve[i] = 0;
    }

    // 计算每个顶点的最早开始时间
    for (int i = 0; i < n; i++) {
        DFS(i, ve);
    }

    int vl[20]; // 存储每个顶点的最晚开始时间

    // 初始化最晚开始时间
    for (int i = 0; i < n; i++) {
        vl[i] = INT_MAX;
    }

    // 计算每个顶点的最晚开始时间
    for (int i = n-1; i >= 0; i--) {
        ArcNode* arc = vertices[i].firstarc;
      
        while (arc != NULL) {
            int w = arc->adjvex;
            if (vl[i] > vl[w] - arc->weight) {
                vl[i] = vl[w] - arc->weight;
            }

            arc = arc->next;
        }
    }

    // 找出关键路径
    for (int i = 0; i < n; i++) {
        ArcNode* arc = vertices[i].firstarc;

        while (arc != NULL) {
            int w = arc->adjvex;
            int e = vertices[i].earliest;
            int l = vl[w] - arc->weight;

            if (e == l) {
                printf("%c->%c ", vertices[i].data, vertices[w].data);
            }

            arc = arc->next;
        }
    }

    // 计算工程完成的最大天数
    int maxTime = 0;

    for (int i = 0; i < n; i++) {
        if (vertices[i].earliest > maxTime) {
            maxTime = vertices[i].earliest;
        }
    }

    printf("\n%d", maxTime);

    return 0;
}

希望以上内容能帮到你解决问题。