数据结构——图——拓扑排序
在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序(英语:Topological sorting)。
(1)每个顶点出现且只出现一次;
(2)若A在序列中排在B的前面,则在图中不存在从B到A的路径。
也可以定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从顶点A到顶点B的路径,那么在排序中B出现在A的后面。
有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。
思路:
拓扑排序的思想是:
(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);
}
}
}
}
关键路径问题: