Java实现图:邻接矩阵表示、深度优先搜索、广度优先搜索、无向图

程序中用到的栈和队列实现请参见另外的博文。package test2;class Vertex{private char vertexName;public boolean wasVisited;public Vertex(char name){vertexName = name;wasVisited = false;}public void displayVertexName(){System.out.println(" name:"+vertexName);}}public class Graph {private int MAX_VERTEX;private Vertex[] vertexList;private Stack stack;private queue que;private int adjMatrix[][];private int nVertex;public Graph(int max){MAX_VERTEX = max;vertexList = new Vertex[MAX_VERTEX];stack = new Stack(MAX_VERTEX);//深度遍历使用que = new queue(MAX_VERTEX);//广度遍历使用adjMatrix = new int[MAX_VERTEX][MAX_VERTEX];nVertex = 0;for(int i = 0; i < MAX_VERTEX; i++){for(int j = 0; j< MAX_VERTEX ; j++){adjMatrix[i][j] = 0;}}}public boolean addVertex(char name){if(nVertex < MAX_VERTEX){vertexList[nVertex++] = new Vertex(name);;return true;}else{return false;}}public boolean addEdge(int startVertex, int endVertex){if(startVertex < nVertex && endVertex < nVertex){adjMatrix[startVertex][endVertex] = 1;adjMatrix[endVertex][startVertex] = 1;return true;}else{return false;}}public int getUnvisitedVertex(int j){//获取与该顶点邻接的未访问顶点for(int i = 0; i < nVertex ; i++){if(adjMatrix[j][i] == 1 && vertexList[i].wasVisited == false){//可达,又未被访问过return i;}}return -1;}public void depthFirstSearch(){stack.push(0);//首先将第0个元素入栈;//vertexList[0].displayVertexName();//******若要输出该图的最小生成树,则删掉这行代码;vertexList[0].wasVisited = true;//标识为已访问while(!stack.isEmpty()){//若栈不空int unvisitedVer = getUnvisitedVertex(stack.getTopValue());//获取一个与该顶点邻接的未访问顶点if(unvisitedVer != -1){ //存在与这个点相连的未访问顶点;vertexList[stack.getTopValue()].displayVertexName();<span style="color:#FF0000;">//******若要输出该图的最小生成树,则加上这行代码;</span>vertexList[unvisitedVer].displayVertexName();//访问它,并标识为已访问vertexList[unvisitedVer].wasVisited = true;System.out.println(" ");stack.push(unvisitedVer);//入栈}else{//与该顶点相连的所有顶点均被访问过,,将该顶点出栈;stack.pop();}}//for(int i = 0; i< nVertex; i++){//重置顶点均未被访问过,保证下次遍历能进行。vertexList[i].wasVisited = false;}}public void breadthFirstSearch(){que.insert(0);vertexList[0].displayVertexName();vertexList[0].wasVisited = true;while(!que.isEmpty()){int unvisit = getUnvisitedVertex(que.getFrontElement());if(unvisit != -1){vertexList[unvisit].displayVertexName();vertexList[unvisit].wasVisited = true;que.insert(unvisit);}else{que.remove();}}for(int i=0; i< nVertex ; i++){vertexList[i].wasVisited = false;}}}class GraphApp{public static void main(String args[]){Graph g = new Graph(9);g.addVertex('A');g.addVertex('B');g.addVertex('C');g.addVertex('D');g.addVertex('E');g.addVertex('F');g.addEdge(0, 1);g.addEdge(1, 2);//g.addEdge(2, 3);g.addEdge(3, 4);g.addEdge(4, 5);g.addEdge(1, 4);g.addEdge(1, 5);g.addEdge(3, 5);//g.breadthFirstSearch();g.depthFirstSearch();}}

最小生成树运行结果:

name:A name:B name:B name:C name:B name:E name:E name:D name:D name:F

愚者用肉体监视心灵,智者用心灵监视肉体

Java实现图:邻接矩阵表示、深度优先搜索、广度优先搜索、无向图

相关文章:

你感兴趣的文章:

标签云: