บทความนี้จะอธิบายวิธีการนำไปใช้ของอัลกอริธึมการแวะผ่านความกว้างแรกที่ใช้ Java สำหรับกราฟในรูปแบบของตัวอย่าง วิธีการเฉพาะมีดังนี้:
ใช้เมทริกซ์ adjacency เพื่อจัดเก็บวิธีกราฟ:
1. กำหนดจำนวนจุดยอดและขอบของกราฟ
2. ข้อมูลจุดยอดอินพุตจะถูกจัดเก็บไว้ในจุดยอดอาเรย์แบบหนึ่งมิติ
3. เริ่มต้นเมทริกซ์ adjacency;
4. ป้อนแต่ละขอบตามลำดับและเก็บไว้ในส่วนโค้งเมทริกซ์ adjacency
ป้อนหมายเลขซีเรียล i และ j ของจุดยอดทั้งสองที่ติดกับขอบ
ตั้งค่าองค์ประกอบของแถวที่ i และคอลัมน์ที่ j ของเมทริกซ์ adjacency เป็น 1
ตั้งค่าองค์ประกอบของแถวที่ j และคอลัมน์ที่ i ของเมทริกซ์ adjacency เป็น 1
การใช้งานการสำรวจเส้นทางแบบกว้างก่อน:
1. เริ่มต้นคิว Q
2. ไปที่จุดยอด v; visited[v]=1;
3.ขณะ (คิว Q ไม่ว่างเปล่า)
v=องค์ประกอบส่วนหัวของคิว Q ถูกแยกออกจากคิว;
w = จุดประชิดจุดแรกของจุดยอด v
ในขณะที่ (มีอยู่แล้ว)
หากยังไม่ได้เยี่ยมชม ให้ไปที่จุดสุดยอด w; เยี่ยมชมแล้ว[w]=1; จุดสุดยอด w จะถูกใส่เข้าไปในคิว Q
w=จุดที่อยู่ติดกันถัดไปของจุดยอด v
รหัสการใช้งานมีดังนี้:
แพ็คเกจ com.teradata.lsw.sort; นำเข้า java.util.ArrayList; นำเข้า java.util.LinkedList; นำเข้า java.util.List; นำเข้า java.util.Queue; คลาสสาธารณะ BFS {// ข้อมูลโหนดการจัดเก็บวัตถุส่วนตัว [] จุดยอด;//อาร์เรย์ข้อมูลขอบการจัดเก็บส่วนตัว int [] [] ส่วนโค้ง; // จำนวนขอบ int vexnum ส่วนตัว; // บันทึกว่าโหนด i-th ได้รับการเยี่ยมชมหรือไม่ บูลีนส่วนตัว[] เยี่ยมชม;//สร้างรายการเชื่อมโยงชั่วคราวเพื่อจัดเก็บโหนดที่ถูกสำรวจส่วนตัว List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO วิธีการสร้างอัตโนมัติ stubBFS g = new BFS(8);Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };g.addVertex(จุดยอด);g.addEdge(0, 1);g .addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(3, 5);g.addEdge(4, 5);g.addEdge(2, 6);g.addEdge(2, 7);System.out.println("การแวะผ่านกราฟในแนวกว้าง:");g.bfs();}//Breadth- การใช้งานการสำรวจครั้งแรก โมฆะส่วนตัว bfs () {// TODO วิธีการสร้างอัตโนมัติ stubfor (int i = 0; i < vexnum; i++) {เยี่ยมชม [i] = false;}คิว<จำนวนเต็ม> q = new LinkedList<Integer>();for (int i = 0; i < vexnum; i++) {if (!visited[i]) {visited[i] = true;visit(i );q.add(i);ในขณะที่ (!q.isEmpty()) {int j = (จำนวนเต็ม) q.remove().intValue();//ตัดสินว่าหากการสำรวจเส้นทางทั้งหมดเสร็จสมบูรณ์ ไม่จำเป็นต้องวนซ้ำ if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = นี่ .firstAdjVex(j); k >= 0; k = this.nextAdjVex(j, k)) {if (!visited[k]) {q.add(k);visited[k] = true;visit(k);}}}}}}// ค้นหาโหนดถัดไป public int firstAdjVex(int i) {for (int j = 0; j < vexnum ; j++) {if (arcs[i][j] > 0)return j;}return -1;}สาธารณะ int nextAdjVex(int i, int k) {สำหรับ (int j = k + 1; j < vexnum; j++) {if (arcs[i][j] > 0)return j;}return -1;}//เตรียมใช้งานขอบของกราฟส่วนตัว addEdge(int i, int j) {/ / TODO วิธีการสร้างอัตโนมัติ stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// เตรียมข้อมูลเบื้องต้นให้กับโหนดของกราฟ private void addVertex(Object[] object) {// TODO วิธีสร้างอัตโนมัติ stubthis.vertices = object;}// เตรียมข้อมูลเบื้องต้นกราฟ public BFS(int n) {// TODO สร้างอัตโนมัติ stubvexnum ตัวสร้าง = n ;vertices = new Object[n];arcs = new int[n][n];visited = new boolean[n];for (int i = 0; i < vexnum; i++) {for (int j = 0; j < vexnum; j++) {arcs [i] [j] = 0;}}} การเข้าชมส่วนตัวเป็นโมฆะ (int i) {// TODO วิธีการสร้างอัตโนมัติ stubtemp .add(จุดยอด[i]);System.out.print(จุดยอด[i] + " ");}}