📄️ 14.1 資料結構介紹
作為指標三劍客之一,圖是樹的升級版。圖通常可以分為有向(directed)或無向(undirected)、有循環(cyclic)或無循環(acyclic)、所有節點相連(connected)或不相連(disconnected)。樹其實就是一種相連的無向無環圖,而另一種很常見的圖則是有向無環圖(Directed Acyclic Graph,DAG)。
📄️ 14.2 二分圖
二分圖演算法也稱為染色法,是一種廣度優先搜索。如果能用兩種顏色對圖中的節點進行著色,且保證相鄰的節點顏色不同,那麼這個圖就是二分圖。
📄️ 14.3 拓撲排序
拓撲排序(topological sort)是一種常見的算法,用於對有向無環圖(DAG)進行排序。給定 DAG 中的 $N$ 個節點,我們需要將它們排序成一個線性序列;如果節點 $i$ 指向節點 $j$,則排序結果中 $i$ 必須在 $j$ 之前。拓撲排序的結果並不唯一,只要滿足以上條件即可。
📄️ 14.4 練習
基礎難度