เรารู้เรื่องเกม Snake and Ladder อันโด่งดัง ในเกมนี้ มีห้องบางห้องอยู่บนกระดานพร้อมหมายเลขห้อง บางห้องเชื่อมต่อกับบันไดหรืองู เมื่อได้บันไดมาเราสามารถปีนขึ้นไปยังห้องบางห้องเพื่อไปให้ใกล้ถึงที่หมายโดยไม่เคลื่อนไปตามลำดับ ในทำนองเดียวกันเมื่อเราได้งูบางตัว มันจะส่งเราไปยังห้องล่างเพื่อเริ่มต้นการเดิน

อัลกอริธึมของ Tarjan ใช้เพื่อค้นหาองค์ประกอบที่เชื่อมโยงอย่างมากของกราฟที่มีทิศทาง ต้องใช้การข้ามผ่าน DFS เพียงหนึ่งครั้งเพื่อใช้อัลกอริทึมนี้ การใช้ DFS traversal เราจะสามารถค้นหา DFS tree ของป่าได้ จากแผนผัง DFS จะพบส่วนประกอบที่เชื่อมต่ออย่างแน่นหนา เมื่อพบรูทของทรีย่อยดังกล่าว เราสามารถแสดงทร

การเรียงลำดับทอพอโลยีสำหรับกราฟอะไซคลิกโดยตรงคือการเรียงลำดับเชิงเส้นของจุดยอด สำหรับขอบ U-V ทุกเส้นของกราฟกำกับ จุดยอด u จะอยู่ก่อนจุดยอด v ในลำดับ ดังที่เราทราบดีว่าจุดยอดต้นทางจะมาหลังจุดยอดปลายทาง เราจึงจำเป็นต้องใช้สแต็กเพื่อเก็บองค์ประกอบก่อนหน้า หลังจากเสร็จสิ้นโหนดทั้งหมด เราก็สามารถแสดงโ

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

Transitive ปิดเมทริกซ์ความสามารถในการเข้าถึงเพื่อเข้าถึงจากจุดยอด u ถึงจุดยอด v ของกราฟ ให้กราฟหนึ่งอัน เราต้องหาจุดยอด v ซึ่งสามารถเข้าถึงได้จากจุดยอดอื่น u สำหรับคู่จุดยอดทั้งหมด (u, v) เมทริกซ์สุดท้ายคือประเภทบูลีน เมื่อมีค่า 1 สำหรับจุดยอด u ถึงจุดยอด v หมายความว่ามีเส้นทางอย่างน้อยหนึ่งเส

ให้กราฟ; เราต้องเช็คว่ากราฟที่กำหนดเป็นกราฟดาวหรือเปล่า โดยการสำรวจกราฟ เราต้องหาจำนวนจุดยอดที่มีดีกรีหนึ่ง และจำนวนจุดยอดที่มีดีกรีเป็น n-1 (ในที่นี้ n คือจำนวนจุดยอดในกราฟที่กำหนด) เมื่อจำนวนจุดยอดที่มีดีกรี 1 เป็น n-1 และจำนวนจุดยอดที่มีองศา (n-1) เป็นหนึ่ง จะเป็นกราฟดาว อินพุตและเอาต์พุต Inpu

อัลกอริธึม Bellman-Ford ใช้เพื่อค้นหาระยะทางต่ำสุดจากจุดยอดต้นทางไปยังจุดยอดอื่นๆ ความแตกต่างหลักระหว่างอัลกอริทึมนี้กับอัลกอริทึมของ Dijkstra คือ ในอัลกอริทึมของ Dijkstra เราไม่สามารถจัดการน้ำหนักเชิงลบได้ แต่ในที่นี้ เราสามารถจัดการได้อย่างง่ายดาย อัลกอริธึม Bellman-Ford ค้นหาระยะทางในลักษณะจา

