#include stdioh#include stdlibh#define MAX_SIZE 10typedef struct int dataMAX_SIZE; int top; Stack;typedef struct node int vertex; struct node next; Node;Node createNodeint v Node new

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

#define MAX_SIZE 10

typedef struct node { int vertex; struct node* next; } Node;

typedef struct { int data[MAX_SIZE]; int top; } Stack;

Node* createNode(int v) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->vertex = v; newNode->next = NULL; return newNode; }

void push(Stack* stack, int item) { if (stack->top == MAX_SIZE - 1) { printf("Stack overflow\n"); return; } stack->data[++stack->top] = item; }

int pop(Stack* stack) { if (stack->top == -1) { printf("Stack underflow\n"); return -1; } return stack->data[stack->top--]; }

int isEmpty(Stack* stack) { return stack->top == -1; }

void topologicalSortUtil(Node* graph[], int v, int visited[], Stack* stack) { visited[v] = 1; Node* temp = graph[v]->next; while (temp != NULL) { if (!visited[temp->vertex]) { topologicalSortUtil(graph, temp->vertex, visited, stack); } temp = temp->next; } push(stack, v); }

void topologicalSort(Node* graph[], int vertices) { int visited[MAX_SIZE] = {0}; Stack stack; stack.top = -1; for (int i = 0; i < vertices; i++) { if (!visited[i]) { topologicalSortUtil(graph, i, visited, &stack); } } while (!isEmpty(&stack)) { printf("%c ", stack.data[stack.top] + 'A'); pop(&stack); } }

int max(int a, int b) { return (a > b) ? a : b; }

void criticalPath(Node* graph[], int vertices, int time[]) { int indegree[MAX_SIZE] = {0}; int earliest[MAX_SIZE] = {0}; int latest[MAX_SIZE] = {0};

for (int i = 0; i < vertices; i++) {
    Node* temp = graph[i]->next;
    while (temp != NULL) {
        indegree[temp->vertex]++;
        temp = temp->next;
    }
}

Stack stack;
stack.top = -1;

for (int i = 0; i < vertices; i++) {
    if (indegree[i] == 0) {
        push(&stack, i);
    }
    earliest[i] = time[i];
}

while (!isEmpty(&stack)) {
    int u = pop(&stack);
    Node* temp = graph[u]->next;
    while (temp != NULL) {
        indegree[temp->vertex]--;
        if (indegree[temp->vertex] == 0) {
            push(&stack, temp->vertex);
        }
        earliest[temp->vertex] = max(earliest[temp->vertex], earliest[u] + time[temp->vertex]);
        temp = temp->next;
    }
}

int projectTime = 0;

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

printf("\n关键路径为：");

for (int i = 0; i < vertices; i++) {
    if (earliest[i] == projectTime) {
        printf("%c ", i + 'A');
    }
}
printf("\n该项目最迟应该合适开始的时间为：%d天\n", projectTime);

}

int main() { int vertices = 9; int time[9] = {3, 2, 4, 5, 8, 3, 5, 10, 2};

Node* graph[9];
for (int i = 0; i < vertices; i++) {
    graph[i] = createNode(i);
}

// 添加边
graph[0]->next = createNode(1);
graph[0]->next->next = createNode(2);
graph[1]->next = createNode(3);
graph[1]->next->next = createNode(4);
graph[2]->next = createNode(5);
graph[2]->next->next = createNode(6);
graph[3]->next = createNode(8);
graph[4]->next = createNode(8);
graph[5]->next = createNode(7);
graph[6]->next = createNode(7);
graph[7]->next = createNode(8);

printf("拓扑排序结果为：");
topologicalSort(graph, vertices);

criticalPath(graph, vertices, time);

return 0;