圖解

代碼實現

package com.atguigu.graph;import java.util.ArrayList; import java.util.Arrays;/*** @創建人 wdl* @創建時間 2021/4/2* @描述*/ public class Graph {private ArrayList<String> vertexList;//存儲頂點集合private int[][] edges;//存儲圖對應的鄰接矩陣private int numOfEdges;//表示邊的數目//定義一個Boolean數組，記錄某個節點是否被訪問private boolean[] isVisited;public static void main(String[] args) {//測試一把圖是否創建OKint n=5;//節點的個數String Vertexs[]={"A","B","C","D","E"};//創建圖對象Graph graph = new Graph(n);//循環的添加頂點for(String vertex:Vertexs){graph.insertVertex(vertex);}//添加邊graph.insertEdge(0,1,1);graph.insertEdge(0,2,1);graph.insertEdge(1,2,1);graph.insertEdge(1,3,1);graph.insertEdge(1,4,1);//顯示一把鄰接矩陣graph.showGraph();//測試一把，我們的dfs遍歷是否OKSystem.out.println("深度遍歷");graph.dfs();}//構造器public Graph(int n) {//初始化矩陣和vertexListedges = new int[n][n];vertexList = new ArrayList<>(n);numOfEdges=0;isVisited=new boolean[5];}//得到第一個鄰接節點的下標w/**** @param index* @return 如果存在就返回對應的下標，否則返回-1*/public 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;}//深度優先遍歷算法//i 第一次就是0public void dfs(boolean[] isVisited,int i){//首先我們訪問該節點，輸出System.out.print(getValueByIndex(i)+"->");//將節點設置為已經訪問isVisited[i]=true;//查找i的第一個鄰接節點wint w=getFirstNeighbor(i);while (w!=-1){//說明有if(!isVisited[w]){dfs(isVisited,w);}//如果w節點已經被訪問過w=getNextNeighbor(i,w);}}//對dfs進行一個重載，遍歷我們所有的節點，并進行dfspublic void dfs(){//遍歷所有的節點，進行dfs[回溯]for (int i = 0; i < getNumOfVertex(); i++) {if(!isVisited[i]){dfs(isVisited,i);}}}//圖中常用的方法//返回節點的個數public int getNumOfVertex(){return vertexList.size();}//顯示圖對應的矩陣public void showGraph(){for(int[] link:edges){System.out.println(Arrays.toString(link));}}//得到邊的數目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 insertVertex(String vertex){vertexList.add(vertex);}//添加邊/**** @param v1 表示點的下標是第幾個頂點 "A"-"B" "A"->0 "B"->1* @param v2 第二個頂點對應的下標* @param weight*/public void insertEdge(int v1,int v2,int weight){edges[v1][v2]=weight;edges[v2][v1]=weight;numOfEdges++;}}

總結

以上是生活随笔為你收集整理的图的深度优先遍历+图解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。