ในปัญหานี้ จะมีการกำหนดชุดของกล่องต่างๆ ความยาว ความกว้าง และความกว้างอาจแตกต่างกันไปสำหรับกล่องต่างๆ งานของเราคือค้นหากองกล่องเหล่านี้ซึ่งมีความสูงมากที่สุด หมุนกล่องอะไรก็ได้ตามใจชอบ แต่มีกฎที่ต้องรักษาไว้ สามารถวางกล่องบนกล่องอื่นได้หากพื้นที่ของพื้นผิวด้านบนของกล่องด้านล่างมีขนาดใหญ่กว่าพื้นที่

ในการตรวจสอบว่ามีวัฏจักรใดในกราฟที่ไม่มีทิศทางหรือไม่ เราจะใช้การข้ามผ่าน DFS สำหรับกราฟที่กำหนด สำหรับจุดยอด v ที่เข้าชมทุกครั้ง เมื่อเราพบจุดยอดที่อยู่ติดกัน u ดังกล่าวมีการเยี่ยมชมแล้ว และ u ไม่ใช่พาเรนต์ของจุดยอด v จากนั้นตรวจพบหนึ่งรอบ เราจะถือว่าไม่มีขอบขนานกันสำหรับจุดยอดคู่ใดๆ Input and

การใช้อัลกอริธึมการข้ามผ่านแบบ Depth First Search (DFS) ทำให้เราตรวจจับวงจรในกราฟที่กำหนดได้ หากมี self-loop ในโหนดใด ๆ จะถือว่าเป็นวงจร มิฉะนั้นเมื่อโหนดย่อยมีขอบอื่นเพื่อเชื่อมต่อพาเรนต์ก็จะเป็นวงจรด้วย สำหรับกราฟที่ตัดการเชื่อมต่อ อาจมีต้นไม้ที่แตกต่างกัน เราสามารถเรียกพวกเขาว่าป่า ตอนนี้เราต้อง

เส้นทางออยเลอร์เป็นเส้นทางที่เราสามารถเยี่ยมชมทุกขอบได้ในครั้งเดียว เราสามารถใช้จุดยอดเดียวกันได้หลายครั้ง วงจรออยเลอร์เป็นเส้นทางออยเลอร์ชนิดพิเศษ เมื่อจุดยอดเริ่มต้นของเส้นทางออยเลอร์เชื่อมโยงกับจุดยอดสิ้นสุดของเส้นทางนั้นด้วย ก็จะเรียกว่าวงจรออยเลอร์ เพื่อตรวจสอบว่ากราฟเป็น Eulerian หรือไม่ เร

เส้นทางออยเลอร์เป็นเส้นทางที่เราสามารถเยี่ยมชมทุกขอบได้ในครั้งเดียว เราสามารถใช้จุดยอดเดียวกันได้หลายครั้ง วงจรออยเลอร์เป็นเส้นทางออยเลอร์ชนิดพิเศษ เมื่อจุดยอดเริ่มต้นของเส้นทางออยเลอร์เชื่อมโยงกับจุดยอดสิ้นสุดของเส้นทางนั้นด้วย ก็จะเรียกว่าวงจรออยเลอร์ ในการตรวจจับเส้นทางและวงจร เราต้องปฏิบัติตา

อัลกอริทึมของ Fleury ใช้เพื่อแสดงเส้นทางออยเลอร์หรือวงจรออยเลอร์จากกราฟที่กำหนด ในอัลกอริธึมนี้ โดยเริ่มจากขอบด้านหนึ่ง มันพยายามย้ายจุดยอดที่อยู่ติดกันอื่นๆ โดยเอาจุดยอดก่อนหน้าออก เมื่อใช้เคล็ดลับนี้ กราฟจะง่ายขึ้นในแต่ละขั้นตอนเพื่อค้นหาเส้นทางหรือวงจรออยเลอร์ เราต้องตรวจสอบกฎบางอย่างเพื่อให้ได้

ปัญหาสีกราฟเป็นกรณีพิเศษของการติดฉลากกราฟ ในปัญหานี้ แต่ละโหนดจะมีสีเป็นบางสี แต่การระบายสีก็มีข้อจำกัดบางประการ เราไม่สามารถใช้สีเดียวกันสำหรับจุดยอดที่อยู่ติดกันได้ ในการแก้ปัญหานี้ เราจำเป็นต้องใช้อัลกอริทึมโลภ แต่ไม่รับประกันว่าจะใช้สีขั้นต่ำ อินพุตและเอาต์พุต Input: Adjacency matrix of the g

