数据结构 C 代码 7.4: 关键路径

摘要: 关键路径算法有一定的难度, 先从左到右, 再从右到左.

1. 代码

将 Java 代码https://blog.csdn.net/minfanphd/article/details/116975772 稍作整理, 告诉 DeepSeek: 将如下 Java 代码翻译为 C 代码.

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<stdbool.h>#defineMAX_DISTANCE10000typedefstructIntMatrix{int**data;introws;intcols;}IntMatrix;IntMatrix*IntMatrix_create(introws,intcols);IntMatrix*IntMatrix_copy(constIntMatrix*src);IntMatrix*IntMatrix_identity(introws);voidIntMatrix_free(IntMatrix*matrix);voidIntMatrix_print(IntMatrix*matrix);intIntMatrix_add(IntMatrix*self,constIntMatrix*other);IntMatrix*IntMatrix_multiply(constIntMatrix*a,constIntMatrix*b);typedefstructNet{intnumNodes;IntMatrix*weightMatrix;}Net;Net*Net_create(intnumNodes);Net*Net_create_from_matrix(int**matrix,introws,intcols);voidNet_free(Net*net);bool*criticalPath(Net*net);// IntMatrix 函数实现IntMatrix*IntMatrix_create(introws,intcols){IntMatrix*matrix=(IntMatrix*)malloc(sizeof(IntMatrix));matrix->rows=rows;matrix->cols=cols;matrix->data=(int**)malloc(rows*sizeof(int*));for(inti=0;i<rows;i++){matrix->data[i]=(int*)malloc(cols*sizeof(int));memset(matrix->data[i],0,cols*sizeof(int));}returnmatrix;}IntMatrix*IntMatrix_copy(constIntMatrix*src){IntMatrix*dest=IntMatrix_create(src->rows,src->cols);for(inti=0;i<src->rows;i++){memcpy(dest->data[i],src->data[i],src->cols*sizeof(int));}returndest;}IntMatrix*IntMatrix_identity(introws){IntMatrix*matrix=IntMatrix_create(rows,rows);for(inti=0;i<rows;i++){matrix->data[i][i]=1;}returnmatrix;}voidIntMatrix_free(IntMatrix*matrix){for(inti=0;i<matrix->rows;i++){free(matrix->data[i]);}free(matrix->data);free(matrix);}voidIntMatrix_print(IntMatrix*matrix){printf("[");for(inti=0;i<matrix->rows;i++){if(i>0)printf(" ");printf("[");for(intj=0;j<matrix->cols;j++){printf("%d",matrix->data[i][j]);if(j<matrix->cols-1)printf(", ");}printf("]");if(i<matrix->rows-1)printf(",\n");}printf("]\n");}intIntMatrix_add(IntMatrix*self,constIntMatrix*other){if(self->rows!=other->rows||self->cols!=other->cols){fprintf(stderr,"Matrix dimensions mismatch\n");return-1;}for(inti=0;i<self->rows;i++){for(intj=0;j<self->cols;j++){self->data[i][j]+=other->data[i][j];}}return0;}IntMatrix*IntMatrix_multiply(constIntMatrix*a,constIntMatrix*b){if(a->cols!=b->rows){fprintf(stderr,"Matrix multiplication dimensions mismatch\n");returnNULL;}IntMatrix*result=IntMatrix_create(a->rows,b->cols);for(inti=0;i<a->rows;i++){for(intj=0;j<b->cols;j++){for(intk=0;k<a->cols;k++){result->data[i][j]+=a->data[i][k]*b->data[k][j];}}}returnresult;}// Net 函数实现Net*Net_create(intnumNodes){Net*net=(Net*)malloc(sizeof(Net));net->numNodes=numNodes;net->weightMatrix=IntMatrix_create(numNodes,numNodes);for(inti=0;i<numNodes;i++){for(intj=0;j<numNodes;j++){net->weightMatrix->data[i][j]=MAX_DISTANCE;}}returnnet;}Net*Net_create_from_matrix(int**matrix,introws,intcols){Net*net=(Net*)malloc(sizeof(Net));net->weightMatrix=IntMatrix_create(rows,cols);net->numNodes=rows;for(inti=0;i<rows;i++){memcpy(net->weightMatrix->data[i],matrix[i],cols*sizeof(int));}returnnet;}voidNet_free(Net*net){IntMatrix_free(net->weightMatrix);free(net);}bool*criticalPath(Net*net){intnumNodes=net->numNodes;int*tempInDegrees=(int*)calloc(numNodes,sizeof(int));int*tempEarliestTime=(int*)calloc(numNodes,sizeof(int));int*tempOutDegrees=(int*)calloc(numNodes,sizeof(int));int*tempLatestTime=(int*)malloc(numNodes*sizeof(int));bool*result=(bool*)calloc(numNodes,sizeof(bool));// 计算入度for(inti=0;i<numNodes;i++){for(intj=0;j<numNodes;j++){if(net->weightMatrix->data[i][j]!=-1){tempInDegrees[j]++;}}}// 拓扑排序计算最早时间int*inDegreesCopy=(int*)malloc(numNodes*sizeof(int));memcpy(inDegreesCopy,tempInDegrees,numNodes*sizeof(int));for(inti=0;i<numNodes;i++){if(inDegreesCopy[i]!=0)continue;for(intj=0;j<numNodes;j++){if(net->weightMatrix->data[i][j]!=-1){intnewTime=tempEarliestTime[i]+net->weightMatrix->data[i][j];if(newTime>tempEarliestTime[j]){tempEarliestTime[j]=newTime;}inDegreesCopy[j]--;}}}printf("Earliest time: ");for(inti=0;i<numNodes;i++){printf("%d, ",tempEarliestTime[i]);}printf("\n");// 计算出度for(inti=0;i<numNodes;i++){for(intj=0;j<numNodes;j++){if(net->weightMatrix->data[i][j]!=-1){tempOutDegrees[i]++;}}}// 初始化最晚时间intcriticalTime=tempEarliestTime[numNodes-1];for(inti=0;i<numNodes;i++){tempLatestTime[i]=criticalTime;}// 反向拓扑排序计算最晚时间int*outDegreesCopy=(int*)malloc(numNodes*sizeof(int));memcpy(outDegreesCopy,tempOutDegrees,numNodes*sizeof(int));for(inti=numNodes-1;i>=0;i--){if(outDegreesCopy[i]!=0)continue;for(intj=0;j<numNodes;j++){if(net->weightMatrix->data[j][i]!=-1){intnewTime=tempLatestTime[i]-net->weightMatrix->data[j][i];if(newTime<tempLatestTime[j]){tempLatestTime[j]=newTime;}outDegreesCopy[j]--;}}}printf("Latest time: ");for(inti=0;i<numNodes;i++){printf("%d, ",tempLatestTime[i]);}printf("\n");// 确定关键路径for(inti=0;i<numNodes;i++){result[i]=(tempEarliestTime[i]==tempLatestTime[i]);}free(tempInDegrees);free(tempEarliestTime);free(tempOutDegrees);free(tempLatestTime);free(inDegreesCopy);free(outDegreesCopy);returnresult;}// 测试代码intmain(){inttempMatrix3[6][6]={{-1,3,2,-1,-1,-1},{-1,-1,-1,2,3,-1},{-1,-1,-1,4,-1,3},{-1,-1,-1,-1,-1,2},{-1,-1,-1,-1,-1,1},{-1,-1,-1,-1,-1,-1}};// 转换为二维指针数组int**matrix=(int**)malloc(6*sizeof(int*));for(inti=0;i<6;i++){matrix[i]=(int*)malloc(6*sizeof(int));memcpy(matrix[i],tempMatrix3[i],6*sizeof(int));}Net*net=Net_create_from_matrix(matrix,6,6);bool*critical=criticalPath(net);printf("Critical nodes: ");for(inti=0;i<6;i++){if(critical[i])printf("%d ",i);}printf("\n");// 释放内存for(inti=0;i<6;i++)free(matrix[i]);free(matrix);Net_free(net);free(critical);return0;}

2. 运行结果

Earliest time:0,3,2,6,6,8,Latest time:0,4,2,6,7,8,Critical nodes:0235

3. 小结

• 主要看 criticalPath 函数.
• 逻辑有一点难度, 当然, 也很有趣.
• 注意: 当前代码有 bug, 我要找时间来重新弄一下.