เกมงูและบันได (Snake and Ladder) มีห้องต่างๆ บนกระดาน บางห้องเชื่อมด้วยบันได (เลื่อนขึ้น) บางห้องเชื่อมด้วยงู (ลื่นลง) ต้องการหาจำนวนครั้งทอยลูกเต๋าน้อยที่สุดเพื่อไปจากจุดเริ่มต้นถึงจุดหมาย การรับค่าและแสดงผล Input: ตำแหน่งงูและบันได Snake: 26→0, 20→8, 16→3, 18→6 Ladder: 2→21, 4→7, 10→25, 19→28 Ou

อัลกอริทึมของทาร์จัน (Tarjans Algorithm) ใช้หา Strongly Connected Components (SCC) ของกราฟมีทิศทาง ใช้เพียงการ DFS ครั้งเดียว จาก DFS จะได้ DFS Tree/Forest จากนั้นหา SCC จากรากของแต่ละ subtree เมื่อพบรากของ subtree ที่เป็น SCC จะแสดงโหนดทั้งหมดใน subtree นั้นออกมา การรับค่าและแสดงผล Input: เมทริกซ

การเรียงลำดับแบบโตโปโลจิคัล (Topological Sorting) สำหรับกราฟมีทิศทางไม่มีวงจร (DAG) คือการเรียงลำดับโหนดแบบเส้นตรง โดยที่สำหรับเส้นเชื่อม U-V ทุกเส้น โหนด U จะอยู่ก่อนโหนด V ในลำดับ เนื่องจากโหนดต้นทางจะอยู่หลังโหนดปลายทาง จึงใช้ Stack เก็บโหนดที่ผ่านมาแล้ว และนำมาแสดงผลจากบนลงล่างของ Stack การรับ

อัลกอริทึมฟอร์ด-ฟูลเลอร์สัน (Ford-Fulkerson) ใช้หา Maximum Flow จากโหนดต้นทาง (Source) ไปยังโหนดปลายทาง (Sink) ในกราฟที่มีความจุ (Capacity) บนเส้นเชื่อม ข้อจำกัด: Flow บนเส้นเชื่อมไม่เกินความจุที่กำหนด Flow เข้าและ Flow ออกของโหนดกลางต้องเท่ากัน (ยกเว้น Source และ Sink) การรับค่าและแสดงผล Input:

การปิดเกี่ยวข้องข้าม (Transitive Closure) คือเมทริกซ์การเข้าถึง (Reachability Matrix) ที่บอกว่า จากโหนด u สามารถไปถึงโหนด v ได้หรือไม่ สำหรับทุกคู่โหนด (u, v) เมทริกซ์ผลลัพธ์เป็นแบบ Boolean: ค่า 1 หมายถึงมีเส้นทางอย่างน้อย 1 เส้นทางจาก u ไป v การรับค่าและแสดงผล Input: เมทริกซ์ตyacency 1 1 0 1 0 1

กราฟดาว (Star Graph) คือกราฟที่มีโหนดกลาง (Center) เชื่อมต่อกับโหนดอื่นๆ ทั้งหมดโดยตรง และโหนดอื่นๆ ไม่เชื่อมต่อกัน การตรวจสอบ: นับจำนวนโหนดที่มีองศา (Degree) เท่ากับ 1 และจำนวนโหนดที่มีองศาเท่ากับ n-1 (n = จำนวนโหนดทั้งหมด) หากมีโหนดองศา 1 จำนวน n-1 ตัว และโหนดองศา n-1 จำนวน 1 ตัว แสดงว่าเป็นกราฟด

อัลกอริทึมเบลล์แมน-ฟอร์ด (Bellman-Ford) ใช้หาระยะทางสั้นที่สุดจากโหนดต้นทางไปยังโหนดอื่นๆ ทุกโหนด ข้อแตกต่างจาก Dijkstra คือ รองรับน้ำหนักลบ (Negative Weight) ได้ อัลกอริทึมทำงานแบบ Bottom-Up: หาระยะทางที่มีเพียง 1 เส้นเชื่อมก่อน แล้วเพิ่มจำนวนเส้นเชื่อมทีละขั้นจนครบทุกกรณี การรับค่าและแสดงผล Inpu