ให้กราฟ acyclic กำกับแบบถ่วงน้ำหนักหนึ่งกราฟ มีจุดยอดแหล่งที่มาอื่นด้วย ตอนนี้เราต้องหาระยะทางที่ยาวที่สุดจากโหนดเริ่มต้นไปยังจุดยอดอื่นทั้งหมดในกราฟ เราจำเป็นต้องเรียงลำดับโหนดในเทคนิคการเรียงลำดับทอพอโลยี และผลลัพธ์หลังจากการเรียงลำดับทอพอโลยีถูกเก็บไว้ในสแต็ก หลังจากนั้นก็เด้งออกจากกองซ้ำแล้

กราฟเรียกว่ากราฟสองส่วน เมื่อจุดยอดของกราฟนั้นสามารถแบ่งออกเป็นชุดอิสระสองชุด โดยที่ทุกขอบในกราฟจะเริ่มจากชุดแรกและสิ้นสุดด้วย ชุดที่สองหรือเริ่มจากชุดที่สองเชื่อมต่อกับชุดแรกกล่าวคือไม่มีขอบในชุดเดียวกัน การตรวจสอบกราฟสองส่วนสามารถทำได้โดยใช้การระบายสีจุดยอด เมื่อจุดยอดอยู่ในชุดเดียวกันก็มีสีเหม

ให้กราฟ acyclic กำกับแบบถ่วงน้ำหนักหนึ่งกราฟ มีจุดยอดแหล่งที่มาอื่นด้วย ตอนนี้เราต้องหาระยะทางที่สั้นที่สุดจากโหนดเริ่มต้นไปยังจุดยอดอื่นทั้งหมดในกราฟ ในการตรวจจับระยะทางที่น้อยกว่า เราสามารถใช้อัลกอริธึมอื่น เช่น Bellman-Ford สำหรับกราฟที่มีน้ำหนักติดลบ สำหรับน้ำหนักที่เป็นบวก อัลกอริธึมของ Dijkst

การจับคู่แบบสองฝ่ายคือชุดของขอบในกราฟที่ถูกเลือกในลักษณะที่ว่าจะไม่มีสองขอบในชุดนั้นที่จะแชร์จุดสิ้นสุด การจับคู่สูงสุดตรงกับจำนวนขอบสูงสุด เมื่อพบการจับคู่สูงสุด เราไม่สามารถเพิ่มขอบอื่นได้ หากมีการเพิ่มขอบหนึ่งลงในกราฟที่ตรงกันสูงสุด ขอบนั้นจะไม่ตรงกันอีกต่อไป สำหรับกราฟสองส่วน อาจมีการจับคู่สู

ในปัญหานี้ ชุดของ n จุดจะได้รับบนระนาบ 2D ในปัญหานี้เราต้องหาคู่ของคะแนนที่มีระยะห่างน้อยที่สุด เพื่อแก้ปัญหานี้ เราต้องแบ่งจุดออกเป็นสองส่วน หลังจากนั้นระยะทางที่เล็กที่สุดระหว่างจุดสองจุดที่คำนวณแบบเรียกซ้ำ โดยใช้ระยะห่างจากเส้นกลาง จุดต่างๆ จะแยกออกเป็นแถบบางๆ เราจะหาระยะทางที่เล็กที่สุดจากอาร์เ

มีการกล่าวถึงรายการว่าเป็นองค์ประกอบสูงสุดเมื่อมีค่ามากกว่าหรือเท่ากับเพื่อนบ้านทั้งสี่ขององค์ประกอบนั้น องค์ประกอบข้างเคียงคือองค์ประกอบด้านบน ด้านล่าง ด้านซ้ายและด้านขวา สำหรับปัญหานี้เราจะพิจารณาถึงขอบเขตบางอย่าง องค์ประกอบในแนวทแยงจะไม่ถูกตรวจสอบเป็นองค์ประกอบข้างเคียง อาจมีองค์ประกอบพีคมากกว่าห