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;}theStack = new Stack();}(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);}//深度优先搜索/*** 深度优先搜索要得到距离起始点最远的顶点，然后不能继续前进的时候返回** 规则1：如果可能，访问一个邻接的未访问顶点，标记它，，并把它放入栈中** 规则2：当不能执行规则1时，如果栈不空，就从栈中弹出一个顶点** 规则3：如果不能执行规则1和规则2，就完成了整个搜索过程*/(){vertexList[0].wasVisited = true;//从第一个节点开始，标记为已访问displayVertex(0);//打印theStack.push(0);//入栈while( !theStack.isEmpty()){//得到一个未被访问的邻接节点int v = getAdjUnvisiedVertex((int) theStack.peek());if(v == -1)//没有这样的节点，该点访问完成theStack.pop();else{//继续访问vertexList[v].wasVisited = true;displayVertex(v);theStack.push(v);}}//所有节点访问完毕，重置所有节点为为访问状态for(int j = 0; j < nVerts; j++){vertexList[j].wasVisited = false;}}(int v){for(int i = 0; i < nVerts; i++){if(adjMat[v][i] == 1 && vertexList[i].wasVisited == false){return i;}}return -1;}}

测试：

Graph theGraph = new Graph();theGraph.addVertex(‘A’);theGraph.addVertex(‘B’);theGraph.addVertex(‘C’);theGraph.addVertex(‘D’);theGraph.addVertex(‘E’);theGraph.addEdge(0, 1);theGraph.addEdge(1, 2);theGraph.addEdge(0, 3);theGraph.addEdge(3, 4);theGraph.dfs();

按深度优先搜索： ABCDE

人的一辈子唯一做的就是，不断地用你手中