圖的深度優先遍歷

2019-11-11 04:18:15

字體：大中小

來源：轉載

供稿：網友

深度優先遍歷是連通圖的一種遍歷策略。其基本思想如下：

設x是當前被訪問頂點，在對x做過訪問標記后，選擇一條從x出發的未檢測過的邊(x，y)。若發現頂點y已訪問過，則重新選擇另一條從x出發的未檢測過的邊，否則沿邊(x，y)到達未曾訪問過的y，對y訪問并將其標記為已訪問過；然后從y開始搜索，直到搜索完從y出發的所有路徑，即訪問完所有從y出發可達的頂點之后，才回溯到頂點x，并且再選擇一條從x出發的未檢測過的邊。上述過程直至從x出發的所有邊都已檢測過為止。代碼示例中遍歷如下圖所示的圖。 ?

這里寫圖片描述

代碼：package test.algorithm.FastSlowPointer;import java.util.Stack;/** * 圖的深度優先遍歷 * @author serenity * */public class Graph { // 存儲節點信息 PRivate char[] vertices; // 存儲邊信息（鄰接矩陣） private int[][] arcs; // 圖的節點數 private int vexnum; // 記錄節點是否已被遍歷 private boolean[] visited; // 初始化 public Graph(int n) { vexnum = n; vertices = new char[n]; arcs = new int[n][n]; visited = new boolean[n]; for (int i = 0; i < vexnum; i++) { for (int j = 0; j < vexnum; j++) { arcs[i][j] = 0; } } } // 添加邊(無向圖) public void addEdge(int i, int j) { // 邊的頭尾不能為同一節點 if (i == j)return; arcs[i][j] = 1; arcs[j][i] = 1; } // 設置節點集 public void setVertices(char[] vertices) { this.vertices = vertices; } // 設置節點訪問標記 public void setVisited(boolean[] visited) { this.visited = visited; } // 打印遍歷節點 public void visit(int i){ System.out.print(vertices[i] + " "); } // 從第i個節點開始深度優先遍歷 private void traverse(int i){ // 標記第i個節點已遍歷 visited[i] = true; // 打印當前遍歷的節點 visit(i); // 遍歷鄰接矩陣中第i個節點的直接聯通關系 for(int j=0;j<vexnum;j++){ // 目標節點與當前節點直接聯通，并且該節點還沒有被訪問，遞歸 if(arcs[i][j]==1 && visited[j]==false){ traverse(j); } } } // 圖的深度優先遍歷（遞歸） public void DFSTraverse(){ // 初始化節點遍歷標記 for (int i = 0; i < vexnum; i++) { visited[i] = false; } // 從沒有被遍歷的節點開始深度遍歷 for(int i=0;i<vexnum;i++){ if(visited[i]==false){ // 若是連通圖，只會執行一次 traverse(i); } } } // 圖的深度優先遍歷（非遞歸） public void DFSTraverse2(){ // 初始化節點遍歷標記 for (int i = 0; i < vexnum; i++) { visited[i] = false; } Stack<Integer> s = new Stack<Integer>(); for(int i=0;i<vexnum;i++){ if(!visited[i]){ //連通子圖起始節點 s.add(i); do{ // 出棧 int curr = s.pop(); // 如果該節點還沒有被遍歷，則遍歷該節點并將子節點入棧 if(visited[curr]==false){ // 遍歷并打印 visit(curr); visited[curr] = true; // 沒遍歷的子節點入棧 for(int j=vexnum-1; j>=0 ; j-- ){ if(arcs[curr][j]==1 && visited[j]==false){ s.add(j); } } } }while(!s.isEmpty()); } } } public static void main(String[] args) { Graph g = new Graph(9); char[] vertices = {'A','B','C','D','E','F','G','H','I'}; g.setVertices(vertices); g.addEdge(0, 1); g.addEdge(0, 5); g.addEdge(1, 0); g.addEdge(1, 2); g.addEdge(1, 6); g.addEdge(1, 8); g.addEdge(2, 1); g.addEdge(2, 3); g.addEdge(2, 8); g.addEdge(3, 2); g.addEdge(3, 4); g.addEdge(3, 6); g.addEdge(3, 7); g.addEdge(3, 8); g.addEdge(4, 3); g.addEdge(4, 5); g.addEdge(4, 7); g.addEdge(5, 0); g.addEdge(5, 4); g.addEdge(5, 6); g.addEdge(6, 1); g.addEdge(6, 3); g.addEdge(6, 5); g.addEdge(6, 7); g.addEdge(7, 3); g.addEdge(7, 4); g.addEdge(7, 6); g.addEdge(8, 1); g.addEdge(8, 2); g.addEdge(8, 3); System.out.print("深度優先遍歷（遞歸）："); g.DFSTraverse(); System.out.println(); System.out.print("深度優先遍歷（非遞歸）："); g.DFSTraverse2(); }}

上一篇：HPUOJ--2017寒假作業專題0/I-SDOI

下一篇：關于去除JS數組中的重復元素問題