圖的深度優(yōu)先遍歷

數(shù)據(jù)結(jié)構(gòu)遍歷的意義

樹的遍歷

圖的遍歷

樹的前序遍歷


圖遍歷和樹遍歷區(qū)別



知識(shí)回顧

樹的深度優(yōu)先遍歷



普通函數(shù)和遞歸函數(shù)調(diào)用的區(qū)別

圖的深度優(yōu)先遍歷的過程


初始visited數(shù)組都是fasle，當(dāng)從頂點(diǎn)0開始調(diào)用時(shí)， 如果沒有被遍歷，那么遍歷結(jié)果列表中添加這個(gè)頂點(diǎn)，然后開始for循環(huán)，執(zhí)行dfs(1)



Java實(shí)現(xiàn)圖的DFS
g.txt

7 8
0 1
0 2
1 3
1 4
2 3
2 6
3 5
5 6


import java.io.File;
import java.io.IOException;
import java.util.TreeSet;
import java.util.Scanner;


/// 暫時(shí)只支持無向無權(quán)圖
public class Graph {

    private int V;
    private int E;
    private TreeSet<Integer>[] adj;

    public Graph(String pathStr){

        File file = new File(pathStr);

        try(Scanner scanner = new Scanner(file)){

            V = scanner.nextInt();
            if(V < 0) throw new IllegalArgumentException("V must be non-negative");
            adj = new TreeSet[V];
            for(int i = 0; i < V; i ++)
                adj[i] = new TreeSet<Integer>();

            E = scanner.nextInt();
            if(E < 0) throw new IllegalArgumentException("E must be non-negative");

            for(int i = 0; i < E; i ++){
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);

                if(a == b) throw new IllegalArgumentException("Self Loop is Detected!");
                if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are Detected!");

                adj[a].add(b);
                adj[b].add(a);
            }
        }
        catch(IOException e){
            e.printStackTrace();
        }
    }

    private void validateVertex(int v){
        if(v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + "is invalid");
    }

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    public boolean hasEdge(int v, int w){
        validateVertex(v);
        validateVertex(w);
        return adj[v].contains(w);
    }

    public Iterable<Integer> adj(int v){
        validateVertex(v);
        return adj[v];
    }

    public int degree(int v){
        validateVertex(v);
        return adj[v].size();
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();

        sb.append(String.format("V = %d, E = %d\n", V, E));
        for(int v = 0; v < V; v ++){
            sb.append(String.format("%d : ", v));
            for(int w : adj[v])
                sb.append(String.format("%d ", w));
            sb.append('\n');
        }
        return sb.toString();
    }

    public static void main(String[] args){

        Graph g = new Graph("g.txt");
        System.out.print(g);
    }
}

GraphDFS.java

package com.duanxuehan.dfs05;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author Eric Lee
 * @date 2020/11/5 20:52
 */
public class GrahDFS {
    // 基本圖表示
    private Graph G;
    // 該節(jié)點(diǎn)是否被遍歷
    private boolean[] visited;
    // 每個(gè)頂點(diǎn)被遍歷到的順序
    private ArrayList<Integer> order = new ArrayList<>();

    // 定義構(gòu)造函數(shù)，直接在構(gòu)造函數(shù)中執(zhí)行 dfs
    public GrahDFS(Graph G){
        // 初始化 圖
        this.G = G;
        // 初始化 是否被遍歷過的數(shù)組，長度和頂點(diǎn)個(gè)數(shù)一樣
        // 默認(rèn)false也就是沒有被遍歷過
        visited = new boolean[G.V()];
        System.out.println(Arrays.toString(visited));
        // 直接從頂點(diǎn)0 開始進(jìn) dfs
        dfs(0);

    }

    public void dfs(int v){
        System.out.println("開始深度優(yōu)先遍歷"+v+"頂點(diǎn)");
        // 能進(jìn)入這里說明v頂點(diǎn)接下來要被遍歷了
        visited[v] = true;
        // 向記錄頂點(diǎn)遍歷順序的 order列表中添加此頂點(diǎn)
        order.add(v);
        // 遍歷這個(gè)頂點(diǎn)所有的鄰接頂點(diǎn)
        for(int w : G.adj(v)){
            // 每次w代表 和v相鄰頂點(diǎn)中的一個(gè)
            // 如果這個(gè)頂點(diǎn)沒有被遍歷過， 繼續(xù)調(diào)用該頂點(diǎn)的深度優(yōu)先
            if (!visited[w]){
                dfs(w);
            }
        }
    }
    public ArrayList<Integer> order(){
        return order;
    }
    public static void main(String[] args) {
        Graph g = new Graph("g.txt");
        GrahDFS grahDFS = new GrahDFS(g);
        System.out.println(grahDFS.order());
    }

}

DFS的改進(jìn)

如果是如下的圖結(jié)構(gòu)



對應(yīng)的txt

7 6
0 1
0 2
1 3
1 4
2 3
2 6

執(zhí)行dfs之后我們發(fā)現(xiàn) 頂點(diǎn)5并沒有被遍歷，這是因?yàn)槲覀僤fs是從0開始的
只調(diào)用一次， 5和其他頂點(diǎn)并沒有聯(lián)通， 所以應(yīng)該執(zhí)行dfs(5)



求聯(lián)通分量的個(gè)數(shù)

CC.java

package com.duanxuehan.liantongfenliang06;
import com.duanxuehan.dfs05.Graph;

