ตัวอย่างในบทความนี้อธิบายถึงวิธีที่ Java ใช้ breadth-first traversal (BFS) เพื่อคำนวณเส้นทางที่สั้นที่สุด แบ่งปันกับทุกคนสำหรับการอ้างอิงของคุณ การวิเคราะห์เฉพาะมีดังนี้:
เราใช้สตริงเพื่อแสดงจุดยอดของกราฟเพื่อจำลองตำแหน่งของห้องเรียน จัตุรัส ห้องน้ำ โรงอาหาร ประตูทิศใต้ และประตูทิศเหนือในโรงเรียน จากนั้นคำนวณเส้นทางที่สั้นที่สุดระหว่างจุดสองจุดใดๆ
ดังที่แสดงด้านล่าง:
ตัวอย่างเช่น หากฉันต้องการเดินทางจากประตูทิศเหนือไปยังโรงอาหาร ผลลัพธ์ของโปรแกรมควรเป็น:
BFS: จาก [ประตูทิศเหนือ] ถึง [โรงอาหาร]:ประตูทิศเหนือSquareCanteen
ขั้นแรกให้กำหนดอัลกอริทึมอินเทอร์เฟซอัลกอริทึม:
อัลกอริธึมอินเทอร์เฟซสาธารณะ { /** * ดำเนินการอัลกอริธึม */ เป็นโมฆะดำเนินการ (กราฟ g, สตริง sourceVertex); /** * รับเส้นทาง */ แผนที่ <สตริง, สตริง> getPath();}จากนั้นให้กำหนดกราฟ:
/** * (ไม่ระบุทิศทาง) กราฟ*/กราฟคลาสสาธารณะ { // จุดเริ่มต้นของกราฟส่วนตัว String firstVertax; // Adjacency รายการแผนที่ส่วนตัว<String, List<String>> adj = new HashMap<>(); / Algorithm อัลกอริทึมส่วนตัว Traversal Algorithm; } /** * รับเส้นทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังจุด {@code vertex} * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack< >() ; stack.add(vertex) ; false == location.equals(firstVertax) ; location = path.get(location)) { stack.push(location); } stack.push(firstVertax); } /** * เพิ่มขอบ*/ โมฆะสาธารณะ addEdge(String fromVertex, String toVertex) { ถ้า (firstVertax == null) { firstVertax = fromVertex; } adj.get(fromVertex).add(toVertex); adj.get(toVertex).add(fromVertex); } /** * เพิ่มจุดสุดยอด*/ โมฆะสาธารณะ addVertex(String vertex) { adj.put(vertex, new ArrayList<>()); } แผนที่สาธารณะ<String, List<String>> getAdj() { return adj; }}ที่นี่เราใช้รูปแบบการออกแบบเชิงกลยุทธ์เพื่อแยกอัลกอริธึมออกจากคลาสกราฟ และเลือกอัลกอริธึมการสำรวจเส้นทางสำหรับกราฟโดยส่งผ่านการใช้งานอินเทอร์เฟซอัลกอริทึมเมื่อสร้างวัตถุกราฟ
กราฟสาธารณะ (อัลกอริธึมอัลกอริธึม) { this.algorithm = อัลกอริธึม;โครงสร้างการจัดเก็บข้อมูลของกราฟที่ไม่ได้กำหนดทิศทางเป็นรายการที่อยู่ติดกัน ในที่นี้ แผนที่ถูกใช้เพื่อแสดงรายการที่อยู่ติดกัน คีย์ของแผนที่คือที่ตั้งของโรงเรียน (สตริง) และค่าคือรายการสถานที่ (รายการ<สตริง>) เชื่อมต่อกับสถานที่
// Adjacency list แผนที่ส่วนตัว <String, List <String>> adj = new HashMap <>();
จากนั้น เขียนการใช้งาน BFS ของอินเทอร์เฟซอัลกอริทึม:
/** * สรุปอัลกอริธึม BFS*/คลาสสาธารณะ BroadFristSearchAlgorithm ใช้อัลกอริทึม { // บันทึกตำแหน่งที่เยี่ยมชม รายการส่วนตัว<String> visitVertex; // บันทึกเส้นทางที่สั้นที่สุด แผนที่ส่วนตัว<String, String> พาธ; g, สตริง sourceVertex) { if (null == visitVertex) { visitVertex = new ArrayList<>(); } if (null == path) { path = ใหม่ HashMap<>(); } BFS(g, sourceVertex); } @Override public Map<String, String> getPath() { return path; } ส่วนตัว void BFS(Graph g, String sourceVertex) { Queue<String> Queue = new LinkedList<>(); // ทำเครื่องหมายจุดเริ่มต้น visitVertex.add(sourceVertex); // จัดคิวจุดเริ่มต้น.add(sourceVertex); while (false == Queue.isEmpty()) { String ver = Queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); สำหรับ (สตริง v : toBeVisitedVertex) { ถ้า (false == visitVertex.contains( v)) { visitVertex.add(v); path.put(v, ver); คิว.เพิ่ม(v);ในหมู่พวกเขา เส้นทางเป็นประเภทแผนที่ ซึ่งหมายถึงเส้นทางจากค่าไปยังคีย์
คำอธิบายอัลกอริทึม BFS:
1. ทำเครื่องหมายต้นทางว่าเยี่ยมชมแล้ววางลงในคิว
2. นำจุดยอดออกจากคิวและนำจุดยอดทั้งหมดมาเชื่อมต่อกับจุดยอด
3. สำรวจจุดยอดเหล่านี้ อันดับแรกพิจารณาว่ามีการเยี่ยมชมจุดยอดหรือไม่ ถ้าไม่ ให้ทำเครื่องหมายจุดว่ามีการเยี่ยมชม บันทึกเส้นทางปัจจุบัน และเข้าคิวจุดยอดปัจจุบัน
4. ทำซ้ำขั้นตอนที่ 2 และ 3 จนกว่าคิวจะว่างเปล่า
กรณีทดสอบ:
String[] vertex = {"ประตูทิศเหนือ", "ประตูทิศใต้", "ห้องเรียน", "จัตุรัส", "ห้องน้ำ", "โรงอาหาร"}; ), ขอบใหม่ ("ประตูทิศเหนือ", "สี่เหลี่ยม"), ขอบใหม่ ("ห้องเรียน", "ห้องน้ำ"), ขอบใหม่ ("สี่เหลี่ยม", "ห้องน้ำ"), ขอบใหม่ ("สี่เหลี่ยม", "โรงอาหาร"), Edge ใหม่ ("Toilet", "South Gate"), Edge ใหม่ ("Toilet", "South Gate"), };@Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm( )); addVertex(g); addEdge(g); g.done(); Stack<String> result = g.findPathTo("โรงอาหาร"); System.out.println("BFS: จาก [ประตูทิศเหนือ] ถึง [โรงอาหาร]:"); ในขณะที่ (!result.isEmpty()) { System.out.println(result.pop() } }ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน