BFS, DFS và cái giá của ma trận kề: vì sao duyệt đồ thị thưa bằng ma trận chậm hơn 344 lần
BFS và DFS cùng duyệt mọi đỉnh trong O(V+E) — khác nhau ở thứ tự thăm, không ở tốc độ. Nhưng cách BIỂU DIỄN đồ thị thì khác nhau một trời một vực. Bài này đo thật trong go-lab: trên đồ thị thưa 20.000 đỉnh, ma trận kề tốn 391 MB và duyệt chậm hơn danh sách kề 344 lần, trong khi danh sách chỉ dùng 1,68 MB. Vì sao, và khi nào ma trận mới đáng dùng.