C++拓樸排序Kahn演算與DFS解Leetcode難題1203 Sort Items by Groups Respecting Depende...

 

 C++拓樸排序Kahn演算與DFS解Leetcode難題1203 Sort Items by Groups Respecting Dependencies

Kahn算法是一種透過刪除邊緣並減少入度的廣度優先搜索方法。

孤立項目本身就是一個群組。

建立相鄰清單。

將入度為0的頂點 i 推入佇列 q 中。

使用迴圈，直到佇列 q 為空，並在迭代相鄰清單時將 --deg[y]=0 的頂點推入 q 中。

檢查是否還有一些頂點的deg大於0。

第二種方法在訪問頂點 i 時使用深度優先搜索，將 deg[i]=-1 標記

[codes on Leetcode]https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/solutions/3933825/c-using-bfs-kahn-s-algorithm-vs-dfs-beats-97-67/

[LeetCode程式]https://www.youtube.com/watch?v=7g-E3d_Oja4&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk&index=1

===========

Kahn's Algorithm is BFS method by removing the edges and decreasing the indegrees.

Isolated item is a group by itself

Build the adjacent lists

Push vertices i's with deg[i]=0 into the queue q

Using while loop until the q is empty and iterate the the adjacent lists push into q when --deg[y]=0

Check whether there is some vertex left with deg greater than 0

2nd Approach uses DFS when the vertex i is visited mark deg[i]=-1