// 更新入度 void updataIndegree( ) { for (auto node : vexs) for (auto x : node.medges) ++x.mit->mindegree; }
// 拓扑排序 void topsort() { int counter = 0; updataIndegree(); std::queue< Iterator > q; for (auto it = vexs.begin(); it != vexs.end(); ++it) if (it->mindegree == 0) q.push(it); // 入队 while (!q.empty()) { Iterator v = q.front(); q.pop(); // 出队 v->mtopNum = ++counter; for (auto& w : v->medges) if (--w.mit->mindegree == 0) q.push(w.mit); // 入队 } if (counter != vexs.size()) throw CycleFoundException{ }; }
原文:https://www.cnblogs.com/lsyy2020/p/12450138.html