ลำดับความสำคัญเชิงลึก
การสำรวจความสำคัญเชิงลึกนั้นคล้ายกับการเดินเขาวงกตโดยคน ๆ หนึ่ง:
ดังที่แสดงในรูปให้เลือกขอบจากจุดเริ่มต้นเพื่อเดินไปยังจุดสุดยอดถัดไป ก่อนที่จะถึงจุดสุดยอดจะมีการทำเครื่องหมายว่าจุดสุดยอดนี้มาถึงแล้ว
เมื่อจุดสุดยอดที่ทำเครื่องหมายอยู่ให้กลับไปที่จุดสุดยอดก่อนหน้าจากนั้นเลือกจุดสุดยอดที่ยังไม่ถึง
ดำเนินการต่อเพื่อล่าถอยไปเมื่อไม่มีทางเดินไปยังสี่แยกที่ได้รับการถอยกลับไป
สำหรับ ส่วนประกอบที่เชื่อมต่อ ให้ดูที่แนวคิด: กราฟย่อยที่เชื่อมต่ออย่างมากของกราฟที่ไม่ได้ทิศทางเรียกว่าส่วนประกอบที่เชื่อมต่อของ G. มีเพียงส่วนประกอบที่เชื่อมต่อเดียวของกราฟที่เชื่อมต่อใด ๆ นั่นคือมันเองและกราฟที่ไม่ได้เชื่อมต่อที่ไม่ได้เชื่อมต่อ
มาดูตัวอย่างเฉพาะ:
แพ็คเกจ com.datastructure.graph; // ค้นหาส่วนประกอบ unicom ของส่วนประกอบคลาสสาธารณะกราฟที่ไม่ได้รับอนุญาต {กราฟส่วนตัว; // อาร์เรย์เพื่อจัดเก็บบูลีนส่วนตัวอินพุต [] เข้าเยี่ยมชม; // เก็บสถานะส่วนประกอบส่วนตัว ส่วนประกอบ (กราฟกราฟ) {this.graph = graph; componentCount = 0; // จำนวนเริ่มต้นของส่วนประกอบที่เชื่อมต่อคือ 0 เข้าเยี่ยมชม = บูลีนใหม่ [graph.v ()]; mark = new int [graph.v (); สำหรับ (int i = 0; ส่วนประกอบที่เชื่อมต่อของโหนดถูกทำเครื่องหมายเป็น -1} สำหรับ (int i = 0; i <graph.v (); i ++) {// ลำดับความสำคัญของความลึกลัดแร่แปรของโหนดที่ไม่ได้รับการตรวจหาก (! เยี่ยมชม [i]) {dfs (i); componentCount ++; // dfs (int i) {เยี่ยมชม [i] = true; // โหนดฉันได้รับการเข้าถึงเครื่องหมาย [i] = componentCount; // โหนดฉันเป็นของจำนวนปัจจุบันของส่วนประกอบที่เชื่อมต่อ (เครื่องหมาย) สำหรับ (int node: graph.adjacentNode (i)) {// traverse dfsdfs (node);}} บูลีนสาธารณะ isconnected (int v, int w) {return mark [v] == mark [w]; // การตัดสินว่าทั้งสองโหนดเชื่อมต่อตามเครื่องหมายของส่วนประกอบที่เชื่อมต่อ/กลับมาเป็นจำนวนมาก ส่วนประกอบ {//// กราฟส่วนตัว g; // การอ้างอิงของกราฟ // บูลีนส่วนตัว [] เยี่ยมชม; // ไม่ว่าจะมีการเข้าถึงโหนดในระหว่างกระบวนการ DFS // private int ccount; // บันทึกจำนวนส่วนประกอบ unicom จีน // private int [] id; // เครื่องหมายคอมโพเนนต์ unicom ของจีนที่สอดคล้องกันสำหรับแต่ละโหนด ///// // การสำรวจลำดับความสำคัญของความลึกของกราฟ // โมฆะส่วนตัว DFS (int v) {/////เยี่ยมชม [v] = true; // สถานะการเข้าถึงของโหนด V ถูกตั้งค่าเป็นจริง // id [v] = ccount; // เครื่องหมาย unicom ของจีนที่สอดคล้องกันของโหนด V ถูกตั้งค่าเป็น ccount ///// // การสำรวจจุด adjacency ของโหนด v i // สำหรับ (int i: g.adjacentNode (v)) {// // // ถ้าจุด adjacency ฉันยังไม่ได้รับการเข้าถึง dfs (i); //} //} //// // constructor เพื่อค้นหาส่วนประกอบที่เชื่อมต่อของกราฟแบบไม่ชอบธรรม // ส่วนประกอบสาธารณะ (กราฟกราฟ) {///// // อัลกอริทึมการเริ่มต้น // g = graph; ///// // เยี่ยมชมสถานะการเข้าถึงของ node ส่วนประกอบที่เชื่อมต่อซึ่งโหนดอยู่ในกราฟที่เก็บอาร์เรย์กราฟ g // id = ใหม่ int [gv ()]; ///// // // // จำนวนส่วนประกอบที่เชื่อมต่อจะเริ่มต้นเป็น 0 // ccount = 0; //// // ตั้งค่าอาร์เรย์ที่เข้าชมทั้งหมดเป็นเท็จ ตั้งค่าอาร์เรย์ทั้งหมดเป็น -1 // สำหรับ (int i = 0; i <gv (); i ++) {// เยี่ยมชม [i] = false; // id [i] = -1; //} /// // // ค้นหาส่วนประกอบ unicom ของกราฟ // สำหรับ (int i = 0; i <gv (); // // ความลึกลำดับความสำคัญ traversal // dfs (i); // ccount ++; //} //} /// ส่งคืนจำนวนส่วนประกอบ unicom ของกราฟ // int count () {// return ccount; //} /////// // query isConnected (int v, int w) {// ยืนยัน v> = 0 && v <gv (); // ยืนยัน w> = 0 && w <gv (); // return id [v] == id [w]; //} //}จำนวนส่วนประกอบ PASS คือ 3
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับการใช้งานการเขียนโปรแกรม Java ของตัวอย่างรหัสการสำรวจความสำคัญและการเชื่อมต่อ ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ติดตาม Wulin.com แล้วคุณจะได้รับมากขึ้น