拓扑排序解决先行课问题

　　伪代码：

while(找到第i批入度为零的节点)
{
indegree[第i批节点];
将第i批节点作为一个学期的课程输出;
indegree[第i批节点指向的所有节点]--;
}

class course//course类
{
public:
    course(int n=1)
    {//定义course类的构造函数
        num=n;
        indegree=new int[n+1];
        edge=new vector<int>[n+1];
        memset(indegree,0,sizeof(int)*(n+1));//将indegree数组置零
    }
    void getIndegree();//根据输入的先行课集合得到各个节点的入度，放入数组indegree
    void topologicalSort();//进行拓扑排序，得到各个学期的课程
private:
    stack<int> zeroInd;//用来记录每一批入度为零的节点
    int *indegree;//记录各节点入度
    int num;//记录课程的数量
    vector<int> *edge;//记录各个节点所指向的下一个节点
    bool findZeroInD();//私有函数，找出入度为零的节点放入栈zeroInd
};

int indegree[200]={0};

indegree=new int[n+1]; edge=new vector<int>[n+1];

　　就需要利用memset函数对其进行置零操作，一开始我是直接memset(indegree,0,sizeof(indegree));，发现得不到正确结果。后来想到问题出在sizeof(indegree)上，因为这时indegree是作为一个int指针变量，而不是作为数组，所以此时sizeof(indegree)应该是int*类型变量的大小，一般为四个字节，而不是等于我们所分配的内存空间的大小，如果要表示分配的内存空间大小，则需要sizeof(int)*(n+1)，更改为memset(indegree,0,sizeof(int)*(n+1));就可以得出正确结果。可能有人会疑问，之前用sizeof(数组名)也可以得出正确结果来，那是因为一开始声明时就是声明的数组名，例如int a[10];，而在本题中，indegree实际为int类型的指针。

　　下面给出各个成员函数的实现

void course::getIndegree()
{
int x,y;
while(scanf("%d%d",&x,&y)==2)
{
if(x==y) continue;
edge[x].push_back(y);
indegree[y]++;
//printf("%d %d %dn",x,y,indegree[y]);
}
}
bool course::findZeroInD()
{
int cnt=0;
for(int i=1;i<=num;i++)
{
if(!indegree[i])
{
//printf("%dn",i);
zeroInd.push(i);
indegree[i]--;
cnt++;
}
}
return cnt!=0;
}
void course::topologicalSort()
{
int semester=1,cnt=num;
while(findZeroInD())
{
printf("Semester %d :n",semester++);
int t;
while(!zeroInd.empty())
{
t=zeroInd.top();zeroInd.pop();cnt--;
printf("%d ",t);
for(int i=0;i<edge[t].size();i++)
{
indegree[edge[t][i]]--;
}
}
putchar('n');
}
if(cnt==0)
printf("最少需要 %d 个学期n",semester-1);
else
printf("有 %d 个课程剩余，先行课表中有闭环n",cnt);
}

　　在了解了拓扑排序的思想之后，要弄懂以上的函数实现过程并不难。唯一需要注意的是我在topologicalSort()的函数中添加了对先行课表中是否有闭环的判断，添加一个计数器cnt，每得到一个入度为零的节点，就cnt--，如果到最后cnt为零，则该课表是一个DAG，既可以得到拓扑序列，反之则图中有闭环，既不能得到拓扑序列。

　　下面给出main函数和测试数据

int main()
{
int n;
freopen("data.txt","r",stdin);
scanf("%d",&n);
course c(n);
c.getIndegree();
c.topologicalSort();
return 0;
}

//data.txt
8
1 2
3 4
2 5
3 6
1 5
7 8
8 1
1 3

最后

以上就是俊逸热狗为你收集整理的拓扑排序解决先行课问题的全部内容，希望文章能够帮你解决拓扑排序解决先行课问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。