Why is topological sorting needed?
:The reason is because topological sorting can ensure that the dependencies of our activities are calculated in order, that is, the predecessor of a node must be before the node.
Interface
#include <stdio.h>
#include <stdlib.h>
#define MAX 65535
typedef struct Graph {
char* vexs;
int** arcs;
int vexNum;
int arcNum;
} Graph;
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* initStack();//Initialization of stack
int isEmpty(Node* stack);//Determine whether the stack is empty
void push(Node* stack, int data);//Push to the stack
int pop(Node* stack);//Pop from the stack
int* findInDegrees(Graph* G);//Find in-degree
Graph* initGraph(int vexNum);//Initialization of graph
int* topologicalSort(Graph* G);//Topological sorting and return key results
void createGraph(Graph* G, char* vexs, int* arcs);//Create graph
int getIndex(Graph* G, int* top, int i);//Get its index in the topology array
void criticalPath(Graph* G);//Get the critical path
void DFS(Graph* G, int* visited, int index);//Depth first traversal
Interface implementation
int isEmpty(Node* stack) {
if (stack->next == NULL) {
return 1;
}
else {
return 0;
}
}
void push(Node* stack, int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = stack->next;
stack->next = node;
stack->data + + ;
}
int pop(Node* stack) {
if (!isEmpty(stack)) {
Node* node = stack->next;
stack->next = node->next;
return node->data;
}
else {
return -1;
}
}
int* findInDegrees(Graph* G) {
int* inDegrees = (int*)malloc(sizeof(int) * G->vexNum);
for (int i = 0; i < G->vexNum; i + + ) {
inDegrees[i] = 0;
}
for (int i = 0; i < G->vexNum; i + + ) {
for (int j = 0; j < G->vexNum; j + + ) {
if (G->arcs[i][j] > 0 & amp; & amp; G->arcs[i][j] != MAX)
inDegrees[j] = inDegrees[j] + 1;
}
}
return inDegrees;
}
int* topologicalSort(Graph* G) {
int index = 0;
int* top = (int*)malloc(sizeof(int) * G->vexNum);
int* inDegrees = findInDegrees(G);
Node* stack = initStack();
for (int i = 0; i < G->vexNum; i + + ) {
if (inDegrees[i] == 0) {
push(stack, i);
}
}
while (!isEmpty(stack)) {
int vex = pop(stack);
top[index + + ] = vex;
for (int i = 0; i < G->vexNum; i + + ) {
if (G->arcs[vex][i] > 0 & amp; & amp; G->arcs[vex][i] != MAX) {
inDegrees[i] = inDegrees[i] - 1;
if (inDegrees[i] == 0) push(stack, i);
}
}
}
for (int i = 0; i < index; i + + ) {
printf("%c ", G->vexs[top[i]]);
}
printf("\\
");
return top;
}
Graph* initGraph(int vexNum) {
Graph* G = (Graph*)malloc(sizeof(Graph));
G->vexs = (char*)malloc(sizeof(char) * vexNum);
G->arcs = (int**)malloc(sizeof(int*) * vexNum);
for (int i = 0; i < vexNum; i + + ) {
G->arcs[i] = (int*)malloc(sizeof(int) * vexNum);
}
G->vexNum = vexNum;
G->arcNum = 0;
return G;
}
void createGraph(Graph* G, char* vexs, int* arcs) {
for (int i = 0; i < G->vexNum; i + + ) {
G->vexs[i] = vexs[i];
for (int j = 0; j < G->vexNum; j + + ) {
G->arcs[i][j] = *(arcs + i * G->vexNum + j);
if (G->arcs[i][j] > 0 & amp; & amp; G->arcs[i][j] != MAX) G->arcNum + + ;
}
}
}
int getIndex(Graph* G, int* top, int i) {
//Want to know the index of i in the topological array
int j;
for (j = 0; j < G->vexNum; j + + ) {
if (top[j] == i) {
// Found it now
break;
}
}
return j;
}
void criticalPath(Graph* G) {
//Get the topological sequence first
\t//Why?
//Because topological sorting can ensure that the dependencies of our activities are calculated in order, that is, the predecessors of all nodes must be before him.
int* top = topologicalSort(G);
//Open early array and late array, both corresponding to the value of topological sequence
int* early = (int*)malloc(sizeof(int) * G->vexNum);
int* late = (int*)malloc(sizeof(int) * G->vexNum);
//Initialization
for (int i = 0; i < G->vexNum; i + + ) {
early[i] = 0;
late[i] = 0;
}
//Calculate the earliest occurrence time
for (int i = 0; i < G->vexNum; i + + ) {
int max = 0;//Calculating the earliest occurrence time requires the maximum value of the previous path
for (int j = 0; j < G->vexNum; j + + ) {
if (G->arcs[j][top[i]] > 0 & amp; & amp; G->arcs[j][top[i]] != MAX) {
int index = getIndex(G, top, j);//Find its index in the topological sequence
if (early[index] + G->arcs[j][top[i]] > max) {
max = early[index] + G->arcs[j][top[i]];
}
}
}
early[i] = max;
}
//Calculate the latest occurrence time
late[(G->vexNum) - 1] = early[(G->vexNum) - 1];//Both are equal
for (int i = (G->vexNum) - 2; i >= 0; i--) {
int min = MAX;
for (int j = 0; j < G->vexNum; j + + ) {
if (G->arcs[top[i]][j] > 0 & amp; & amp; G->arcs[top[i]][j] != MAX) {
int index = getIndex(G, top, j);
if (late[index] - G->arcs[top[i]][j] < min) {
min = late[index] - G->arcs[top[i]][j];
}
}
}
late[i] = min;
}
for (int i = 0; i < G->vexNum; i + + ) {
printf("%d ", early[i]);//Output early array
}
printf("\\
");
for (int i = 0; i < G->vexNum; i + + ) {
printf("%d ", late[i]);//Output the late array
}
//Find the critical path (time margin==0)
for (int i = 0; i < G->vexNum; i + + ) {
for (int j = 0; j < G->vexNum; j + + ) {
if (G->arcs[i][j] > 0 & amp; & amp; G->arcs[i][j] != MAX) {
//Why is G->arcs[i][j] here?
//Because the path is required at this time, it is based on the vertex set.
int start = getIndex(G, top, i);
int end = getIndex(G, top, j);
if (early[start] == (late[end] - G->arcs[i][j])) {//The earliest occurrence time of arc - the latest occurrence time of arc
printf("start=%d end=%d\\
", i, j);//Output if equal
}
}
}
}
}
void DFS(Graph* G, int* visited, int index) {
printf("%c ", G->vexs[index]);
visited[index] = 1;
for (int i = 0; i < G->vexNum; i + + ) {
if (G->arcs[index][i] > 0 & amp; & amp; G->arcs[index][i] != MAX & amp; & amp; !visited[i]) {
DFS(G, visited, i);
}
}
}
Test
int main() {
Graph* G = initGraph(9);
int* visited = (int*)malloc(sizeof(int) * G->vexNum);
for (int i = 0; i < G->vexNum; i + + ) visited[i] = 0;
int arcs[9][9] = {
0, 6, 4, 5, MAX, MAX, MAX, MAX, MAX, MAX, 0, MAX, MAX, 1,
MAX, MAX, MAX, MAX, MAX, MAX, 0, MAX, 1, MAX, MAX, MAX, MAX, MAX,
MAX, MAX, 0, MAX, 2, MAX, MAX, MAX, MAX, MAX, MAX, MAX, 0, MAX,
9, 7, MAX, MAX, MAX, MAX, MAX, MAX, 0, MAX, 4, MAX, MAX, MAX,
MAX, MAX, MAX, MAX, 0, MAX, 2, MAX, MAX, MAX, MAX, MAX, MAX, MAX,
0, 4, MAX, MAX, MAX, MAX, MAX, MAX, MAX, MAX, 0 };
createGraph(G, (char*)"012345678", (int*)arcs);
DFS(G, visited, 0);
printf("\\
");
criticalPath(G);
return 0;
}