1

我的算法是：

  1. 首先计算每个节点的入度，即计算该节点为其下沉的边数。
  2. 现在，将仅推送队列中具有 indegree==0 的那些，因为它们将首先出现在拓扑排序的图形列表中。
  3. 如果现在队列的起始大小为零。这意味着"Graph can't be sorted"。
  4. 否则我们开始排序方法。
  5. 如果我们在任何时候遇到超过 2 个顶点出现在队列中，这意味着“多个序列是可能的”
  6. 但在某些情况下，可能无法进行进一步的序列化。
  7. 所以我跟踪从队列中弹出（从前面删除）的节点。和他们的数目。
  8. 如果最后计数==节点数。并且未设置多个序列的标志，则序列是可能的“可以对图形进行排序”。
  9. 或者如果设置了 count== 节点数和多序列标志。我们说“多重序列是可能的”
  10. 如果计数！=节点数。然后“图形无法排序”

这是我的想法的实现

vector<vector<int> >list(10000); // Graph is represented as Adjacency list
void topological_sort()
{
    int i,l,item,j;
    k=0;    
    queue<int>q; // Queue
    vector<int>:: iterator it; 
    for(i=1;i<=n;i++) // Pushing nodes those who have indegree=0
    {       
        if(indegree[i]==0) 
            q.push(i);  
    }
    l=q.size();
    if(l==0)
    {
        flag=2; // means no sequence is possible
        return; 
    }
    while(q.empty()==0)
    {
        l=q.size();
        if(l>1)
            flag=1;     // multiple sequence possible for sure but check whether this is fully possible or not
        item=q.front();
        q.pop();
        ans[k++]=item;
        for(it=list[item].begin();it!=list[item].end();it++)
        {
            j=*it;
            indegree[j]--;
            if(indegree[j]==0)
                q.push(j);

        }
    }
    if(k!=n)
        flag=2; // no sequence is possible.
}

这个算法太慢了！或者只是一个幼稚的实现。对此有哪些进一步的改进。或者我如何使用 DFS 进行拓扑排序？

4

1 回答 1

3

定理：
有向图具有唯一的拓扑排序当且仅当它是有向链。

留给你练习的证明

要确定有向图是否具有唯一的拓扑排序，您所要做的就是：

  1. 查找度数为 0 的任何节点
    • 如果没有，则图有一个循环并且没有唯一的拓扑排序
  2. 重复跟随当前节点的第一个出边，边走边将访问过的节点添加到集合中
  3. 在以下情况下停止：
    • 你到达了一个你已经访问过的节点——图有一个循环，所以它没有唯一的拓扑排序
    • 你走到了死胡同 - 当且仅当访问的节点集包含图中的所有节点时，图才具有唯一的拓扑排序

您的代码似乎没有遵循这种简单的方法。（如果我错了，请纠正我！）所以，与其试图弄清楚你的代码是否正确，我建议简单地使用上面的算法大纲。

于 2013-06-13T16:25:52.213 回答