BFS-图的广度优先遍历

bfs类：

package com.bfs; import java.util.LinkedList; public class BFS { private char[] vertices; //存储顶点信息 private int[][] arcs; //存储边 private boolean[] visited; //顶点是否访问过 private int vexnum; //顶点个娄 /** * 实例对象时需要传入的顶点的个数 * @param n */ public BFS(int n) { vexnum = n; vertices = new char[n]; arcs = new int[n][n]; visited = new boolean[n]; } /** * 在顶点之间添加一条边 * @param i * @param j */ public void AddEdge(int i, int j) { if(i == j) return; arcs[i][j] = 1; arcs[j][i] = 1; } /** * 设置顶点的值 * @param vertices */ public void SetVertices(char[] vertices) { this.vertices = vertices; } /** * 访问第i个顶点元素 * @param i */ private void visit(int i) { System.out.print(" "+this.vertices[i]); } /** * 当前结点的第一个邻接结点在邻接矩阵中的索引 * @param i * @return */ private int FirstNeighbor(int i) { for(int k =i;k<vexnum;k++) { if(arcs[i][k] == 1) { return k; } } return -1; //表示没有相连接点 } /** * 获取i顶点除j外的下一个连接点 * @param i * @param j * @return */ public int NextNeighbor(int i,int j) { for( int k = j + 1; k<vexnum;k++) { if(arcs[i][k] == 1) { return k; } } return -1; } /** * 内部函数 * @param isVisited * @param i */ private void broadFirstSearch(boolean[] isVisited,int i) { int u,w; LinkedList queue=new LinkedList(); visit(i); isVisited[i]=true; queue.addLast(i); while (!queue.isEmpty()) { u=((Integer)queue.removeFirst()).intValue(); w=FirstNeighbor(u); while(w!=-1) { if(!isVisited[w]) { visit(w); isVisited[w]=true; queue.addLast(w); } w=NextNeighbor(u, w); } } } //对外公开函数，广度优先遍历 public void broadFirstSearch() { for(int i=0;i<vexnum;i++) { if(!visited[i]) { broadFirstSearch(visited, i); } } } }

测试类：

package com.bfs; import com.dfs.DFS; public class MainClass { public static void main(String[] args) { char[] vertices = {'A','B','C','D','E','F','G','H','I'}; BFS dfs = new BFS(8); dfs.SetVertices(vertices); dfs.AddEdge(0, 1); dfs.AddEdge(0, 5); dfs.AddEdge(1, 0); dfs.AddEdge(1, 2); dfs.AddEdge(1, 3); dfs.AddEdge(1, 4); dfs.AddEdge(2, 1); dfs.AddEdge(2, 6); dfs.AddEdge(3, 1); dfs.AddEdge(3, 7); dfs.AddEdge(4, 1); dfs.AddEdge(5, 0); System.out.println("广度遍历结果："); dfs.broadFirstSearch(); } }