กำหนดชุดกล่องที่มีขนาดต่างกัน (ความยาว ความกว้าง ความสูง) ต้องการหาการซ้อนกล่องที่ให้ความสูงรวมมากที่สุด สามารถหมุนกล่องได้ตามต้องการ แต่มีกติกาว่า พื้นที่ผิวด้านบนของกล่องล่างต้องกว้างกว่าพื้นที่ผิวด้านล่างของกล่องบน การรับค่าและแสดงผล Input: รายการกล่อง (ความยาว, ความกว้าง, ความสูง) { (4, 6, 7),

เพื่อตรวจจับวงจรในกราฟไม่มีทิศทาง ใช้ DFS traversal สำหรับโหนดที่เยี่ยมชมแล้ว v หากพบโหนดติดกัน u ที่เยี่ยมชมแล้ว และ u ไม่ใช่พ่อของ v แสดงว่าพบวงจร สมมติว่าไม่มีเส้นเชื่อมขนาน (Parallel Edges) ระหว่างคู่โหนดใดๆ การรับค่าและแสดงผล Input: เมทริกซ์ตyacency 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0

สามารถตรวจจับวงจร (Cycle) ในกราฟมีทิศทางได้โดยใช้ Depth First Search (DFS) หากมี self-loop ในโหนดใดถือเป็นวงจร หรือหากโหนดลูกมีเส้นเชื่อมกลับไปยังโหนดพ่อก็เป็นวงจรเช่นกัน สำหรับกราฟที่ไม่เชื่อมต่อ อาจมีต้นไม้หลายต้น (Forest) ต้องตรวจจับวงจรในทุกต้นไม้ วิธีนี้ใช้ 3 เซตสำหรับจัดสถานะโหนด: White Set

วงจรออยเลอร์ในกราฟมีทิศทาง (Directed Graph) คือเส้นทางที่ผ่านทุกเส้นเชื่อมเพียงครั้งเดียวและกลับมายังจุดเริ่มต้น เงื่อนไขในการเป็นกราฟออยเลอร์แบบมีทิศทาง: กราฟต้องเชื่อมต่อ (Strongly Connected) องศาเข้า (In-degree) และองศาออก (Out-degree) ของทุกโหนดต้องเท่ากัน การรับค่าและแสดงผล Input: เมทริกซ์ต

เส้นทางออยเลอร์ (Euler Path) คือเส้นทางที่ผ่านทุกเส้นเชื่อม (Edge) เพียงครั้งเดียว สามารถใช้โหนด (Vertices) ซ้ำได้ วงจรออยเลอร์ (Euler Circuit) เป็นกรณีพิเศษที่โหนดเริ่มต้นและโหนดสิ้นสุดเชื่อมต่อกัน เงื่อนไขในการตรวจสอบ: กราฟต้องเชื่อมต่อ (Connected) มีโหนดองศาคี่อยู่ที่ 2 โหนดพอดี → เป็น Euler Pa

อัลกอริทึมของฟลูรี (Fleurys Algorithm) ใช้สำหรับหาเส้นทางออยเลอร์ (Euler Path) หรือวงจรออยเลอร์ (Euler Circuit) จากกราฟที่กำหนด อัลกอริทึมเริ่มจากเส้นเชื่อมหนึ่งเส้น แล้วพยายามเคลื่อนที่ไปยังโหนดติดกันโดยการลบโหนดก่อนหน้า ทำให้กราฟง่ายขึ้นในแต่ละขั้นตอน กติกาสำคัญ: กราฟต้องเป็นกราฟออยเลอร์ เมื่อมี

ปัญหาการระบายสีกราฟ (Graph Coloring) เป็นกรณีพิเศษของการติดป้ายกำกับกราฟ (Graph Labeling) โดยแต่ละโหนดจะถูกระบายสี แต่มีข้อจำกัดคือ ไม่สามารถใช้สีเดียวกันสำหรับโหนดที่ติดกันได้ (Adjacent Vertices) การแก้ปัญหานี้ใช้ Greedy Algorithm แต่ไม่รับประกันว่าจะใช้สีน้อยที่สุด (Chromatic Number) การรับค่าแล

กำหนดกราฟมีทิศทางไม่มีวงจร (DAG) ที่มีน้ำหนักบนเส้นเชื่อม และโหนดต้นทาง ต้องการหาระยะทางยาวที่สุดจากโหนดต้นทางไปยังโหนดอื่นๆ ทั้งหมดในกราฟ วิธีแก้คือการเรียงลำดับโหนดแบบ Topological Sorting เก็บผลลัพธ์ไว้ใน Stack จากนั้นนำโหนดออกจาก Stack ทีละตัวเพื่อคำนวณระยะทางยาวที่สุดสำหรับแต่ละโหนด การรับค่าแ

กราฟเรียกว่า กราฟแบ่งสองส่วน (Bipartite Graph) เมื่อจุด (Vertices) สามารถแบ่งออกเป็นสองเซตอิสระได้ โดยที่ทุกเส้นเชื่อม (Edge) จะเชื่อมระหว่างเซตแรกและเซตที่สองเท่านั้น ไม่มีเส้นเชื่อมภายในเซตเดียวกัน การตรวจสอบสามารถทำได้โดยการระบายสีจุด (Vertex Coloring) จุดในเซตเดียวกันจะมีสีเดียวกัน เซตต่างกันจะ

กำหนดกราฟมีทิศทางไม่มีวงจร (DAG) ที่มีน้ำหนักบนเส้นเชื่อม และโหนดต้นทาง ต้องการหาระยะทางสั้นที่สุดจากโหนดต้นทางไปยังโหนดอื่นๆ ทั้งหมดในกราฟ สำหรับกราฟที่มีน้ำหนักลบ สามารถใช้ Bellman-Ford สำหรับน้ำหนักบวก ใช้ Dijkstra แต่สำหรับ DAG เราสามารถใช้เทคนิค Topological Sorting เพื่อลดความซับซ้อนได้ การรั

การจับคู่แบ่งสองส่วน (Bipartite Matching) คือการเลือกชุดของเส้นเชื่อม (Edges) ในกราฟ โดยที่ไม่มีเส้นเชื่อมสองเส้นใดๆ ที่แบ่งปันจุดปลาย (Endpoint) ร่วมกัน การจับคู่สูงสุด (Maximum Matching) คือการจับคู่ที่มีจำนวนเส้นเชื่อมมากที่สุด เมื่อพบการจับคู่สูงสุดแล้ว จะไม่สามารถเพิ่มเส้นเชื่อมได้อีก หากเพิ่ม

ในปัญหานี้ กำหนดชุดของ n จุดบนระนาบ 2 มิติ เราต้องหาคู่ของจุดที่มีระยะห่างระหว่างกันน้อยที่สุด วิธีแก้คือการแบ่งจุดออกเป็นสองครึ่ง คำนวณระยะห่างที่น้อยที่สุดในแต่ละครึ่งแบบเรียกซ้ำ (Recursive) จากนั้นพิจารณาจุดที่อยู่ใกล้เส้นแบ่งกลาง (Strip) เพื่อหาคู่ที่อาจมีระยะห่างน้อยกว่าที่พบในแต่ละครึ่ง อัลก

องค์ประกอบถือว่าเป็น จุดสูงสุด (Peak Element) เมื่อค่าของมันมากกว่าหรือเท่ากับค่าของเพื่อนบ้านทั้งสี่ทิศทาง ได้แก่ บน ล่าง ซ้าย และขวา (ไม่รวมทิศมุม) ในเมทริกซ์อาจมีจุดสูงสุดได้มากกว่าหนึ่งจุด และจุดสูงสุดไม่จำเป็นต้องเป็นค่าสูงสุดของเมทริกซ์ทั้งหมด การรับค่าและแสดงผล Input: เมทริกซ์ตัวเลข 10 8 1