import java.util.Arrays;

/**
 * 求解聯(lián)通分量的個(gè)數(shù)
 */
public class CC {
    // 定義表示
    private Graph G;
    // 定義是否被遍歷數(shù)組
    private int[] visited;
    // 定義一個(gè)計(jì)數(shù)變量，統(tǒng)計(jì)聯(lián)通分量的個(gè)數(shù)
    private int cccount = 0;
    // 構(gòu)造函數(shù)
    public CC(Graph G){
        this.G = G;
        // 初始化布爾數(shù)組的值
        visited = new int[G.V()];
        // 默認(rèn)將數(shù)組中所有值變成 -1， 代表沒有被遍歷過
        for (int i = 0; i < visited.length; i++) {
            visited[i] = -1;
        }
        System.out.println("visited初始值");
        System.out.println(Arrays.toString(visited));
        // 循環(huán)調(diào)用 每個(gè)頂點(diǎn)的dfs
        for (int v = 0; v < G.V() ; v++) {
            if (visited[v] == -1){
                dfs(v, cccount);
                cccount ++;
            }
        }
    }
    // 深度優(yōu)先過程
    public void dfs(int v, int ccid){
        // 使用ccid表示是否被遍歷過,
        // 只要不是-1證明已經(jīng)被遍歷過，
        // 具體ccid的值實(shí)際代表的是所屬第幾個(gè)聯(lián)通分量
        visited[v] = ccid;
        // 遍歷頂點(diǎn)v所有相鄰頂點(diǎn)
        for (int w :G.adj(v)){
            // visited[w]是 -1 代表w頂點(diǎn)沒有被遍歷過，要繼續(xù)進(jìn)行dfs
            if (visited[w] == -1){
                dfs(w,ccid);
            }
        }
    }
    // 編寫專門 統(tǒng)計(jì)聯(lián)通分量個(gè)數(shù)的方法
    public int count(){
        for (int e: visited){
            System.out.print(e + " ");
        }
        System.out.println();
        return cccount;

    }
    public static void main(String[] args) {
        Graph graph = new Graph("g2.txt");
        CC cc = new CC(graph);
        System.out.println(Arrays.toString(cc.visited));
        System.out.println(cc.count());
    }

}

g2.txt

9 7
0 1
0 2
1 3
1 4
2 3
2 6
7 8

聯(lián)通分量的改進(jìn)，列出所有的聯(lián)通分量詳情

CC2.java

package com.duanxuehan.liantongfenliang06;

import com.duanxuehan.dfs05.Graph;

import java.lang.reflect.Array;
import java.util.ArrayList;

// 聯(lián)通分量的改進(jìn)，列出所有的聯(lián)通分量詳情
public class CC2 {
    // 定義圖表示
    private Graph G;
    // 定義是否被遍歷數(shù)組
    private int[] visited;
    // 定義一個(gè)計(jì)數(shù)變量，統(tǒng)計(jì)聯(lián)通分量的個(gè)數(shù)
    private int cccount = 0;
    // 構(gòu)造函數(shù)
    public CC2(Graph G){
        this.G = G;
        visited = new int[G.V()];
        for (int i = 0; i < visited.length; i++) {
            visited[i] = -1;
        }
        for (int v = 0; v < G.V(); v++) {
            if (visited[v] == -1){
                dfs(v, cccount);
                cccount++;
            }
        }
    }
    private void dfs(int v, int ccid){
        visited[v] = ccid;
        for (int w : G.adj(v)){
            if (visited[w] == -1){
                dfs(w, ccid);
            }
        }
    }

    public int count(){
        return cccount;
    }
    // 判斷 頂點(diǎn)v 和頂點(diǎn) t是否聯(lián)通
    public boolean isConnected(int v, int t){
        G.validateVertex(v);
        G.validateVertex(t);
        return visited[v] == visited[t];
    }
    // 返回 所有聯(lián)通分量詳情
    public ArrayList<Integer>[] compnents(){
        // 將所有的聯(lián)通分量存儲(chǔ)成一個(gè)數(shù)組
        // 每一個(gè)聯(lián)通分量的值一個(gè)ArrayList
        // 一個(gè)ArrayList 存儲(chǔ)該聯(lián)通分量的所有值
        ArrayList<Integer>[] res = new ArrayList[cccount];
        // 為res初始化
        for (int i = 0; i < cccount; i++) {
            res[i] = new ArrayList<Integer>();
        }
        // 往res里面進(jìn)行值添加， 添加具體的聯(lián)通分量
        for (int v = 0; v < G.V() ; v++) {
            // visited[v] 代表第幾個(gè)聯(lián)通分量
            // 向列表中添加元素
            res[visited[v]].add(v);
        }
        return res;
    }

    public static void main(String[] args) {
        Graph graph = new Graph("g2.txt");
        CC2 cc2 = new CC2(graph);
        System.out.println(cc2.cccount);
        System.out.println(cc2.isConnected(7, 8));;
        System.out.println(cc2.isConnected(0, 5));
        // 顯示所以聯(lián)通分量
        ArrayList<Integer>[] compnents = cc2.compnents();
        for (int i = 0; i < compnents.length; i++) {
            System.out.print("第"+i+"個(gè)聯(lián)通分量" +" : ");
            for(int w: compnents[i]){
                System.out.print(w + " ");
            }
            System.out.println();
        }
    }


}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容