编写程序,实现用拓扑排序方法求有向无环图中最长路径长度的算法。
思想:
①以maxDist[v]表示以v为结尾的最长路径,G.Edge存储的是图的边的权值,u是v的直接前驱,那么maxDist[v]=max(maxDist[v],maxDist[u]+G.Edge[u][v])表示:maxDist[v]和maxDist[u]+G.Edge[u][v]中最长的一个。
②顶点的计算顺序应该是和拓扑序列的结果一致。
③最长路径一定是从初始入度为0的顶点开始
④maxDist数组中最大值为所求maxPathvalue结果。
代码:
typedef struct { // 图的定义int numV, numEdges; // 图中实际的顶点数和边数char VerticesList[MAXV]; // 顶点表,MAXV为已定义常量int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;//获取每个结点的入度
int *getIndegree(MGraph *G){int *indegree = (int*)malloc(sizeof(int)*G.numV);//初始化每个顶点的入度为0for(int i=0;i<G.numV;i++){indegree[i]=0;} //遍历邻接矩阵for(int i=0;i<G.numV;i++){for(int j=0;j<G.numV;j++){if(G.Edge[i][j] != 0){indegree[j]++;}}} return indegree
}//拓扑遍历
bool topsort(MGraph *G){//topResult用来保存拓扑序列 int *topResult = (int*)malloc(sizeof(int)*G.numV);int topResultIndex = 0;//计算每个结点的入度 int *indegree=getIndegree(G);//找一个入度为0的顶点int stack[MAXSIZE];top=-1;//入度为0的顶点入队for(int i=0;i<G.numV;i++){if(indegree[i]=0){stack[++top]=i;}} //栈不为空时while(top != -1){//完成拓扑排序的个数+1//出栈int v=stack[top--];topResult[topResultIndex++]=v;//由该顶点发出的边到到的顶点,入度均减1for(int i=0;i<G.numV;i++){if(G.Edge[v][i]==1){indegree[i]--;//出现新的入度为0的顶点if(indegree[i]==0){//入队stack[++top]; } }} } free(indegree);return topResult;} int getMaxPath(MGraph *G){int topResult=topsort(G);//进行拓扑排序//maxDist[v]表示以v为结尾的最长路径 int *maxDist=(int*)malloc(sizeof(int)*G.numV);memset(maxDist,0,sizeof(int)*G.numV); int maxPathvalue = -1;//最长路径长度,初始化为-1//按照拓扑排序的顺序进行处理for(int i=0;i<n;++i){int v=topResult[i];for(int u=0;u<G.numV;++u){if(G.Edge[u][v] != 0){//从u到v有路径 maxDist[v]=max(maxDist[v],maxDist[u]+G.Edge[u][v]);if(maxDist[v]>maxPathValue){//记录产生的最大值 maxPathvalue = maxDist[v];}}}} free(topRuslt);free(maxDist);return maxPathvalue;}