Java用邻接矩阵实现广度优先

定义节点类：

//一个节点class Vertex{char label;boolean wasVisited;public Vertex(char label){this.label = label;wasVisited = false;}}

图：

class Graph{MAX_VERTS = 20;adjMat[][];nVerts;(){vertexList = new Vertex[MAX_VERTS];adjMat = new int[MAX_VERTS][MAX_VERTS];nVerts = 0;for(int i = 0; i < MAX_VERTS; i++){for(int j = 0; j < MAX_VERTS; j++)adjMat[i][j] = 0;}theQueue = new ArrayDeque();}(char lab){vertexList[nVerts++] = new Vertex(lab);}(int start, int end){adjMat[start][end] = 1;adjMat[end][start] = 1;}(int v){System.out.print(vertexList[v].label);}(int v){for(int i = 0; i < nVerts; i++){if(adjMat[v][i] == 1 && vertexList[i].wasVisited == false){return i;}}return -1;}//广度优先搜索/*** 规则1：访问下一个未来访问的邻接点（如果存在），这个顶点必须是当前顶点的邻接点，标记为已访问，并把它插入到队列中*** 规则2：如果因为已经没有未访问顶点而不能执行规则1，那么从队列头取一个顶点（如果存在），，并使其* 称为当前顶点** 规则3：如果因为队列为空而不能执行规则2，则搜索结束*/(){vertexList[0].wasVisited = true;displayVertex(0);;theQueue.offer(0);int v2;while( !theQueue.isEmpty()){int v1 = (int) theQueue.remove();while((v2 = getAdjUnvisiedVertex(v1)) != -1){vertexList[v2].wasVisited = true;displayVertex(v2);theQueue.offer(v2);}}for(int i = 0; i < nVerts; i++){vertexList[i].wasVisited = false;}} }

测试：

Graph theGraph = new Graph();theGraph.addVertex(‘A’);theGraph.addVertex(‘B’);theGraph.addVertex(‘C’);theGraph.addVertex(‘D’);theGraph.addVertex(‘E’);theGraph.addVertex(‘F’);theGraph.addVertex(‘G’);theGraph.addVertex(‘H’);theGraph.addVertex(‘I’);theGraph.addEdge(0, 1);//ABtheGraph.addEdge(0, 2);//ACtheGraph.addEdge(0, 3);//ADtheGraph.addEdge(0, 4);//AEtheGraph.addEdge(1, 5);//BFtheGraph.addEdge(5, 6);//FGtheGraph.addEdge(3, 6);//DGtheGraph.addEdge(6, 7);//GItheGraph.bfs();

广度优先搜索：ABCDEFGH

一旦有了意志，脚步也会轻松起来。