1. BFS拓扑排序介绍拓扑排序解决的问题一堆事情存在先后依赖问能否不重不漏排出合法顺序也可以判断依赖关系中是否存在环思路把事件看成点、依赖看成有向边如果能将所有元素排序那么这张有向图无环。用 BFS 实现只需要维护一个入度数组和一个队列流程建图edges[b].push_back(a)in[a]所有入度为 0 的点入队队列不空时循环取队头 t把 t 的所有邻接点入度 -1减到 0 就入队结束后若还有入度不为 0 的点说明有环2. 课程表207. 课程表解题思路原问题可以直接转成拓扑排序课程是顶点先修关系是有向边。建图对[a, b]表示学a之前要先学b所以可以建立b - a的关系不要忘了in[a]拓扑排序先把所有入度为 0 的课程入队然后 BFS 不断把邻居入度减 1判环排序结束后遍历in数组只要有一个不为 0说明成环返回false注意点边的方向容易写反。[a, b]是b指向a入度加在a上复杂度时O(N M)空O(N M)N为课程数M为先修关系数。classSolution{public:boolcanFinish(intnumCourses,vectorvectorintprerequisites){//1.邻接表:边入度unordered_mapint,vectorintedges;vectorintin(numCourses);//映射关系for(inti0;iprerequisites.size();i){intxprerequisites[i][0];intyprerequisites[i][1];edges[y].push_back(x);in[x];}//2.入度为0的进队列queueintq;for(inti0;inumCourses;i){if(in[i]0)q.push(i);}//3.拓扑排序while(q.size()0){inttq.front();q.pop();for(autoe:edges[t]){//更新入度--in[e];//入度为0的进队列if(in[e]0)q.push(e);}}//遍历返回结果for(inti0;inumCourses;i){if(in[i]!0)returnfalse;}returntrue;}};3. 课程表 II210. 课程表 II解题思路和上一题一模一样只多了一步记录顺序。出队时把课程塞进ret数组返回值判断ret.size() numCourses相等说明全部排完直接返回不等说明有环返回空数组这里的关键是有环时ret是残缺的不能直接返回ret必须先检查长度复杂度时O(N M)空O(N M)。classSolution{public:vectorintfindOrder(intnumCourses,vectorvectorintprerequisites){vectorintret;//1.创建邻接表入度unordered_mapint,vectorintedges;vectorintin(numCourses);for(inti0;iprerequisites.size();i){intxprerequisites[i][0];intyprerequisites[i][1];edges[y].push_back(x);in[x];}//2.入度为0的入队列queueintq;for(inti0;inumCourses;i){if(in[i]0){q.push(i);ret.push_back(i);}}//3.拓扑排序ret补全while(q.size()0){inttq.front();q.pop();for(autoe:edges[t]){--in[e];if(in[e]0){ret.push_back(e);q.push(e);}}}//4.检查并返回if(ret.size()!numCourses)return{};returnret;}};4. 火星词典LCR 114. 火星词典解题思路这道题的难点不在拓扑排序而在建图和处理复杂容器内的数据一不小心就会出错。题目给的是一串已按外星字典序排好的单词要从相邻单词里反推出字母的大小关系。收集信息两层for枚举所有单词对用双指针找第一个不同的字符后续舍弃比较无意义初始化所有出现过的小写字母都要在初始化时预存入入度表中in[ch] 0包括那些没有任何依赖关系的孤立字母建边第一个不同位置上前一个单词的字符一定小于后一个单词的字符连边a - bin[b]去重和前两题不同的是同一对字符关系可能被多组单词重复包含需要用edges[a].count(b)判重否则入度会虚高永远减不到 0拓扑排序队列里放字符出队时拼进ret返回值结束后还有入度不为 0 的字母说明约束成环返回注意点边界情况藏在一个很隐蔽的地方——如果比较时短单词是长单词的前缀且短单词更长i s2.size() i s1.size()这本身就违反字典序必须直接判错。比如[abc, ab]不可能有序因为前缀一定排前面血的教训TvT复杂度设单词总字符数为C比较次数为O(n²)每次最多扫L个字符时间O(n² · L C)空间O(C)。classSolution{unordered_mapchar,unordered_setcharedges;// 邻接表来存储图unordered_mapchar,intin;// 统计入度boolcheak;// 处理边界情况public:stringalienOrder(vectorstringwords){// 1. 建图 初始化入度哈希表for(autos:words){for(autoch:s){in[ch]0;}}intnwords.size();for(inti0;in;i){for(intji1;jn;j){add(words[i],words[j]);if(cheak)return;}}// 2. 拓扑排序queuecharq;for(auto[a,b]:in){if(b0)q.push(a);}string ret;while(q.size()){chartq.front();q.pop();rett;for(charch:edges[t]){if(--in[ch]0)q.push(ch);}}// 3. 判断for(auto[a,b]:in)if(b!0)return;returnret;}voidadd(strings1,strings2){intnmin(s1.size(),s2.size());inti0;for(;in;i){if(s1[i]!s2[i]){charas1[i],bs2[i];// a - bif(!edges.count(a)||!edges[a].count(b)){edges[a].insert(b);in[b];}break;}}if(is2.size()is1.size())cheaktrue;}};4. 易错点总结易错点表现修正边方向写反拓扑排序能跑通但顺序反了[a,b]是b - a入度加在a只看队列空就判无环有环时队列也会空误判为可行必须检查in是否全为 0或出队计数是否等于N课程表 II 直接返回ret有环时返回残缺序列答案错误先判ret.size() numCourses火星词典漏初始化字符孤立字母进不了队列结果少字符建图前把所有出现过的字符in[ch] 0重复边导致入度虚高入度永远减不到 0误判成有环用unordered_set存邻接点加边前判重忽略前缀非法[abc,ab]返回了错误顺序比较结束后检查短串是否为长串前缀认为拓扑序唯一和示例输出不一致就以为写错任意合法顺序都算对