#图的实现并没有指针与引用的概念,相对来说建立一个图的结构还是比较简单的,最重要的是图的两种遍历方式,DFS和BFS真是重要极了。很多时候。但一个问题没有捷径的时候,不妨采用暴力遍历的方法。
这里给出图的实现及其方法 先定义一下图的点类,图是由点与线段组成的
//图是由点和线组成的 //定义一个点的类 class Vertex{ public boolean WasVisited; //顶点是否访问 public String label; //顶点的名字 Vertex(String lbl){ this.label = lbl; WasVisited = false; } }
然后我们定义一个图类,并定义一系列方法
//定义一个图类 //图中要可以添加顶点 可以添加边 class MyGragh{ private int NUM_Vertex; //顶点的数目 private Vertex[] verts; //存放顶点的数组 private int[][] adjMatrix; //定义二维的邻接矩阵 private int curVertNum; //当前是第几个顶点 MyGragh(int NUM_Vertex){ this.NUM_Vertex = NUM_Vertex; //初始化构造顶点的数目 verts = new Vertex[NUM_Vertex]; //顶点初始化 adjMatrix = new int[NUM_Vertex][NUM_Vertex]; //边的初始化 curVertNum = 0; //当前是第0个顶点 for (int i = 0; i < NUM_Vertex; i++) { for (int j = 0; j < NUM_Vertex; j++) { adjMatrix[i][j] = 0; } } } //给图添加顶点 public void addVertex(String label){ if(curVertNum<NUM_Vertex){ verts[curVertNum] = new Vertex(label); curVertNum++; } else{ System.out.println("顶点已经添加完毕。。。。。"); } } //查看当前的顶点 public void ShowVertex(int cur){ if(cur<= curVertNum ){ System.out.println(verts[cur].label+"===="); } else{ System.out.println("还没有这个顶点"); } } //给图添加边 public void addEdge(int i,int j){ if(i<NUM_Vertex && j<NUM_Vertex){ adjMatrix[i][j] = 1; //无向图 adjMatrix[j][i] = 1; } else{ System.out.println("当前连接无效。。。"+i+" "+j); } } //查看图的邻接表 public void ShowAdjMatrix(){ for (int i = 0; i < NUM_Vertex; i++) { System.out.println(); for (int j = 0; j < NUM_Vertex; j++) { System.out.print(adjMatrix[i][j]+" "); } } } public void setVertsFalse(){ for (int i = 0; i < NUM_Vertex; i++) { verts[i].WasVisited = false; } } //判断第i个节点是否还有点未曾遍历 public int IsUnvisitedAdjVerts(int i){ for (int j = 0; j < NUM_Vertex; j++) { if(adjMatrix[i][j]==1&&verts[j].WasVisited == false){ return j; } } return -1; } //深度优先遍历图 DepthFirstTraverse //栈的合理使用 public void DFS(int i){ System.out.println(); Stack<Integer> sta = new Stack<Integer>(); Vertex v1 = verts[i]; v1.WasVisited = true; sta.push(i); System.out.print(verts[i].label+" "); while(sta.size()>0){ while(IsUnvisitedAdjVerts(i)!=-1){ i = IsUnvisitedAdjVerts(i); System.out.print(verts[i].label+" "); verts[i].WasVisited = true; sta.push(i); } sta.pop(); if(sta.size()>0){ i = sta.peek(); } } } //广度优先遍历 breadth-first search //队列的合理使用 public void BFS(int i){ System.out.println(); Queue<Integer> qu = new LinkedList<Integer>(); Vertex v1 = verts[i]; v1.WasVisited = true; qu.offer(i); int j; while(qu.size()>0){ while(IsUnvisitedAdjVerts(i)!=-1){ j = IsUnvisitedAdjVerts(i); qu.offer(j); verts[j].WasVisited = true; } System.out.print(verts[qu.peek()].label+" "); qu.poll(); if(qu.size()>0){ i = qu.peek(); } } } }
图的测试,着重关注建立一个图
MyGragh mg = new MyGragh(10); mg.addVertex("A"); mg.addVertex("B"); mg.addVertex("C"); mg.addVertex("D"); mg.addVertex("E"); mg.addVertex("F"); mg.addVertex("G"); mg.addVertex("H"); mg.addVertex("I"); mg.addVertex("J"); mg.addEdge(0, 1); mg.addEdge(1, 2); mg.addEdge(2, 3); mg.addEdge(0, 4); mg.addEdge(4, 5); mg.addEdge(5, 6); mg.addEdge(0, 7); mg.addEdge(7, 8); mg.addEdge(8, 9); mg.addEdge(9, 10); mg.ShowVertex(6); mg.ShowAdjMatrix();