拓扑排序有向无环图

算法描述

• 拓扑排序就是对一个有向图进行排序&＃xff0c;得到一个有序序列。
• 找到有向图中入度为0的结点&＃xff0c;加入到队列中&＃xff0c;然后删除与该点所有关联的边&＃xff0c;重复此操作
• 拓扑排序可以判断改图是否有环

代码

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