目录

图的创建和常用方法

深度优先遍历（Depth First Search）

广度优先遍历（Broad First Search） 

---

图的创建和常用方法

//无向图
public class Graph {//顶点集合private ArrayList<String> vertexList;//存储对应的邻接矩阵private int[][] edges;//边数private int numOfEdges;//构造方法//传入顶点数public Graph(int numOfVertex) {this.vertexList = new ArrayList<>(numOfVertex);this.edges = new int[numOfVertex][numOfVertex];this.numOfEdges = 0;//边数初始为0}//添加顶点public void  interVertex(String vertex){vertexList.add(vertex);}//添加边public void interEdge(int v1,int v2,int weight){edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}//图中常用方法：//返回节点的个数public int getNumOfVertex(){return vertexList.size();}//得到边的数目public int getNumOfEdges(){return numOfEdges;}//返回节点i对应的数据，以添加的顺序为准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.out.println(Arrays.toString(link));}}//测试public static void main(String[] args) {int n = 5;String[] vertexs={"A","B","C","D","E"};Graph graph = new Graph(n);//添加顶点for(String vertex:vertexs){graph.interVertex(vertex);}//添加边：A-C  A-B  A-E  B-Dgraph.interEdge(0,2,1);graph.interEdge(0,1,1);graph.interEdge(0,4,1);graph.interEdge(1,3,1);graph.showGraph();}
}

邻接矩阵： 

 

 

 

深度优先遍历（Depth First Search）

深度优先：每次访问当前节点后，首先访问当前节点的第一个邻接矩阵

添加标记顶点是否访问的数组：

 private boolean[] isVisted;

 在构造方法中初始化：

  this.isVisted = new boolean[numOfVertex];

得到第一个邻接节点的下标w： 

 //得到第一个邻接节点的下标wpublic int getFirstNeighbor(int index){for (int j = 0; j< vertexList.size(); j++) {if (edges[index][j]>0){return j;}}return -1;}

 根据前一个节点的坐标获取下一个邻接节点：

//根据前一个节点的坐标获取下一个邻接节点public int getNextNeighbor(int v1,int v2){for (int j = v2+1; j < vertexList.size(); j++) {if (edges[v1][j]>0)return j;}return -1;}

深度优先遍历： 

 //深度优先遍历private void dfs(boolean[] isVisted,int i){//首先访该节点，输出System.out.print(getValueByIndex(i)+"->");//访问标记isVisted[i] = true;//访问节点的第一个邻接节点int w = getFirstNeighbor(i);while (w!=-1){//有的话并且没有被访问过，就遍历该节点if (!isVisted[w]){dfs(isVisted,w);}//如果已经被访问过，就访问下一个w = getNextNeighbor(i,w);}}

 若是非连通图（有孤立点），需要将每个顶点深度遍历：

//若是非连通图，需要将每个顶点深度遍历public void dfs(){for (int i = 0; i < vertexList.size(); i++) {if (!isVisted[i]){dfs(isVisted,i);}}}

 如下图的深度遍历：

 

 //测试public static void main(String[] args) {int n = 6;String[] vertexs={"A","B","C","D","E","F"};Graph graph = new Graph(n);//添加顶点for(String vertex:vertexs){graph.interVertex(vertex);}//添加边：A-C  A-B  A-E  B-Dgraph.interEdge(0,2,1);graph.interEdge(0,1,1);graph.interEdge(0,4,1);graph.interEdge(1,3,1);graph.showGraph();graph.dfs();}

广度优先遍历（Broad First Search） 

 广度优先：先访问所有直接相邻的节点，然后访问所有与这些节点相邻的节点，以此类推，直到遍历完整个图。

//广度优先遍历//对一个节点进行广度优先算法private void bfs(boolean[] isVisted,int i){int u;//队列头结点的下标int w;//邻接节点LinkedList queue = new LinkedList();//  访问节点，输出System.out.print (getValueByIndex(i)+"=>");//    标记已访问isVisted[i]=true;//    添加到队列queue.addLast(i);while (!queue.isEmpty()){u = (Integer) queue.removeFirst();//得到第一个邻接节点的下标w = getFirstNeighbor(u);while (w!=-1){if (!isVisted[w]){//没有访问过System.out.print(getValueByIndex(w)+"=>");isVisted[w] = true;queue.addLast(w);}//以u为前一个节点，访问过去下一个节点w = getNextNeighbor(u, w);}}}//非连通图 广度优先遍历public void bfs(){this.isVisted = new boolean[vertexList.size()];for (int i = 0; i < vertexList.size(); i++) {if (!isVisted[i]){bfs(isVisted,i);}}}

测试：

System.out.println("广度优先");
graph.bfs();

 深度和广度测试：

public static void main(String[] args) {int n = 8;String[] vertexs={"1","2","3","4","5","6","7","8"};Graph graph = new Graph(n);//添加顶点for(String vertex:vertexs){graph.interVertex(vertex);}//添加边：1-2 1-3 2-4 2-5 4-8 5-8 3-6 3-7graph.interEdge(0,1,1);graph.interEdge(0,2,1);graph.interEdge(1,3,1);graph.interEdge(1,4,1);graph.interEdge(3,7,1);graph.interEdge(4,7,1);graph.interEdge(2,5,1);graph.interEdge(2,6,1);graph.showGraph();System.out.println("深度优先");graph.dfs();System.out.println();System.out.println("广度优先");graph.bfs();}