Graph — BFS / DFS / Dijkstra / Topo sort / Cycle

Bắt đầu từ:

Frontier (queue/stack):

[]

Thứ tự thăm:

BFS dùng queue: thăm gần trước xa sau. DFS dùng stack/đệ quy: đi sâu một nhánh trước khi quay lại.

Từ: Đến:

parent[]:

Path:

Lưu parent[v] khi enqueue. Sau BFS, truy ngược t → s qua parent để dựng path.

Source:

Priority queue (sắp xếp theo dist):

[]

node

Dùng min-heap. Mỗi bước: pop node có dist nhỏ nhất, relax mọi cạnh ra ngoài. O((V+E) log V).

Postorder DFS (rồi đảo ngược):

Topological order:

DAG. DFS, sau khi hoàn thành node u (mọi con đã xong) → append vào danh sách. Đảo ngược cuối cùng.

Đồ thị:

color[]:

Trắng=chưa thăm · Xám=đang trong stack đệ quy · Đen=đã xong. Trong DFS, gặp node XÁM → CÓ chu trình (đi ngược về tổ tiên).