数据结构之关键路径

    xiaoxiao2022-06-30  140

    今天看的关键路径,总结一下学的关键路径。

    一,什么是关键路径

       把开始顶点到完成顶点的最长路径称为关键路径。

    二,如何求关键路径

    (首先先说明,作为一个有关键路径的图,图中的每条边带有权值,这些权值假设为活动持续的时间,顶点表示一个活动的开始或者结束这样一个事件)。

    1,作为一个关键路径,需要用到的第一个函数是拓补排序的函数,并且作为一个图如果它有关键路径,那么它不能出现回路,所以,拓补排序中要判断,如果出现回路就不用判断关键路径。

    2.在拓补排序完成之后,会有一个数组x[n]按顺序存储入度为0的点,用这些点先求出与之相邻的顶点的最早时间,用数组ee[n]存储,其中,假设ee[i]与ee[j]相关联,那么ee[j]=max(ee[i]+Map[i][j]);其中二维数组map存储的从i到j的边的权值。

    3.ee[n]求出之后,需要求出每个活动最晚开始时间(但是这个时间不能耽误下一个活动的开始),这个时间需要从后往前求,因为最后一位的时间是确定的。

    4.当最晚时间与最早时间求出之后,关键路径的点就是最晚时间与最早时间相等的点,只需要进行判断输出即可。

    下面是自己写的代码,没有结构体啥的,所以显得有些乱。。。。

    #include <iostream> #include <cstdio> #include <cstring> using namespace std; int Map[110][110]; int indegree[110]; int x[110]; int value[110]; int n; int Findnum(int top) { int cnt=0; while(top!=-1) { int p=top; top=indegree[top]; x[cnt++]=p; for (int i=1;i<=n;++i) { if (Map[p][i]!=0) { value[i]-=1; if(value[i]==0) { indegree[i]=top; top=i; } } } } if (cnt<n)return 0; return 1; } int tobosort() { memset(indegree,0,sizeof(indegree)); memset(x,0,sizeof(x)); int top=-1; for (int i=1;i<=n;++i) { if (value[i]==0) { indegree[i]=top; top=i; } } int nd=0; nd=Findnum(top); if(nd==0)return 0; return 1; }//以上两个函数是用来求拓补排序的 void getee(int *ee) { memset(ee,0,sizeof(int)*100); for (int i=0;i<n;++i) { int k=x[i]; for (int j=1;j<=n;j++) { if (Map[k][j]!=0&&ee[j]<ee[k]+Map[k][j]) { ee[j]=ee[k]+Map[k][j]; } } } }//求最早的时间 void getll(int * ee,int * ll) { for (int i=1;i<=n;++i) { ll[i]=ee[x[n-1]]; } for (int i=n-1;i>=1;--i) { int k=x[i]; for (int j=1;j<=n;++j) { if (Map[k][j]!=0&&ll[k]>ll[j]-Map[k][j]) { ll[k]=ll[j]-Map[k][j]; } } } }//求最晚的时间 int guanjian() { int ee[110]; int ll[110]; if (tobosort()==0) return 0; getee(ee); for(int i=1;i<=n;++i) { cout<<ee[i]<<" "; } cout<<endl; getll(ee,ll); for (int i=1;i<=n;++i) { cout<<ll[i]<<" "; } cout<<endl; for (int i=1;i<=n;++i) { for (int j=1;j<=n;++j) { if (ee[i]==(ll[j]-Map[i][j])&&Map[i][j]!=0) { cout<<"关键路径为"<<i<<" "<<j<<endl; } } } return 1; }//求关键路径的函数

    转载请注明原文地址: https://ju.6miu.com/read-1126246.html

    最新回复(0)