题目：
基于宽度优先搜索的拓扑排序
思路：
这个问题相当查找有向图中是否存在环。逐个删除入度为0的节点，当删除的节点数量等于输入的所有节点数量时，判定不存在环。
拓扑排序最好使用邻接链表存储邻接关系，而非使用邻接矩阵。因为邻接链表在能够非常直接查找到邻接节点，查找操作耗时O(m+n)，而邻接矩阵需要进行遍历才能查找到邻接节点，查找操作耗时O(n^2)。其中n为节点数量，m为边的数量。
本算法的时间复杂度和空间复杂度都比较大，原因在于创建了邻接矩阵存储邻接关系。导致在查找邻接关系的时候，需要进行遍历操作，时间复杂度为O（n^2）。
执行用时 :60 ms, 在所有 cpp 提交中击败了32.55%的用户
内存消耗 :81.6 MB, 在所有 cpp 提交中击败了5.21%的用户
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(prerequisites.size() == )
return true;
vector< vector<int> > mat( numCourses, vector<int>(numCourses,) );
vector<int> numR(numCourses, );
vector<int> stack(numCourses, );
vector<int> tIn;
int top = , count = ;
for(int i = ; i < prerequisites.size(); ++i) {
tIn = prerequisites[i];
mat[tIn[]][tIn[]] = ;
numR[tIn[]] += ;
}
for(int j = ; j < numCourses; ++j) {
if(numR[j] == ) {
stack[top++] = j;
}
}
while(top > ) {
int gettop = stack[--top];
count += ;
for(int k = ; k < numCourses; ++k) {
if(mat[gettop][k] == ) {
numR[k] -= ;
if(numR[k] == )
stack[top++] = k;
}
}
}
if(count == numCourses )
return true;
else
return false;
}
};
对上述算法进行改进。将邻接矩阵换成邻接链表。时间复杂度为O（m+n），耗时大大缩小。
执行用时 :24 ms, 在所有 cpp 提交中击败了93.35%的用户
内存消耗 :12.9 MB, 在所有 cpp 提交中击败了19.07%的用户
注意，这里巧妙使用vector<vector<int>>数据类型创建了“邻接链表”。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(prerequisites.size() == )
return true;
vector< vector<int> > mat(numCourses);
vector<int> numR(numCourses, );
vector<int> stack(numCourses, );
vector<int> tIn;
int top = , count = ;
for(int i = ; i < prerequisites.size(); ++i) {
tIn = prerequisites[i];
mat[tIn[]].push_back(tIn[]);
numR[tIn[]] += ;
}
for(int j = ; j < numCourses; ++j) {
if(numR[j] == ) {
stack[top++] = j;
}
}
while(top > ) {
int gettop = stack[--top];
count += ;
for(int k = ; k < mat[gettop].size(); ++k) {
numR[mat[gettop][k]] -= ;
if(numR[mat[gettop][k]] == )
stack[top++] = mat[gettop][k];
}
}
if(count == numCourses )
return true;
else
return false;
}
};
基于深度优先搜索的拓扑排序
时间复杂度：排序过程为O(n+m)，其中n为节点数量，m为边数量。构建邻接链表为O(m)。
空间复杂度：邻接链表占据空间为O(m)；标识数组占据空间为O(n)；递归过程的栈内存最大为O(n)，此时拓扑序列为一条链。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(prerequisites.size() == )
return true;
vector< vector<int> > mat(numCourses);
vector<int> flag(numCourses, );
vector<int> tIn;
for(int i = ; i < prerequisites.size(); ++i) {
tIn = prerequisites[i];
mat[tIn[]].push_back(tIn[]);
}
bool ans = true;
for(int i = ; i < numCourses; ++i) {
ans = ans&&dfsF(i, flag, mat); // 每一条路线不允许存在回路，所以是“&&”逻辑
}
return ans;
}
bool dfsF(int i, vector<int>& flag, const vector<vector<int> >& matC){
if(flag[i] == )
return true;
if(flag[i] == -)
return false;
flag[i] = -;
for(int j = ; j < matC[i].size(); ++j) {
if(dfsF(matC[i][j], flag, matC))
continue;
else
return false;
}
flag[i] = ;
return true;
}
};