https://wiki.ta.in.th/index.php?action=history&feed=atom&title=Summary_Graph_Algorithm 2026-05-02T16:42:57Z Revision history for this page on the wiki MediaWiki 1.33.0-alpha https://wiki.ta.in.th/index.php?title=Summary_Graph_Algorithm&diff=89&oldid=prev 2019-03-07T17:12:39Z

<p>Created page with &quot;MST ===================================================== 1. Kruskal O(V log V) + เรียง edge + วนทุกเส้นแล้วดูว่าทั้...&quot;</p> <p><b>New page</b></p><div>MST<br /> =====================================================<br /> 1. Kruskal O(V log V) <br /> + เรียง edge <br /> + วนทุกเส้นแล้วดูว่าทั้งสองจุดที่ปลาย edge อยู่เซ็ตเดียวกันรึยัง ถ้ายังก็ union set<br /> <br /> 2. Prim<br /> -- ถ้าเก็บใส่ Adj Matrix O(V^2)<br /> -- ถ้าเก็บใส่ Adj List O(E log V)<br /> 1. หยิบซักจุด push (จุดนั้น, ระยะทาง=0) เข้า min-heap (เรียงตามระยะทาง)<br /> 2. pop จุด (ที่ไปถึงได้ในระยะใกล้สุด) ออกมาจาก heap<br /> 3. ดูว่าจุดที่จะไปนั้นเคยเชื่อมไปรึยัง ถ้าเชื่อมแล้วก็ไม่เอาไปทำข้อ 4 ต่อ แต่ถ้ายังก็เอาก็ mark ไว้ว่าจุดนี้เอาไปแล้ว<br /> 4. เอา edge รอบๆจุดนั้น push (จุดที่ปลายเส้น, ความยาว edge) ยัดใส่ min-heap (priority queue)<br /> <br /> <br /> <br /> <br /> <br /> <br /> Shortest Path<br /> =====================================================<br /> 1. Dijkstra (เขียนเหมือน Prim แก้นิดเดียว คือ แทนที่จะ push เส้น ก็ไป push จุด,ระยะทาง แทน)<br /> ** ใช้กับ Graph ที่มี negative cycle ไม่ได้ (ใช้ได้เฉพาะกับ Negative Acyclic Graph)<br /> -- ถ้าเก็บใส่ Adj Matrix O(V^2)<br /> -- ถ้าเก็บใส่ Adj List O(E log V)<br /> -- เขียนเหมือน prim เลย แต่แทนที่ ขั้นตอนที่ 4 จะ push (จุดที่ปลายเส้น, ความยาว edge) ก็เปลี่ยนเป็น push(จุดที่ปลายเส้น , ระยะทางที่เดินทางมาถึงจุดปัจจถุบัน +ความยาว edge ) แทน<br /> 2. Bellman-Ford <br /> ** ใช้กับ Graph ที่มี negative cycle ได้<br /> -- O(VE)<br /> 3. BFS<br /> ** ใช้กับ edge ที่ weight เท่ากันหมด<br /> ** ส่วนมากใช้กับพวกเดินในตารางที่นับก้าวเท่ากันหมด<br /> <br /> All pair shortest path<br /> =====================================================<br /> 3. Floyd Warshall<br /> -- O(V^3)</div>

Tata