数据结构——图——拓扑排序

Bertha 。 2022-04-12 05:07 373阅读 0赞

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。  
（1）每个顶点出现且只出现一次；  
（2）若A在序列中排在B的前面，则在图中不存在从B到A的路径。  
也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjIzNDI4_size_16_color_FFFFFF_t_70][]

**思路：**

拓扑排序的思想是：

（1）从有向图中选取一个没有前驱的顶点，并输出之；

（2）从有向图中删去此顶点以及所有以它为尾的弧；

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱 – 入度为零，删除顶点及以它为尾的弧– 弧头顶点的入度减1。

当前图中不存在无前驱的顶点说明有向图中必然存在环。

queue<int>q;
    //priority_queue<int,vector<int>,greater<int>>q;
    //优先队列的话，会按照数值大小有顺序的输出
    //此处为了理解，暂时就用简单队列
    inttopo()
    {
        for(inti=1;i<=n;i++)
        {
            if(indegree[i]==0)
            {
                q.push(i);
            }
        }
     
        int temp;
        while(!q.empty())
        {
            temp=q.front();//如果是优先队列，这里可以是top()
            printf("%d->",temp);
            q.pop();
            for(inti=1;i<=n;i++)//遍历从temp出发的每一条边，入度--
            {
                if(map[temp][i])
                {
                    indegree[i]--;
                    if(indegree[i]==0)q.push(i);
                }
            }
        }
    }

关键路径问题：

[拓扑排序应用][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjIzNDI4_size_16_color_FFFFFF_t_70]: /images/20220412/8d163d6bced44897839e3adaea1f6735.png
[Link 1]: https://blog.csdn.net/qq_42623428/article/details/84312346