图

//创建图 package graph; import java.util.ArrayList; import java.util.Arrays; public class Graph { //存储顶点String,使用ArrayList(2)保存矩阵int[][]edges private ArrayList<String> vertexList;//存储顶点集合 private int[][] edges;//存储图对应的邻接矩阵 private int numOfEdges;//表示边的数目 public static void main(String[] args) { // TODO Auto-generated method stub //测试图是否创建 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-E graph.insertEdge(0, 1, 1);//A-B graph.insertEdge(0, 2, 1);//A-C graph.insertEdge(1, 2, 1);//B-C graph.insertEdge(1, 3, 1);//B-D graph.insertEdge(1, 4, 1);//B-E //显示邻接矩阵 graph.showGraph(); } //构造器 public Graph(int n) { edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; } //图中常用的方法 //返回结点的个数 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.err.println(Arrays.toString(link)); } } //插入节点 public void insertVertex(String vertex) { vertexList.add(vertex); } //添加边 /** * @param v1表示点的下标即第几个顶点"A"-"B" "A"->0 "B"->1 * @param v2表示第二个顶点对应的下标 * @param weight表示1或者0 */ public void insertEdge(int v1,int v2,int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } } //输出 [0, 1, 1, 0, 0] [1, 0, 1, 1, 1] [1, 1, 0, 0, 0] [0, 1, 0, 0, 0] [0, 1, 0, 0, 0]

package graph; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; public class Graph { //存储顶点String,使用ArrayList(2)保存矩阵int[][]edges private ArrayList<String> vertexList;//存储顶点集合 private int[][] edges;//存储图对应的邻接矩阵 private int numOfEdges;//表示边的数目 //定义给数组boolean[],记录某个结点是否被访问 private boolean[] isVisted; public static void main(String[] args) { // TODO Auto-generated method stub //测试图是否创建 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-E graph.insertEdge(0, 1, 1);//A-B graph.insertEdge(0, 2, 1);//A-C graph.insertEdge(1, 2, 1);//B-C graph.insertEdge(1, 3, 1);//B-D graph.insertEdge(1, 4, 1);//B-E //显示邻接矩阵 graph.showGraph(); //深度优先遍历 // System.out.print("DFS"); // graph.dfs(); //广度优先 System.out.println("BFS"); graph.bfs(); } //构造器 public Graph(int n) { edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; isVisted = new boolean[5]; } //得到第一个邻接结点的下标w /** * @param index * @return如果存在就返回对应的下标，否则返回-1 */ public int getFirstNeighbour(int index) { for (int i = 0; i < vertexList.size(); i++) { if(edges[index][i] > 0) { return i; } } return -1; } //根据前一个邻接结点的下标来获取下一个邻接结点 public int getNextNeighbor(int v1,int v2) { for(int j = v2 +1;j < vertexList.size();j++) { if(edges[v2][j] > 0) { return j; } } return -1; } //深度优先遍历算法 //i第一次就是0 public void dfs(boolean[] isVisted,int i) { //首先访问该结点，输出 System.out.println(getValueByIndex(i) + "->"); //将该结点设置为已经访问 isVisted[i] = true; //查找结点i的第一个邻接结点w int w = getFirstNeighbour(i); while (w != -1) {//说明有 if(!isVisted[w]) { dfs(isVisted,w); } //如果w已经被访问过 w = getNextNeighbor(i,w); } } //对dfs进行重载，遍历所有的结点，并进行dfs public void dfs() { //遍历所有结点，进行dfs(回溯) for (int i = 0; i < getNumOfVertex(); i++) { if (!isVisted[i]) { dfs(isVisted,i); } } } //对一个结点进行广度优先遍历的方法 private void bfs(boolean[] isVisted,int i) { int u ;//表示队列的头节点的下标 int w; //表示邻接结点的下标 //队列，结点访问顺序 LinkedList queue = new LinkedList(); //访问结点，输出结点信息 System.out.println(getValueByIndex(i) + "=>"); //标记为以访问 isVisted[i] = true; //将结点加入队列 queue.addLast(i); while (!queue.isEmpty()) { //取出队列的头节点下标 u = (Integer)queue.removeFirst();//返回的是Object,转为Integer,自动拆箱 //得到第一个邻接结点的下标 w = getFirstNeighbour(u); while (w != -1) { //找到w //是否访问过 if(!isVisted[w]) { //1.若结点w尚未被访问，则访问w,w标记为以访问 System.out.println(getValueByIndex(w) + "=>"); isVisted[w] = true; //入队 queue.addLast(w); } //以u为前驱点，找w后面的下一个邻接点 w = getNextNeighbor(i, w); //体现出广度优先 } } } //遍历所有结点，进行广度优先搜索 public void bfs() { for (int i = 0; i < getNumOfVertex(); i++) { if (!isVisted[i]) { bfs(isVisted,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.err.println(Arrays.toString(link)); } } //插入节点 public void insertVertex(String vertex) { vertexList.add(vertex); } //添加边 /** * @param v1表示点的下标即第几个顶点"A"-"B" "A"->0 "B"->1 * @param v2表示第二个顶点对应的下标 * @param weight表示1或者0 */ public void insertEdge(int v1,int v2,int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } }