1 BFS拓扑排序
代码语言：javascript复制class Solution {
public:
vector<vector<int>> edges; // 邻接矩阵
vector<int> indegree; // 入度表
vector<int> res;
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
indegree.resize(numCourses, 0);
// 1.构造邻接矩阵 入度表
for (auto edge : prerequisites) {
edges[edge[1]].push_back(edge[0]);
indegree[edge[0]] ;
}
// 2.遍历入度表，将入度=0的节点放入队列中，即图的最先驱节点
queue<int> q;
for (int i = 0; i < indegree.size(); i )
if (indegree[i] == 0) q.push(i);
// 3.从图的最先驱节点一步一步删除，出队，存入res，并遍历每个出队先驱节点的所有子节点，将子节点入度-1，若子节点入度=0，则入队
while (!q.empty()) {
int v = q.front(); q.pop();
res.push_back(v);
for (auto& subv : edges[v]) {
indegree[subv]--;
if (indegree[subv] == 0)
q.push(subv);
}
}
// 4.若有环，则res通常比节点数小，比如三个节点成环，则res.size()==0 < 3
if (res.size() == numCourses) return res;
return {};
}
};
2 DFS拓扑排序
class Solution {
public:
vector<vector<int>> edges; // 邻接矩阵
vector<int> visited; // 0-未搜索; 1-已访问; 2-已压栈
vector<int> res; // 最终结果
stack<int> stk; // 存放结果的栈，图的子节点先入栈，父节点后入栈
bool vaild = true; // 是否有环，若有环则直接退出
void dfs(int v) {
visited[v] = 1; // 标记已访问，但不知道子节点是否已访问，故需先DFS访问所有子节点
for (auto& subv : edges[v]) { // DFS遍历所有子节点
if (visited[subv] == 1) { // 若某个子节点已访问，则存在环，直接退出遍历
vaild = false;
return;
} else if (visited[subv] == 0) { // 当且仅当子节点为<未搜索>状态时才进行DFS，若visited[subv] == 2则直接跳过即可
dfs(subv);
if (!vaild) return; // 遍历完某个子节点及其孙子节点后发现有环则直接退出遍历
}
}
visited[v] = 2; // 所有子节点均已访问并压栈，此时标记当前节点为已压栈
stk.push(v);
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
visited.resize(numCourses, 0);
// 1.构建邻接矩阵
for (auto& edge : prerequisites)
edges[edge[1]].push_back(edge[0]);
// 2.从图中任意选取1个未搜索节点进行DFS (为什么是任意选取？因为只要该节点进行DFS后则对应所有子节点均会压栈，此时其他未搜索节点一定是其先驱节点)
for (int i = 0; i < numCourses; i ) {
if (visited[i] == 0) dfs(i);
if (!vaild) return {};
}
// 3.将stack弹出变成程序需要的vector，若使用vector的reverse(vec.begin(), vec.end())也可节省空间
while (!stk.empty()) {
res.emplace_back(stk.top());
stk.pop();
}
return res;
}
};
