© Song_about_summer/Shutterstock.com
เมื่อค้นหาผ่านกราฟหรือโครงสร้างข้อมูลแบบต้นไม้ อัลกอริทึมที่ได้รับความนิยม 2 อัลกอริทึม ได้แก่ การค้นหาระยะแรก (DFS) และการค้นหาอันดับแรก (BFS) ทั้งสองมีจุดประสงค์เดียวกันในการค้นหาเส้นทางหรือสำรวจกราฟ อย่างไรก็ตาม DFS กับ BFS แตกต่างกันในแง่ของแนวทางและประสิทธิภาพ
DFS เป็นแบบเรียกซ้ำ สำรวจลึกเข้าไปในกราฟและย้อนรอยเมื่อถึงทางตัน ในขณะที่ BFS ตรวจซ้ำไปยังโหนดที่อยู่ติดกันทั้งหมดก่อนที่จะดำเนินการต่อ บทความนี้จะเปรียบเทียบความแตกต่างของ DFS และ BFS โดยสรุปความแตกต่างที่สำคัญ ตลอดจนข้อดีและข้อเสียที่เกี่ยวข้องกับแต่ละวิธี
อัลกอริทึม DFS จะค้นหาในแต่ละสาขาให้ได้ไกลที่สุดก่อนที่จะย้อนรอย
©Wolfram Esser/CC BY-SA 3.0 – ใบอนุญาต
ความซับซ้อนของเวลาและพื้นที่
ข้อแตกต่างที่สำคัญอีกประการหนึ่งระหว่าง DFS และ BFS คือความซับซ้อนของเวลาและพื้นที่ ความซับซ้อนของเวลาของ DFS คือ O(V+E) โดยที่ V คือจำนวนจุดยอด และ E คือจำนวนขอบในกราฟหรือต้นไม้ นอกจากนี้ ความซับซ้อนของพื้นที่ยังเกิน O(V+E) เนื่องจากโหนดที่เข้าชมทั้งหมดจะต้องถูกจัดเก็บไว้ในสแต็กจนกว่าจะถึงลีฟที่เกี่ยวข้อง
ตรงกันข้าม BFS มีความซับซ้อนด้านเวลาเท่ากับ O(V+E) คล้ายกับ DFS; อย่างไรก็ตาม ความซับซ้อนของพื้นที่คือ O(V) เนื่องจากเก็บโหนดที่เยี่ยมชมทั้งหมดไว้ในอาร์เรย์ ดังนั้น BFS อาจต้องการหน่วยความจำมากกว่า DFS เมื่อจัดการกับกราฟหรือแผนผังขนาดใหญ่
กรณีการใช้งานและแอปพลิเคชัน
DFS และ BFS มีการใช้งานและแอปพลิเคชันที่แตกต่างกัน DFS มักจะใช้เมื่อพื้นที่การค้นหามีขนาดใหญ่และลึก โดยมีเป้าหมายเพื่อสำรวจเส้นทางที่กำหนดให้ไกลที่สุดเท่าที่จะเป็นไปได้ก่อนที่จะย้อนรอย นอกจากนี้ยังสามารถเป็นประโยชน์เมื่อพยายามค้นหาคำตอบในเกมหรือปริศนาที่คำตอบอาจอยู่ลึกเข้าไปในช่องว่างของปริศนา
ในทางกลับกัน BFS มักใช้เมื่อค้นหาขนาดใหญ่และ พื้นที่ค้นหาตื้นเพื่อระบุเส้นทางที่สั้นที่สุดระหว่างสองโหนดหรือจุดยอด นอกจากนี้ยังกำหนดระยะทางที่ใกล้ที่สุดระหว่างโหนดเครือข่ายสองโหนดหรือตำแหน่งบนแผนที่ทางภูมิศาสตร์
ความสมบูรณ์และความเหมาะสมที่สุด
อัลกอริทึมการค้นหาต้องเป็นไปตามข้อกำหนดสำคัญสองประการ ได้แก่ ความสมบูรณ์และความเหมาะสม ความสมบูรณ์หมายถึงว่าอัลกอริทึมสามารถรับประกันการพบวิธีแก้ปัญหาได้หรือไม่ ในขณะที่การเพิ่มประสิทธิภาพหมายถึงการค้นหาเส้นทางที่สั้นที่สุดหรือเหมาะสมที่สุดไปยังโซลูชันนั้น
DFS ไม่ได้สมบูรณ์แบบหรือเหมาะสมที่สุด เนื่องจากอาจติดขัดใน วนซ้ำไม่สิ้นสุดหรือล้มเหลวในการค้นหาเส้นทางที่สั้นที่สุด DFS อาจติดขัดหากวงจรในกราฟหรือแผนผังไม่สามารถติดตามโหนดที่เยี่ยมชมได้ นอกจากนี้ DFS อาจพบเส้นทางที่ไม่เหมาะสมในการแก้ปัญหา
อย่างไรก็ตาม BFS นั้นสมบูรณ์และเหมาะสมที่สุด รับประกันว่าจะหาทางออกได้หากมีอยู่ตลอดจนค้นหาเส้นทางที่สั้นที่สุดในนั้น หลังจากสำรวจโหนดทั้งหมดในระดับความลึกหนึ่งก่อนที่จะย้ายไปที่โหนดอื่น BFS จะตรวจสอบให้แน่ใจว่าพบเส้นทางที่สั้นที่สุด อย่างไรก็ตาม BFS อาจใช้เวลานานกว่า DFS ในบางกรณี โดยเฉพาะอย่างยิ่งเมื่อต้องจัดการกับกราฟหรือต้นไม้ที่ลึกหรือแคบ
การจัดการหน่วยความจำ
ปัจจัยสำคัญอีกประการหนึ่งในการเลือกระหว่าง DFS และ BFS ก็คือหน่วยความจำ การจัดการ. การจัดการหน่วยความจำหมายถึงวิธีที่อัลกอริทึมใช้หน่วยความจำและพื้นที่ที่จำเป็นสำหรับการจัดเก็บโหนดที่เข้าชม
DFS ใช้สแต็กเพื่อจัดเก็บโหนดที่เข้าชม แต่พื้นที่ค้นหาหรือกราฟขนาดใหญ่อาจทำให้เกิดปัญหาได้ ในกรณีดังกล่าว DFS อาจใช้หน่วยความจำไม่เพียงพอและไม่สามารถค้นหาโซลูชันที่เหมาะสมที่สุดได้ กราฟหรือต้นไม้ที่หนาแน่นต้องใช้หน่วยความจำมากขึ้นเนื่องจากวงจรที่เกิดขึ้นบ่อยครั้ง
BFS อาศัยโครงสร้างข้อมูลแบบคิวเพื่อจัดเก็บโหนดที่เยี่ยมชม ซึ่งรับประกันได้ว่าหน่วยความจำจะไม่หมด อย่างไรก็ตาม ในบางสถานการณ์ BFS อาจใช้หน่วยความจำมากกว่า DFS โดยเฉพาะอย่างยิ่งเมื่อกราฟหรือแผนผังมีความกว้างและตื้นหรือมีหลายสาขา นอกจากนี้ BFS อาจต้องการทรัพยากรมากขึ้นหากมีหลายโหนดหรือโครงสร้างกระจัดกระจาย
อัลกอริทึม BFS จะค้นหาโหนดทั้งหมดที่ระดับความลึกหนึ่งก่อนที่จะไปยังโหนดที่ระดับความลึกถัดไป
©Alexander Drichel/CC BY-SA 3.0 – ใบอนุญาต
ความซับซ้อนในการดำเนินการ
ความซับซ้อนในการดำเนินการของอัลกอริทึมหมายถึงความง่ายหรือยากในการดำเนินการ ขึ้นอยู่กับภาษาการเขียนโปรแกรมที่ใช้ โครงสร้างข้อมูลที่ใช้ได้ และตรรกะใดๆ ที่จำเป็นสำหรับการดำเนินการให้เสร็จสมบูรณ์
โดยปกติแล้ว DFS จะนำไปใช้ได้ง่ายกว่า BFS เนื่องจากต้องการเพียงโครงสร้างข้อมูลแบบสแต็กและฟังก์ชันเรียกซ้ำหรือการวนซ้ำ DFS สามารถนำไปใช้ได้โดยใช้อัลกอริทึมการค้นหาเชิงลึกก่อนอย่างง่าย ซึ่งจะเข้าไปที่แต่ละโหนดก่อนที่จะสำรวจแต่ละสาขาตามลำดับ นอกจากนี้ การติดตั้งใช้งานในภาษาการเขียนโปรแกรมแบบเรียกซ้ำได้ง่ายกว่า เช่น Python ซึ่งการเรียกซ้ำจะเกิดขึ้นอย่างเป็นธรรมชาติ
BFS บน ในทางกลับกัน ต้องใช้โครงสร้างข้อมูลคิวและลูป เพื่อนำไปใช้อย่างมีประสิทธิภาพ BFS ใช้อัลกอริธึมการค้นหาแบบกว้างก่อน ซึ่งเข้าถึงโหนดทั้งหมดที่ระดับความลึกหนึ่งก่อนที่จะดำเนินการต่อไปยังโหนดถัดไป อย่างไรก็ตาม การนำ BFS ไปใช้ในภาษาการเขียนโปรแกรมแบบเรียกซ้ำอย่างเช่น Python อาจเป็นเรื่องที่ท้าทายกว่าเนื่องจากต้องใช้การวนซ้ำจริงแทนที่จะเรียกซ้ำเพียงอย่างเดียว
แอปพลิเคชัน
DFS และ BFS มีแอปพลิเคชันที่แตกต่างกันในโดเมนต่างๆ โดยทั่วไปแล้ว DFS จะถูกนำไปใช้ในคอมพิวเตอร์กราฟิก ปัญญาประดิษฐ์ และการรวบรวมข้อมูลเว็บเพื่อเสนอโมเดล 3 มิติและรูปภาพโดยการสำรวจพื้นที่ 3 มิติเพื่อเรนเดอร์วัตถุ ปัญญาประดิษฐ์ใช้ DFS สำหรับแผนผังการตัดสินใจหรือแผนผังเกม – ประเมินแต่ละการเคลื่อนไหวที่เป็นไปได้เพื่อสำรวจกิ่งก้านของต้นไม้ – ในขณะที่โปรแกรมรวบรวมข้อมูลเว็บใช้ DFS เพื่อรวบรวมข้อมูลเว็บและสำรวจลิงก์บนเพจ
BFS ถูกใช้อย่างแพร่หลายในเครือข่าย การกำหนดเส้นทาง อัลกอริธึมเส้นทางที่สั้นที่สุด และปริศนา ในการกำหนดเส้นทางเครือข่าย จะค้นหาเส้นทางที่สั้นที่สุดระหว่างสองโหนดโดยสำรวจเส้นทางที่เป็นไปได้ทั้งหมดจนกว่าจะพบเส้นทางที่สั้นที่สุด BFS ยังมีบทบาทในอัลกอริธึมเส้นทางที่สั้นที่สุด เช่น Dijkstra หรือ A* ที่รับประกันว่าจะค้นหาเส้นทางที่สั้นที่สุด ในทำนองเดียวกัน เมื่อไขปริศนาต่างๆ เช่น Rubik’s Cube โดยใช้ BFS คุณจะได้ทราบวิธีแก้ปัญหาที่สั้นที่สุดที่จะไขปริศนาได้
การใช้ BFS เพื่อแก้ Rubik’s Cube จะเป็นตัวกำหนดวิธีแก้ปัญหาที่เร็วที่สุดในการไขปริศนา
©gd_project/Shutterstock.com
Search Space
Search Space คือชุดของสถานะหรือการกำหนดค่าที่เป็นไปได้ทั้งหมดที่อัลกอริทึมสามารถสำรวจเพื่อค้นหาวิธีแก้ปัญหา สามารถแสดงเป็นกราฟหรือต้นไม้ โดยที่แต่ละโหนดแสดงถึงสถานะหรือการกำหนดค่าเดียว และขอบแต่ละอันบ่งบอกถึงการเปลี่ยนผ่านระหว่างกัน
DFS ตรวจสอบลักษณะความลึกของพื้นที่ค้นหาก่อน สำรวจแต่ละสาขาเท่าที่ไกล ให้ได้มากที่สุดก่อนที่จะย้อนรอยและสำรวจสาขาอื่นๆ วิธีนี้ใช้ได้ผลดีที่สุดสำหรับพื้นที่ค้นหาขนาดใหญ่และลึก ซึ่งโซลูชันอาจอยู่ลึกลงไป น่าเสียดายที่ DFS อาจติดอยู่ในลูปไม่สิ้นสุดหากมีลูปไม่สิ้นสุดและไม่สามารถติดตามโหนดที่เยี่ยมชมได้
BFS สำรวจพื้นที่การค้นหาในลักษณะกว้างๆ ก่อน สำรวจโหนดทั้งหมดในที่เดียว ลึกก่อนที่จะดำเนินการต่อไป เหมาะอย่างยิ่งสำหรับพื้นที่ค้นหาขนาดใหญ่หรือตื้น ซึ่งโซลูชันอาจอยู่ใกล้กับราก BFS รับประกันว่าจะค้นหาเส้นทางที่สั้นที่สุดไปยังโซลูชันนั้น แต่อาจใช้หน่วยความจำมากกว่าและช้ากว่า DFS ในบางกรณี
กลยุทธ์การค้นหา
กลยุทธ์การค้นหาหมายถึงอัลกอริทึมที่ตัดสินใจเลือกโหนดใด เพื่อสำรวจต่อไป ปัจจัยต่างๆ เช่น ต้นทุน ฮิวริสติก หรือการสุ่มอาจเป็นตัวกำหนดกระบวนการตัดสินใจนี้
DFS ใช้กลยุทธ์การค้นหาเชิงลึกก่อน ซึ่งจะสำรวจแต่ละสาขาในขอบเขตสูงสุดที่เป็นไปได้ก่อนที่จะกลับมาและสำรวจสาขาอื่นๆ DFS ไม่ใช้ต้นทุนหรือการวิเคราะห์พฤติกรรมเมื่อเลือกโหนดที่จะสำรวจต่อไป ดังนั้นจึงอาจสำรวจเส้นทางที่ไม่เหมาะสม ในบางกรณี DFS อาจใช้การสุ่ม เช่น การค้นหาต้นไม้มอนติคาร์โล
โดยปกติแล้ว BFS จะใช้กลยุทธ์การค้นหาแบบกว้างๆ ก่อน สำรวจโหนดทั้งหมดที่ระดับความลึกหนึ่งก่อนที่จะดำเนินการต่อไป ในทางกลับกัน จะใช้กลยุทธ์การค้นหาต้นทุนแบบเดียวกันซึ่งจัดลำดับความสำคัญของโหนดด้วยต้นทุนที่ต่ำที่สุด ในบางกรณี BFS อาจใช้ฮิวริสติก เช่น อัลกอริทึม A* ซึ่งใช้ต้นทุนและระยะทางโดยประมาณในการตัดสินใจว่าจะสำรวจโหนดใดต่อไป
DFS เทียบกับ BFS: 10 ข้อเท็จจริงที่ต้องรู้
DFS ย่อมาจาก Depth First Search ในขณะที่ BFS ย่อมาจาก Breadth First Search DFS เคลื่อนที่ไปตามกราฟหรือต้นไม้ด้วยการเคลื่อนไหวเชิงลึก ในขณะที่ BFS เคลื่อนที่ตามความกว้างของต้นไม้ เพื่อติดตามโหนดที่เยี่ยมชมในระหว่างการเคลื่อนที่ DFS พวกเขาใช้สแต็ก ในขณะที่ใช้ BFS จะใช้คิว สามารถใช้ DFS สำหรับการเรียงลำดับทอพอโลยี การตรวจจับวงจร และการค้นหาส่วนประกอบที่เชื่อมต่ออย่างแน่นหนาในกราฟ ในขณะที่ BFS มีเป้าหมายที่จะค้นหาเส้นทางที่สั้นที่สุดระหว่างสองโหนด DFS ใช้พื้นที่น้อยกว่า ในขณะที่ BFS ต้องการมากกว่าเนื่องจากจัดเก็บโหนดทั้งหมดในระดับปัจจุบันก่อนที่จะดำเนินการต่อไป DFS เร็วกว่าเมื่อแก้ปัญหาที่เกี่ยวข้องกับโหนดจำนวนมาก ในขณะที่ BFS เก่งกว่าเมื่อจัดการกับกลุ่มที่เล็กกว่า DFS สำรวจโหนดทั้งหมดในกราฟหรือต้นไม้ ในขณะที่ BFS ไปที่เส้นทางที่สั้นที่สุดเท่านั้น DFS ใช้กลยุทธ์การค้นหาเชิงลึกก่อน ในขณะที่ BFS ใช้วิธีกว้างๆ มาก่อน DFS อาจไม่ ค้นหาเส้นทางที่สั้นที่สุด ในขณะที่ BFS มักจะทำ นอกจากนี้ DFS อาจติดอยู่ในลูปไม่สิ้นสุดหากกราฟของคุณมีวงจร อย่างไรก็ตาม BFS จะสิ้นสุดลงเมื่อเหลือโหนดจำกัดเท่านั้น
DFS กับ BFS: อันไหนดีกว่ากัน?
อัลกอริทึมการค้นหาเชิงลึก (DFS) และการค้นหาแนวกว้างก่อน (BFS) ต่างก็มีข้อดีและข้อเสียเฉพาะของตัวเอง บางสถานการณ์มากกว่าสถานการณ์อื่น
DFS สำรวจกราฟที่ลึกหรือไม่มีที่สิ้นสุดได้อย่างมีประสิทธิภาพด้วยความซับซ้อนของพื้นที่ต่ำและการใช้งานตามการเรียกซ้ำ นอกจากนี้ยังตรวจจับวัฏจักรในกราฟได้อย่างมีประสิทธิภาพ เนื่องจากสำรวจไกลออกไปตามแต่ละสาขาก่อนที่จะย้อนรอย DFS นำเสนอวิธีแก้ไขปัญหาต่างๆ เช่น การค้นหาส่วนประกอบที่เชื่อมต่อ การเรียงลำดับโทโพโลยี และปริศนา 8 ข้อ; สามารถปรับเปลี่ยนได้
ในทางกลับกัน BFS เหมาะสำหรับการค้นหาเส้นทางที่สั้นที่สุดระหว่างสองโหนดในกราฟ เนื่องจากจะตรวจสอบโหนดทั้งหมดที่ระดับความลึกนั้นก่อนที่จะไปยังระดับถัดไป นอกจากนี้ยังสามารถใช้เพื่อคำนวณต้นไม้ที่มีช่วงต่ำสุดของกราฟและแก้ปัญหาต่างๆ เช่น Knight’s Tour
อัลกอริทึมทั้งสองมีความซับซ้อนด้านเวลาของตัวเอง และตัวเลือกระหว่างทั้งสองจะขึ้นอยู่กับปัญหาเฉพาะและ ลักษณะของกราฟที่กำลังวิเคราะห์ โดยทั่วไป BFS มีความซับซ้อนของเวลาสูงกว่า DFS แต่รับประกันเส้นทางที่สั้นที่สุดระหว่างสองโหนดในกราฟที่ไม่มีการถ่วงน้ำหนัก ในทางกลับกัน DFS อาจมีความซับซ้อนน้อยกว่า แต่อาจไม่รับประกันเส้นทางที่สั้นที่สุดนี้เสมอไป
โดยสรุป ทางเลือกระหว่าง DFS กับ BFS ขึ้นอยู่กับปัญหาที่กำลังแก้ไขและกราฟที่กำลังวิเคราะห์ อัลกอริทึมทั้งสองมีจุดแข็งและจุดอ่อน ดังนั้นการทำความเข้าใจทั้งสองอย่างสามารถช่วยเลือกสิ่งที่เหมาะสมที่สุดสำหรับปัญหาเฉพาะได้ ดังนั้นจึงจำเป็นอย่างยิ่งที่จะต้องมีอัลกอริทึมทั้งสองประเภทในกล่องเครื่องมือของคุณ พร้อมด้วยตัวอย่างที่เป็นประโยชน์สูงสุด
DFS กับ BFS: การเปรียบเทียบแบบเต็มและคำถามที่พบบ่อยเกี่ยวกับความแตกต่างหลัก 9 ข้อ (คำถามที่พบบ่อย)
อัลกอริทึมใดดีกว่าสำหรับการค้นหาเส้นทางระหว่างสองโหนด
สามารถใช้ BFS และ DFS เพื่อค้นหาเส้นทางระหว่างสองโหนดได้ BFS ดีกว่าในการหาเส้นทางที่สั้นที่สุด ในขณะที่ DFS ชอบค้นหาเส้นทางที่อาจไม่สั้นที่สุด แต่อาจมีลักษณะที่ต้องการอื่นๆ เช่น การจัดเรียงทอพอโลยีหรือส่วนประกอบที่เชื่อมต่อกันอย่างมาก
อัลกอริทึมใดคือ ดีกว่าสำหรับการลากผ่านกราฟกระจายหรือไม่
BFS ดีกว่าสำหรับการลากผ่านกราฟกระจาย เนื่องจากมันสำรวจโหนดทั้งหมดในระดับหนึ่งก่อนที่จะดำเนินการต่อ ทำให้มีประสิทธิภาพเมื่อมีขอบน้อย ในทางตรงกันข้าม DFS อาจสำรวจโหนดที่ไม่เกี่ยวข้องจำนวนมาก ทำให้มีประสิทธิภาพน้อยลงเมื่อทำงานในกราฟที่กระจัดกระจาย
อัลกอริทึมใดดีกว่าสำหรับการสำรวจกราฟที่หนาแน่น
DFS มีประสิทธิภาพมากขึ้นเมื่อสำรวจกราฟที่มีความหนาแน่น เนื่องจากจะสำรวจโหนดเชิงลึกและสามารถย้อนรอยไปยังโหนดที่ยังเกี่ยวข้องกับการค้นหาได้อย่างรวดเร็ว อย่างไรก็ตาม BFS อาจตรวจสอบโหนดที่ไม่เกี่ยวข้องจำนวนมากพร้อมกันก่อนที่จะไปถึงโหนดที่คุณต้องการ ทำให้มีประสิทธิภาพน้อยลงในเครือข่ายที่มีความหนาแน่นสูง
สามารถใช้ DFS และ BFS ในการค้นหาส่วนประกอบที่เชื่อมต่อของกราฟได้หรือไม่
ใช่ สามารถใช้ทั้ง DFS และ BFS เพื่อค้นหาส่วนประกอบที่เชื่อมต่อกันของกราฟ DFS เริ่มต้นจากโหนดหนึ่งและสำรวจให้ไกลที่สุดก่อนที่จะย้อนกลับและสำรวจโหนดอื่นๆ ที่ไม่ได้เยี่ยมชม ในขณะที่ BFS ตรวจสอบโหนดทั้งหมดในระดับหนึ่งก่อนที่จะดำเนินการต่อไปยังโหนดถัดไป
สามารถใช้ DFS และ BFS เพื่อ ตรวจหารอบในกราฟหรือไม่
ใช่ ทั้ง DFS และ BFS สามารถใช้ตรวจหารอบในกราฟได้ DFS ตรวจจับรอบโดยการติดตามโหนดที่เยี่ยมชมในรายการและสแต็กของโหนดที่กำลังสำรวจ หากโหนดเดิมนั้นปรากฏขึ้นอีกครั้งโดยไม่ได้อยู่ในลำดับใดลำดับหนึ่ง ก็จะถือว่าเป็นรอบใหม่ ในทำนองเดียวกัน BFS จะรักษาทั้งรายการของโหนดที่เยี่ยมชมและคิวที่ใช้งานของโหนดที่กำลังสำรวจ หากโหนดที่เยี่ยมชมก่อนหน้านี้ปรากฏขึ้นอีกครั้งโดยไม่ได้เป็นลูกของตัวเองภายในคิวหลังนี้ โหนดนั้นจะถูกตั้งค่าสถานะว่าอาจสร้างความเสียหายได้
สามารถใช้ DFS และ BFS เพื่อค้นหาการจัดเรียงทอพอโลยีของกราฟแบบ acyclic ที่กำกับ ( DAG) หรือไม่
ใช่ สามารถใช้ทั้ง DFS และ BFS เพื่อกำหนดประเภทโทโพโลยีของ DAG ด้วย DFS สิ่งนี้ทำได้โดยการรักษาดัชนีของโหนดที่เยี่ยมชมรวมถึงสแต็กที่กำลังสำรวจอย่างต่อเนื่อง เมื่อสำรวจลูกทั้งหมดของแต่ละโหนดแล้ว พวกเขาจะถูกเพิ่มในการเรียงลำดับทอพอโลยี ในทำนองเดียวกัน ใน BFS ยังมีดัชนีที่ติดตามโหนดที่เยี่ยมชมพร้อมกับคิวที่กำลังรอการสำรวจ เมื่อมีการสำรวจพาเรนต์ทั้งหมดของโหนด โหนดนั้นจะรวมอยู่ในการจัดเรียงโทโพโลยีด้วย
สามารถใช้ DFS และ BFS เพื่อค้นหาเส้นทางที่สั้นที่สุดในกราฟถ่วงน้ำหนักได้หรือไม่
BFS สามารถใช้เพื่อค้นหาเส้นทางที่สั้นที่สุดในกราฟที่ไม่มีการถ่วงน้ำหนัก ในขณะที่อัลกอริทึมของ Dijkstra ใช้สำหรับกราฟที่มีการถ่วงน้ำหนัก อย่างไรก็ตาม DFS อาจประสบความสำเร็จเช่นกันเมื่อน้ำหนักไม่เป็นค่าลบ และการค้นหาจำกัดไว้ที่องค์ประกอบที่เชื่อมต่อหนึ่งรายการเท่านั้น