实现拓扑排序的核心代码

2016年8月1日 2点热度 0条评论 来源: SxTopc
注:一些主要的数组声明及树的建构在以下代码里均未声明


int que[maxn];
int ip = 0;

//先将图中没有前驱,,即入度为0的顶点加入队列

for(int i = 0; i<=n; i++)
{
    if(indegree[i] == 0)
    {
        que[ip++] = i;
    }
}
  //使用队列中的点更新indegree数组并生成拓扑排序序列
  
for(int i = 0; i<ip; i++)
{
    for(int k = head[que[i]]; k!=-1; k = edge[k].next)
    {
        indegree[edge[k].to]--;
        if(indegreee[edge[k].to] == 0)
            //如果indegree数组中的元素变为0,即又有新的顶点的入度变为0,,所以压入队列中
        {
            que[ip++] = edge[k].to;
        }
    }
}

  //输出拓扑排序的序列
for(int i = 0; i<ip; i++)
    cout<<que[i]<<' ';
cout<<endl;

    原文作者:SxTopc
    原文地址: https://blog.csdn.net/sxtopc/article/details/52086680
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。