This article describes the implementation method of the Java-based breadth-first traversal algorithm for graphs in the form of examples. The specific methods are as follows:
Use adjacency matrix to store graph method:
1. Determine the number of vertices and edges of the graph
2. The input vertex information is stored in the one-dimensional array vertex
3. Initialize the adjacency matrix;
4. Enter each edge in turn and store it in the adjacency matrix arc.
Enter the serial numbers i and j of the two vertices attached to the edge;
Set the element value of the i-th row and j-th column of the adjacency matrix to 1;
Set the element value of the j-th row and i-th column of the adjacency matrix to 1;
Breadth-first traversal implementation:
1. Initialize queue Q
2. Visit vertex v; visited[v]=1; vertex v is added to queue Q;
3.while (queue Q is not empty)
v=The head element of queue Q is dequeued;
w = first adjacent point of vertex v
while(w exists)
If w has not been visited, visit vertex w; visited[w]=1; vertex w is put into queue Q
w=next adjacent point of vertex v
The implementation code is as follows:
package com.teradata.lsw.sort;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class BFS {//Storage node information private Object[] vertices;//Storage edge information array private int[][] arcs;//Number of edges private int vexnum;// Record whether the i-th node has been visited private boolean[] visited;//Construct a temporary linked list to store the nodes that have been traversed private List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO Auto-generated method stubBFS g = new BFS(8);Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };g.addVertex(vertices);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("Breadth-first traversal of the graph:");g.bfs();}//Breadth-first traversal implementation private void bfs() {// TODO Auto-generated method stubfor (int i = 0; i < vexnum; i++) {visited[i] = false;}Queue<Integer> q = new LinkedList<Integer>();for (int i = 0; i < vexnum; i++) {if (!visited[i]) {visited[i] = true;visit(i );q.add(i);while (!q.isEmpty()) {int j = (Integer) q.remove().intValue();//Judge that if all traversals are completed, there is no need to loop if (temp.size() == vexnum) {q.removeAll(q);return;}for (int k = this .firstAdjVex(j); k >= 0; k = this.nextAdjVex(j, k)) {if (!visited[k]) {q.add(k);visited[k] = true;visit(k);}}}}}}// Find the next node public int firstAdjVex(int i) {for (int j = 0; j < vexnum ; j++) {if (arcs[i][j] > 0)return j;}return -1;}public int nextAdjVex(int i, int k) {for (int j = k + 1; j < vexnum; j++) {if (arcs[i][j] > 0)return j;}return -1;}//Initialize the edges of the graph private void addEdge(int i, int j) {// TODO Auto-generated method stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// Initialize the nodes of the graph private void addVertex(Object[] object) {// TODO Auto-generated method stubthis.vertices = object;}// Initialize the graph public BFS(int n) {// TODO Auto-generated constructor 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;}}}private void visit(int i) {// TODO Auto-generated method stubtemp .add(vertices[i]);System.out.print(vertices[i] + " ");}}