Graph Algorithm

Day 1

Search in Graph

• Depth-First Search
  • https://grader.mwit.ac.th/problem/vance
    hint

    dfs from all node
• Breadth-First Search
  • https://grader.mwit.ac.th/problem/toi17_wall
    hint

    dfs/bfs โจทย์ซับซ้อน
• Backtracking
  • เป็นการเก็บคำตอบย้อนหลัง หลังจากที่เข้าเงื่อนไขบางอย่างแล้ว
  • https://grader.mwit.ac.th/problem/walking_bot_2
• Branch and Bound (implementation)
  • https://grader.mwit.ac.th/problem/snakeword
• Challenge
  • https://grader.mwit.ac.th/problem/teleport
    hint

    ad-hoc, implementation

• Eulerian
• Hamiltonian

• Colorings
• Connectivity check
• Finding cycles visualgo
• Bipartiteness check

Day 2

visualgo

• Dijkstra’s Algorithm (implementation)
  • https://grader.mwit.ac.th/problem/turboprogramming
    hint

    dijkstra ตรงๆ
  • https://grader.mwit.ac.th/problem/town
    hint

    dijsktra ไม่ตรงมาก
  • https://grader.mwit.ac.th/problem/followpeatt
    hint

    dijkstra แบบมีเงื่อนไข
  • https://grader.mwit.ac.th/problem/toi14_logistics
    hint

    dijkstra ซับซ้อนขึ้น
• Bellman-Ford
  • Negative cycles
• Floyd-Warshall (implementation)
  • https://grader.mwit.ac.th/problem/toi17_1221
    hint

    all-pair
• Johnson (exist)
• A* Search

visualgo

• Kruskal’s (implementation)
  • Union-find
  • https://grader.mwit.ac.th/problem/mst
    hint

    ตรงสุดๆ
• Prim’s

Day 3

• Diameter
• Lowest common ancestor (implementation)
• Euler Tour Technique
• https://grader.mwit.ac.th/problem/toi12_weakpoint
  hint

  one-cycle, dp?

• https://grader.mwit.ac.th/problem/toi14_technology

• Kosaraju’s
• Challenge
  • https://grader.mwit.ac.th/problem/walk_around
    hint

    cycle, union find, reverse query

เพิ่มเติม

• Principles of Algorithmic Problem Solving
  • https://usaco.guide/PAPS.pdf#page=215
• Competitive Programmer’s Handbook
  • https://usaco.guide/CPH.pdf#page=119
• Algorithms for Competitive Programming
  • https://cp-algorithms.com/#graphs
• ตะลุยโจทย์ Graph ระดับโหดใน Competitive Programming (aquablitz11) ตะลุยโจทย์ Graph ระดับโหดใน Competitive Programming
• การบรรยายวิชา การออกแบบและวิเคราะห์อัลกอริทึม โดย สมชาย ประสิทธิ์จูตระกูล
  • อัลกอริทึม : 6.1 กราฟ - นิยามและการใช้งาน
  • อัลกอริทึม : 6.2 กราฟ - การแทนกราฟ
  • อัลกอริทึม : 6.3 กราฟ - การค้นตามแนวกว้าง
  • อัลกอริทึม : 6.4 กราฟ - การค้นตามแนวลึก
  • อัลกอริทึม : 6.5 กราฟ - การเรียงลำดับทอพอโลยี
  • อัลกอริทึม : 6.6 กราฟ - การเชื่อมต่อแบบเข้ม
  • อัลกอริทึม : 6.7 กราฟ - Prim : ต้นไม้แบบทอดข้ามต่ำสุด
  • อัลกอริทึม : 6.8 กราฟ - Kruskal : ต้นไม้แบบทอดข้ามต่ำสุด
  • อัลกอริทึม : 6.9 กราฟ - Dijkstra : วิถีสั้นสุดแหล่งต้นทางเดี่ยว
  • อัลกอริทึม : 6.10 กราฟ - Bellman-Ford : วิถีสั้นสุดแหล่งต้นทางเดี่ยว
  • อัลกอริทึม : 6.11 กราฟ - Floyd-Warshall : วิถีสั้นสุดของทุกคู่ปม
  • อัลกอริทึม : 6.12 กราฟ - Johnson : วิถีสั้นสุดของทุกคู่ปม