圖的遍歷

一、DFS（Depth First Search）

概念：
從初始訪問點出發(fā)，訪問其第一個鄰接節(jié)點；然后把這個鄰接節(jié)點作為初始節(jié)點，繼續(xù)訪問它的第一個鄰接節(jié)點。

即每次都在訪問完當前節(jié)點過后，訪問它的第一個鄰接節(jié)點。

算法：

訪問初始節(jié)點v（下標），并標記v已被訪問；

查找節(jié)點v的第一個鄰接節(jié)點w（下標）；

如果w存在，則繼續(xù)4步驟；如果w不存在，則返回1步驟；

如果w未被訪問過，對w進行dfs遞歸操作（重復1、2、3操作）；

查找節(jié)點v的w鄰接節(jié)點的下一個鄰接節(jié)點，返回3步驟

源代碼如下：

import java.util.ArrayList; import java.util.Arrays;public class graph {private ArrayList<String> vertexList;// 定義頂點列表private int[][] edges;// 存儲圖對應的鄰接矩陣private int numOfEdges;// 存儲邊private boolean isVisited[];// 標記頂點是否已被訪問public static void main(String[] args) {// TODO Auto-generated method stub// 測試圖int n = 5;// 定義頂點個數(shù)String vertexs[] = { "A", "B", "C", "D", "E" };// 創(chuàng)建圖對象graph graph = new graph(n);// 循環(huán)添加頂點for (String vertex : vertexs) {// 每次循環(huán)從vertexValue取出來一個值（定義為value）graph.insertVertex(vertex);// 把頂點加進去}// 添加邊// A-B A-C B-C B-D B-E// 權值默認為是1graph.insertEdges(0, 1, 1);// A-Bgraph.insertEdges(0, 2, 1);// A-Cgraph.insertEdges(1, 2, 1);// B-Cgraph.insertEdges(1, 3, 1);// B-Dgraph.insertEdges(1, 4, 1);// B-E// 顯示鄰接矩陣graph.show();// DFSgraph.dfs();}// ————————————--------------------------------------------------------// 首先定義圖的屬性// 1.構造器public graph(int n) {// 首先要傳入頂點的數(shù)目// 初始化矩陣和vertexListedges = new int[n][n];vertexList = new ArrayList<String>();// 初始化頂點列表numOfEdges = 0;// 可省略，因為默認為0isVisited = new boolean[5];}// 2.插入頂點public void insertVertex(String vertex) {vertexList.add(vertex);}// 3.設置邊/*** * @param v1 第一個頂點的下標* @param v2 第二個頂點的下標* @param weight 權值*/public void insertEdges(int v1, int v2, int weight) {// 這里是定義無向圖，所以兩個方向都要定義edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}// 4.返回頂點個數(shù)public int getnumOfVertexs() {return vertexList.size();}// 5.返回邊個數(shù)public int getnumOfEdges() {return numOfEdges;}// 6.返回頂點i（頂點的下標）的對應的數(shù)據(jù)/*** * @param i返回數(shù)據(jù)下標* @return 返回數(shù)據(jù) 例：0->A 1->B 2->C 3->D 4->E*/public String getValueByIndex(int i) {return vertexList.get(i);}// 7.返回v1,v2兩頂點之間的權值public int getWeight(int v1, int v2) {return edges[v1][v2];}// 8.打印鄰接矩陣（本質(zhì)：遍歷圖）public void show() {for (int[] link : edges) {System.out.println(Arrays.toString(link));}} //————————————-------------------------------------------------------- // DFS算法步驟// 1.得到第一個鄰接節(jié)點下標w/*** * @param index* @return 如果存在就返回它的下標，沒有就返回-1*/public int getFirstNerghborIndex(int index) {// 傳入當前節(jié)點的下標indexfor (int w = 0; w < vertexList.size(); w++) {if (edges[index][w] > 0) {// 如果下一個鄰接節(jié)點存在return w;// 返回它的下標}}return -1;// 沒有返回就返回-1}// 2.根據(jù)前一個鄰接節(jié)點的下標來獲取下一個鄰接節(jié)點/*** * @param v1* @param v2* @return*/public int getNextNeighbor(int v1, int v2) {for (int w = v2 + 1; w < vertexList.size(); w++) {if (edges[v1][w] > 0) {return w;}}return -1;}// 3.開始深搜遍歷public void dfs(boolean[] isVisited, int i) {// 判斷是否遍歷過的標記，定義節(jié)點下標// 首先訪問當前節(jié)點，輸出System.out.print(getValueByIndex(i) + "->");// 訪問過后，要標記節(jié)點已訪問isVisited[i] = true;// 查找節(jié)點i的第一個鄰接節(jié)點int w = getFirstNerghborIndex(i);while (w != -1) {// 存在if (!isVisited[w]) {// 如果沒有被標記過dfs(isVisited, w);// 以w為初始節(jié)點重新開始，遞歸操作dfs}// 如果已經(jīng)被訪問過w = getNextNeighbor(i, w);}}// 對dfs進行重載，遍歷所有節(jié)點public void dfs() {for (int i = 0; i < getnumOfVertexs(); i++) {while (!isVisited[i]) {// 如果沒被訪問過dfs(isVisited, i);}}} }

二、BFS（Broad First Search）

.addLast()獲取最后一個節(jié)點

概念：
類似一個分層搜索過程，BFS需要一個隊列以保持訪問過節(jié)點的順序，以便按照這個順序來訪問他們的鄰接節(jié)點。

算法：

訪問初始節(jié)點v，并將其標記已經(jīng)訪問；

把節(jié)點v加入隊列；

當隊列非空時，繼續(xù)執(zhí)行，否則算法結束；

出隊列，取得隊頭結點u；

查找初始節(jié)點也是隊頭結點u第一個鄰接節(jié)點w；

若節(jié)點u的第一個鄰接節(jié)點w不存在，執(zhí)行步驟3，否則循環(huán)執(zhí)行下述三個操作：
（1）若節(jié)點w未被訪問，訪問它并標記已經(jīng)訪問；
（2）節(jié)點w入隊列；
（3）查找節(jié)點u的繼w鄰接節(jié)點后的下一個鄰接節(jié)點，轉到步驟6。

源代碼如下：

import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList;public class graph {private ArrayList<String> vertexList;// 定義頂點列表private int[][] edges;// 存儲圖對應的鄰接矩陣private int numOfEdges;// 存儲邊private boolean isVisited[];// 標記頂點是否已被訪問public static void main(String[] args) {// TODO Auto-generated method stub// 測試圖int n = 5;// 定義頂點個數(shù)String vertexs[] = { "A", "B", "C", "D", "E" };// 創(chuàng)建圖對象graph graph = new graph(n);// 循環(huán)添加頂點for (String vertex : vertexs) {// 每次循環(huán)從vertexValue取出來一個值（定義為value）graph.insertVertex(vertex);// 把頂點加進去}// 添加邊// A-B A-C B-C B-D B-E// 權值默認為是1graph.insertEdges(0, 1, 1);// A-Bgraph.insertEdges(0, 2, 1);// A-Cgraph.insertEdges(1, 2, 1);// B-Cgraph.insertEdges(1, 3, 1);// B-Dgraph.insertEdges(1, 4, 1);// B-E// 顯示鄰接矩陣graph.show();/*// DFSSystem.out.println();System.out.println("DFS：");graph.dfs();*/System.out.println();System.out.println();System.out.println("BFS：");graph.bfs();}// ————————————--------------------------------------------------------// 首先定義圖的屬性// 1.構造器public graph(int n) {// 首先要傳入頂點的數(shù)目// 初始化矩陣和vertexListedges = new int[n][n];vertexList = new ArrayList<String>();// 初始化頂點列表numOfEdges = 0;// 可省略，因為默認為0isVisited = new boolean[vertexList.size() + 1];}// 2.插入頂點public void insertVertex(String vertex) {vertexList.add(vertex);}// 3.設置邊/*** * @param v1 第一個頂點的下標* @param v2 第二個頂點的下標* @param weight 權值*/public void insertEdges(int v1, int v2, int weight) {// 這里是定義無向圖，所以兩個方向都要定義edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}// 4.返回頂點個數(shù)public int getnumOfVertexs() {return vertexList.size();}// 5.返回邊個數(shù)public int getnumOfEdges() {return numOfEdges;}// 6.返回頂點i（頂點的下標）的對應的數(shù)據(jù)/*** * @param i返回數(shù)據(jù)下標* @return 返回數(shù)據(jù) 例：0->A 1->B 2->C 3->D 4->E*/public String getValueByIndex(int i) {return vertexList.get(i);}// 7.返回v1,v2兩頂點之間的權值public int getWeight(int v1, int v2) {return edges[v1][v2];}// 8.打印鄰接矩陣（本質(zhì)：遍歷圖）public void show() {for (int[] link : edges) {System.out.println(Arrays.toString(link));}} //————————————-------------------------------------------------------- // DFS算法步驟// 1.得到第一個鄰接節(jié)點下標w/*** * @param index* @return 如果存在就返回它的下標，沒有就返回-1*/public int getFirstNerghborIndex(int index) {// 傳入當前節(jié)點的下標indexfor (int w = 0; w < vertexList.size(); w++) {if (edges[index][w] > 0) {// 如果下一個鄰接節(jié)點存在return w;// 返回它的下標}}return -1;// 沒有返回就返回-1}// 2.根據(jù)前一個鄰接節(jié)點的下標來獲取下一個鄰接節(jié)點/*** * @param v1為前驅點* @param v2為前驅點的當前鄰接節(jié)點* @return*/public int getNextNeighbor(int v1, int v2) {for (int w = v2 + 1; w < vertexList.size(); w++) {if (edges[v1][w] > 0) {return w;}}return -1;}// 3.開始深搜遍歷private void dfs(boolean[] isVisited, int i) {// 判斷是否遍歷過的標記，定義節(jié)點下標// 首先訪問當前節(jié)點，輸出System.out.print(getValueByIndex(i) + "->");// 訪問過后，要標記節(jié)點已訪問isVisited[i] = true;// 查找節(jié)點i的第一個鄰接節(jié)點int w = getFirstNerghborIndex(i);while (w != -1) {// 存在if (!isVisited[w]) {// 如果沒有被標記過dfs(isVisited, w);// 以w為初始節(jié)點重新開始，遞歸操作dfs}// 如果已經(jīng)被訪問過// 以u為前驅點，找w的下一個鄰接節(jié)點// w為輔助變量，每次進行此操作的時候更新值w = getNextNeighbor(i, w);}}// 對dfs進行重載，遍歷所有節(jié)點public void dfs() {for (int i = 0; i < getnumOfVertexs(); i++) {while (!isVisited[i]) {// 如果沒被訪問過dfs(isVisited, i);}}}// ————————————--------------------------------------------------------// BFS算法步驟private void bfs(boolean[] isVisited, int i) {int u;// 初始節(jié)點，隊頭結點int w;// 鄰接節(jié)點// 使用隊列記錄訪問節(jié)點的順序LinkedList queue = new LinkedList();// 訪問節(jié)點（輸出節(jié)點信息）System.out.print(getValueByIndex(i) + "->"); 標記為已訪問isVisited[i] = true;// 若已訪問，添加節(jié)點到隊列queue.addLast(i);// 重復操作while (!queue.isEmpty()) {// 如果隊列不為空// 取出隊列的頭節(jié)點下標u = (Integer) queue.removeFirst();// 得到第一個鄰接節(jié)點的下標ww = getFirstNerghborIndex(u);while (w != -1) {// 找到鄰接節(jié)點// 判斷是否訪問過if (!isVisited[w]) {// 如果沒有訪問過System.out.print(getValueByIndex(w) + "->");// 訪問isVisited[w] = true;// 標記為已訪問// 鄰接節(jié)點入隊列queue.addLast(w);}// 以u為前驅點，訪問w的下一個鄰接節(jié)點w = getNextNeighbor(u, w);}}}// 對bfs進行重載，遍歷所有節(jié)點public void bfs() {for (int i = 0; i < getnumOfVertexs(); i++) {while (!isVisited[i]) {// 如果沒被訪問過bfs(isVisited, i);}}} }

如果要同時顯示DFS和BFS遍歷結果，需將構造器中的初始化部分摘出來，分別放到DFS和BFS的重載方法里，每次調(diào)用時重新分配，就不會出現(xiàn)執(zhí)行完一種遍歷無法執(zhí)行第二種遍歷的情況。

代碼如下：

import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList;public class graph {private ArrayList<String> vertexList;// 定義頂點列表private int[][] edges;// 存儲圖對應的鄰接矩陣private int numOfEdges;// 存儲邊private boolean isVisited[];// 標記頂點是否已被訪問public static void main(String[] args) {// TODO Auto-generated method stub// 測試圖int n = 5;// 定義頂點個數(shù)String vertexs[] = { "A", "B", "C", "D", "E" };// 創(chuàng)建圖對象graph graph = new graph(n);// 循環(huán)添加頂點for (String vertex : vertexs) {// 每次循環(huán)從vertexValue取出來一個值（定義為value）graph.insertVertex(vertex);// 把頂點加進去}// 添加邊// A-B A-C B-C B-D B-E// 權值默認為是1graph.insertEdges(0, 1, 1);// A-Bgraph.insertEdges(0, 2, 1);// A-Cgraph.insertEdges(1, 2, 1);// B-Cgraph.insertEdges(1, 3, 1);// B-Dgraph.insertEdges(1, 4, 1);// B-E// 顯示鄰接矩陣graph.show();// DFSSystem.out.println();System.out.println("DFS：");graph.dfs();System.out.println();System.out.println();System.out.println("BFS：");graph.bfs();}// ————————————--------------------------------------------------------// 首先定義圖的屬性// 1.構造器public graph(int n) {// 首先要傳入頂點的數(shù)目// 初始化矩陣和vertexListedges = new int[n][n];vertexList = new ArrayList<String>();// 初始化頂點列表numOfEdges = 0;// 可省略，因為默認為0}// 2.插入頂點public void insertVertex(String vertex) {vertexList.add(vertex);}// 3.設置邊/*** * @param v1 第一個頂點的下標* @param v2 第二個頂點的下標* @param weight 權值*/public void insertEdges(int v1, int v2, int weight) {// 這里是定義無向圖，所以兩個方向都要定義edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}// 4.返回頂點個數(shù)public int getnumOfVertexs() {return vertexList.size();}// 5.返回邊個數(shù)public int getnumOfEdges() {return numOfEdges;}// 6.返回頂點i（頂點的下標）的對應的數(shù)據(jù)/*** * @param i返回數(shù)據(jù)下標* @return 返回數(shù)據(jù) 例：0->A 1->B 2->C 3->D 4->E*/public String getValueByIndex(int i) {return vertexList.get(i);}// 7.返回v1,v2兩頂點之間的權值public int getWeight(int v1, int v2) {return edges[v1][v2];}// 8.打印鄰接矩陣（本質(zhì)：遍歷圖）public void show() {for (int[] link : edges) {System.out.println(Arrays.toString(link));}} //————————————-------------------------------------------------------- // DFS算法步驟// 1.得到第一個鄰接節(jié)點下標w/*** * @param index* @return 如果存在就返回它的下標，沒有就返回-1*/public int getFirstNerghborIndex(int index) {// 傳入當前節(jié)點的下標indexfor (int w = 0; w < vertexList.size(); w++) {if (edges[index][w] > 0) {// 如果下一個鄰接節(jié)點存在return w;// 返回它的下標}}return -1;// 沒有返回就返回-1}// 2.根據(jù)前一個鄰接節(jié)點的下標來獲取下一個鄰接節(jié)點/*** * @param v1* @param v2* @return*/public int getNextNeighbor(int v1, int v2) {for (int w = v2 + 1; w < vertexList.size(); w++) {if (edges[v1][w] > 0) {return w;}}return -1;}// 3.開始深搜遍歷private void dfs(boolean[] isVisited, int i) {// 判斷是否遍歷過的標記，定義節(jié)點下標// 首先訪問當前節(jié)點，輸出System.out.print(getValueByIndex(i) + "->");// 訪問過后，要標記節(jié)點已訪問isVisited[i] = true;// 查找節(jié)點i的第一個鄰接節(jié)點int w = getFirstNerghborIndex(i);while (w != -1) {// 存在if (!isVisited[w]) {// 如果沒有被標記過dfs(isVisited, w);// 以w為初始節(jié)點重新開始，遞歸操作dfs}// 如果已經(jīng)被訪問過w = getNextNeighbor(i, w);}}// 對dfs進行重載，遍歷所有節(jié)點public void dfs() {isVisited = new boolean[5];for (int i = 0; i < getnumOfVertexs(); i++) {while (!isVisited[i]) {// 如果沒被訪問過dfs(isVisited, i);}}}// ————————————--------------------------------------------------------// BFS算法步驟private void bfs(boolean[] isVisited, int i) {int u;// 初始節(jié)點，隊頭結點int w;// 鄰接節(jié)點// 使用隊列記錄訪問節(jié)點的順序LinkedList queue = new LinkedList();// 訪問節(jié)點（輸出節(jié)點信息）System.out.print(getValueByIndex(i) + "->"); 標記為已訪問isVisited[i] = true;// 若已訪問，添加節(jié)點到隊列queue.addLast(i);// 重復操作while (!queue.isEmpty()) {// 如果隊列不為空// 取出隊列的頭節(jié)點下標u = (Integer) queue.removeFirst();// 得到第一個鄰接節(jié)點的下標ww = getFirstNerghborIndex(u);while (w != -1) {// 找到鄰接節(jié)點// 判斷是否訪問過if (!isVisited[w]) {// 如果沒有訪問過System.out.print(getValueByIndex(w) + "->");// 訪問isVisited[w] = true;// 標記為已訪問// 鄰接節(jié)點入隊列queue.addLast(w);}// 以u為前驅點，訪問w的下一個鄰接節(jié)點w = getNextNeighbor(u, w);}}}// 對bfs進行重載，遍歷所有節(jié)點public void bfs() {isVisited = new boolean[5];for (int i = 0; i < getnumOfVertexs(); i++) {while (!isVisited[i]) {// 如果沒被訪問過bfs(isVisited, i);}}} }

總結

以上是生活随笔為你收集整理的图的遍历（Java）构造器的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。