广度优先搜索基本思想
图的广度优先搜索类似于一个分层搜索的过程，需要使用一个队列以保持访问过的节点的顺序，以便按这个顺序来访问这些节点的邻接节点
广度优先搜索算法步骤
1.访问初始节点 v 并标记为以访问
2.节点 v 入队列
3.当队列为非空时，继续执行，否则 v 的算法结束
4.出队列，取得队列头节点 u
5.查找节点 u 的第一个邻接节点 w
6.如果节点 u 的邻接节点 w 不存在，则转到步骤 3；否则循环执行以下三个步骤
①若节点 w 尚未被访问，则访问节点 w 并标记为已访问
②节点 w 入队列
③查找节点 u 的继 w 邻接节点后的下一个邻接节点 w，转到步骤 6
public class Graph {private ArrayList<String> vertexList; //存储顶点的集合private int[][] edges; //存储图对应的邻接矩阵private int numOfEdges; //表示边的数目//定义一个数组 boolean[]，记录某个节点是否被访问private boolean[] isVisited;public static void main(String[] args) {//测试int n = 5; //节点的个数String[] Vertexs = {"A", "B", "C", "D", "E"};//创建图对象Graph graph = new Graph(n);//循环的添加顶点for (String vertex : Vertexs) {graph.insertVertex(vertex);}//添加边// A-B A-C B-C B-D B-Egraph.insertEdge(0, 1, 1);graph.insertEdge(0, 2, 1);graph.insertEdge(1, 2, 1);graph.insertEdge(1, 3, 1);graph.insertEdge(1, 4, 1);graph.showGraph();//测试 dfsSystem.out.println("深度遍历");graph.dfs();System.out.println("\n");//测试 bfsSystem.out.println("广度优先");graph.bfs();}//构造器public Graph(int n) {//初始化矩阵和 vertexListedges = new int[n][n];vertexList = new ArrayList<String>(n);numOfEdges = 0;}//得到第一个邻接节点的下标 w/**** @param index* @return 如果存在，返回对应下标，否则返回 -1*/public int getFirstNeighbor(int index) {for (int j = 0;j < vertexList.size(); j++) {if (edges[index][j] > 0) {return j;}}return -1;}//根据前一个邻接节点的下标来获取下一个邻接节点public int getNextNeighbor(int v1, int v2) {for (int j = v2 + 1; j < vertexList.size(); j++) {if (edges[v1][j] > 0) {return j;}}return -1;}//深度优先搜索算法private void dfs(boolean[] isVisited, int i) {//首先我们访问该节点，输出System.out.print(getValueByIndex(i) + " -> ");//将节点设置为已经访问isVisited[i] = true;//查找节点 i 的第一个邻接节点 wint w = getFirstNeighbor(i);while (w != -1) { //说明存在if (!isVisited[w]) {dfs(isVisited, w);}//如果 w 节点已经被访问过w = getNextNeighbor(i, w);}}//对 dfs 进行一个重载，遍历我们所有的节点，并进行 dfspublic void dfs() {isVisited = new boolean[5];//遍历所有的节点，进行 dfs （回溯）for (int i = 0; i < getNumOfEdges(); i++) {if (!isVisited[i]) {dfs(isVisited, i);}}}//对一个节点进行广度优先搜索的方法private void bfs(boolean[] isVisited, int i) {int u; //表示队列的头节点对应下标int w; //邻接节点 w//队列，记录节点访问的顺序LinkedList queue = new LinkedList();//访问节点，输出节点信息System.out.print(getValueByIndex(i) + " -> ");//标记为已访问isVisited[i] = true;//将节点加入队列queue.addLast(i);while (!queue.isEmpty()) {//取出队列的头节点下标u = (Integer) queue.removeFirst();//得到第一个邻接节点的下标 ww = getFirstNeighbor(u);while (w != -1) { //找到了//是否访问过if (!isVisited[w]) {System.out.print(getValueByIndex(w) + " -> ");//标记已经访问isVisited[w] = true;//入队列queue.addLast(w);}//以 u 为前驱点，找 w 后面的下一个邻接节点w = getNextNeighbor(u, w); //体现出广度优先}}}//遍历所有的节点，都进行广度优先搜索public void bfs() {isVisited = new boolean[5];for (int i = 0; i < getNumOfVertex(); i++) {if (!isVisited[i]) {bfs(isVisited, i);}}}//图中常用的方法//返回节点的个数public int getNumOfVertex() {return vertexList.size();}//返回边的个数public int getNumOfEdges() {return numOfEdges;}//返回节点 i(下标)对应的数据 0->"A" 1->"B" 2->"C"public String getValueByIndex(int i) {return vertexList.get(i);}//返回 v1 和 v2 的权值public int getWeight(int v1, int v2) {return edges[v1][v2];}//显示图对应的矩阵public void showGraph() {for (int[] link : edges) {System.out.println(Arrays.toString(link));}}//插入节点public void insertVertex(String vertex) {vertexList.add(vertex);}//添加边/**** @param v1 代表第一个顶点对应的下标* @param v2 代表第二个顶点对应的下标* @param weight*/public void insertEdge(int v1, int v2, int weight) {edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}
}