Summary Graph Algorithm

MST

=========================================

1. Kruskal  O(V log V)  

+ เรียง edge + วนทุกเส้นแล้วดูว่าทั้งสองจุดที่ปลาย edge อยู่เซ็ตเดียวกันรึยัง ถ้ายังก็ union set

2. Prim

-- ถ้าเก็บใส่ Adj Matrix O(V^2) -- ถ้าเก็บใส่ Adj List O(E log V) 1. หยิบซักจุด push (จุดนั้น, ระยะทาง=0) เข้า min-heap (เรียงตามระยะทาง) 2. pop จุด (ที่ไปถึงได้ในระยะใกล้สุด) ออกมาจาก heap 3. ดูว่าจุดที่จะไปนั้นเคยเชื่อมไปรึยัง ถ้าเชื่อมแล้วก็ไม่เอาไปทำข้อ 4 ต่อ แต่ถ้ายังก็เอาก็ mark ไว้ว่าจุดนี้เอาไปแล้ว 4. เอา edge รอบๆจุดนั้น push (จุดที่ปลายเส้น, ความยาว edge) ยัดใส่ min-heap (priority queue)

Shortest Path

=========================================

1. Dijkstra (เขียนเหมือน Prim แก้นิดเดียว คือ แทนที่จะ push เส้น ก็ไป push จุด,ระยะทาง  แทน)

** ใช้กับ Graph ที่มี negative cycle ไม่ได้ (ใช้ได้เฉพาะกับ Negative Acyclic Graph) -- ถ้าเก็บใส่ Adj Matrix O(V^2) -- ถ้าเก็บใส่ Adj List O(E log V) -- เขียนเหมือน prim เลย แต่แทนที่ ขั้นตอนที่ 4 จะ push (จุดที่ปลายเส้น, ความยาว edge) ก็เปลี่ยนเป็น push(จุดที่ปลายเส้น , ระยะทางที่เดินทางมาถึงจุดปัจจถุบัน +ความยาว edge ) แทน

2. Bellman-Ford 

** ใช้กับ Graph ที่มี negative cycle ได้ -- O(VE)

3. BFS

** ใช้กับ edge ที่ weight เท่ากันหมด ** ส่วนมากใช้กับพวกเดินในตารางที่นับก้าวเท่ากันหมด

All pair shortest path

=========================================

3. Floyd Warshall

-- O(V^3)