理论准备
- 优先级的调度问题，做饭先烧水，切菜先买菜，炒菜先放油，活动之间有先后限制关系。
- 把必须先准备的事放到前面，需要大量铺垫的活动放到后面，得到一个序列就是拓扑排列。
- 拓扑排序不唯一
算法
- 依次拿掉入度（指向自己的箭头个数）为零的节点（起点），并把起点的邻接点的入度减一。
- 重复以上操作，直到不存在入度为零的点（起点）。
- 如果最后仍然剩余节点，说明图中必然有环。
准备：图的度数类API
-
Degrees（Digraph G）构造函数 -
int indegree（int v）v的入度 -
int outdegree（int v）v的出度 -
list<int> sources()所有起点的集合 -
list<int> sinks()所有终点的集合 -
bool isMap()G是一幅映射吗？
定义：入度为零的点是起点，出度为零的点为终点，一个图允许出现自环且每个顶点的出度为1的有向图叫做映射（从0到V-1之间的整数到他们自身的函数）
实现degrees
得到 Digraph.h 点这里
#pragma once
#include<queue>
#include"Digraph.h"
class Degrees
{
public:
Degrees(Digraph& G);
int indegree(int v) { return m_indegree->at(v); }
int outdegree(int v) {
return m_outdegree->at(v);
}
list<int>* sources();
list<int>* sinks();
bool isMap();
private:
vector<int>* m_indegree=nullptr;
vector<int>* m_outdegree=nullptr;
};
list<int>* TopSortByQueue(Digraph& G);
void testForTopSortByQ();
队列拓扑排序 Degrees.cpp 见注释
#include "Degrees.h"
Degrees::Degrees(Digraph& G)
{
int n = G.V();
m_indegree = new vector<int>(n, 0);
m_outdegree = new vector<int>(n, 0);
for (int i = 0; i < n; ++i) {
m_outdegree->at(i)=(G.adj(i)->size());
forIt(G.adj(i)) {
++m_indegree->at(*it);
}
}
}
list<int>* Degrees::sources()
{
list<int>* ans = new list<int>();
for (int i = 0; i < m_indegree->size();++i) {
if (m_indegree->at(i) == 0) {
ans->push_back(i);
}
}
return ans;
}
list<int>* Degrees::sinks()
{
list<int>* ans = new list<int>();
for (int i = 0; i < m_outdegree->size(); ++i) {
if (m_outdegree->at(i) == 0) {
ans->push_back(i);
}
}
return ans;
}
bool Degrees::isMap()
{
bool is_map = true;
for (int i = 0; i < m_outdegree->size(); ++i) {
if (m_outdegree->at(i) != 1) {
is_map = false;
break;
}
}
return is_map;
}
list<int>* TopSortByQueue(Digraph& G)
{
list<int>* topSortList = new list<int>();
vector<bool>* marked = new vector<bool>(G.V(), false);
vector<int>* indegrees = new vector<int>(G.V(), 0);
queue<int>* inQ = new queue<int>();
//取出入度放入数组indegrees
Degrees dg(G);
for (int i = 0; i < G.V(); ++i) {
indegrees->at(i) = dg.indegree(i);
}
//将起点（入度为零的点）入队
list<int>* sources = dg.sources();
forIt(sources) {
inQ->push(*it);
}
//队列不空
while (!inQ->empty())
{
//取出 标记 写到topSortList
int now = inQ->front(); inQ->pop();
marked->at(now) = true;
topSortList->push_back(now);
//修改邻接点的入度，把新起点入队
forIt(G.adj(now)) {
int nxt = *it;
if (!marked->at(nxt)) {
indegrees->at(nxt)--;
if (indegrees->at(nxt) == 0) {
inQ->push(nxt);
}
}
}
}
return topSortList;
}
void testForTopSortByQ()
{
Digraph G("tinyDAG.txt");
list<int>* topSlist = TopSortByQueue(G);
forIt(topSlist) {
out(*it);
}
hh;
}
/*
2 8 0 3 7 1 5 6 9 4 11 10 12
*/
测试图
依次取出起点，得到拓扑序列：