tag: %u56FE%u8BBA.md

Tag: 图论

3 posts
拓扑排序 Topological Sort

DAG 里给所有节点排个序,使得每条边都从靠前的指向靠后的。两种实现各背一份:Kahn 算法(BFS 入度法)和 DFS 后序逆序。顺手就把环检测做了。

...
Dijkstra 最短路径算法

Dijkstra = BFS + 贪心。把 FIFO 队列换成优先队列,每次从未确定的节点里挑距离最小的那个去松弛邻居。前提:边权非负——因为已确定节点的距离一旦敲定就不再回头。

...
BFS 广度优先搜索

一句话:BFS = 把图当池塘,从起点丢颗石头,看波纹一圈圈扩出去。第一次碰到目标的那一圈,就是最短步数(边权为 1)。

...