图的深度优先遍历

作者: __method__ | 来源:发表于2020-11-05 20:01 被阅读0次

图的深度优先遍历和马踏棋盘算法
数据结构与算法学习-图的遍历
哈夫曼实现图：十字链表，邻接多重链表，邻接表（无向），邻接表
图的DFS && BFS遍历
搜索
数据结构—图的遍历
图的遍历
基本数据结构
无向图DFS和BFS
数据结构之图的遍历-深度优先搜索(DFS)和广度优先搜索(BFS

数据结构遍历的意义

树的遍历

图的遍历

树的前序遍历

图遍历和树遍历区别

知识回顾

树的深度优先遍历

普通函数和递归函数调用的区别

图的深度优先遍历的过程

初始visited数组都是fasle，当从顶点0开始调用时，如果没有被遍历，那么遍历结果列表中添加这个顶点，然后开始for循环，执行dfs(1)

Java实现图的DFS
g.txt


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


/// 暂时只支持无向无权图
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;
    // 该节点是否被遍历
    private boolean[] visited;
    // 每个顶点被遍历到的顺序
    private ArrayList<Integer> order = new ArrayList<>();

    // 定义构造函数，直接在构造函数中执行 dfs
    public GrahDFS(Graph G){
        // 初始化 图
        this.G = G;
        // 初始化 是否被遍历过的数组，长度和顶点个数一样
        // 默认false也就是没有被遍历过
        visited = new boolean[G.V()];
        System.out.println(Arrays.toString(visited));
        // 直接从顶点0 开始进 dfs
        dfs(0);

    }

    public void dfs(int v){
        System.out.println("开始深度优先遍历"+v+"顶点");
        // 能进入这里说明v顶点接下来要被遍历了
        visited[v] = true;
        // 向记录顶点遍历顺序的 order列表中添加此顶点
        order.add(v);
        // 遍历这个顶点所有的邻接顶点
        for(int w : G.adj(v)){
            // 每次w代表 和v相邻顶点中的一个
            // 如果这个顶点没有被遍历过， 继续调用该顶点的深度优先
            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的改进

如果是如下的图结构

对应的txt

执行dfs之后我们发现顶点5并没有被遍历，这是因为我们dfs是从0开始的
只调用一次， 5和其他顶点并没有联通，所以应该执行dfs(5)

求联通分量的个数

CC.java

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

import java.util.Arrays;

/**
 * 求解联通分量的个数
 */
public class CC {
    // 定义表示
    private Graph G;
    // 定义是否被遍历数组
    private int[] visited;
    // 定义一个计数变量，统计联通分量的个数
    private int cccount = 0;
    // 构造函数
    public CC(Graph G){
        this.G = G;
        // 初始化布尔数组的值
        visited = new int[G.V()];
        // 默认将数组中所有值变成 -1， 代表没有被遍历过
        for (int i = 0; i < visited.length; i++) {
            visited[i] = -1;
        }
        System.out.println("visited初始值");
        System.out.println(Arrays.toString(visited));
        // 循环调用 每个顶点的dfs
        for (int v = 0; v < G.V() ; v++) {
            if (visited[v] == -1){
                dfs(v, cccount);
                cccount ++;
            }
        }
    }
    // 深度优先过程
    public void dfs(int v, int ccid){
        // 使用ccid表示是否被遍历过,
        // 只要不是-1证明已经被遍历过，
        // 具体ccid的值实际代表的是所属第几个联通分量
        visited[v] = ccid;
        // 遍历顶点v所有相邻顶点
        for (int w :G.adj(v)){
            // visited[w]是 -1 代表w顶点没有被遍历过，要继续进行dfs
            if (visited[w] == -1){
                dfs(w,ccid);
            }
        }
    }
    // 编写专门 统计联通分量个数的方法
    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

联通分量的改进，列出所有的联通分量详情

CC2.java

package com.duanxuehan.liantongfenliang06;

import com.duanxuehan.dfs05.Graph;

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

// 联通分量的改进，列出所有的联通分量详情
public class CC2 {
    // 定义图表示
    private Graph G;
    // 定义是否被遍历数组
    private int[] visited;
    // 定义一个计数变量，统计联通分量的个数
    private int cccount = 0;
    // 构造函数
    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;
    }
    // 判断 顶点v 和顶点 t是否联通
    public boolean isConnected(int v, int t){
        G.validateVertex(v);
        G.validateVertex(t);
        return visited[v] == visited[t];
    }
    // 返回 所有联通分量详情
    public ArrayList<Integer>[] compnents(){
        // 将所有的联通分量存储成一个数组
        // 每一个联通分量的值一个ArrayList
        // 一个ArrayList 存储该联通分量的所有值
        ArrayList<Integer>[] res = new ArrayList[cccount];
        // 为res初始化
        for (int i = 0; i < cccount; i++) {
            res[i] = new ArrayList<Integer>();
        }
        // 往res里面进行值添加， 添加具体的联通分量
        for (int v = 0; v < G.V() ; v++) {
            // visited[v] 代表第几个联通分量
            // 向列表中添加元素
            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));
        // 显示所以联通分量
        ArrayList<Integer>[] compnents = cc2.compnents();
        for (int i = 0; i < compnents.length; i++) {
            System.out.print("第"+i+"个联通分量" +" : ");
            for(int w: compnents[i]){
                System.out.print(w + " ");
            }
            System.out.println();
        }
    }


}

图的深度优先遍历和马踏棋盘算法
图的深度优先遍历思想图的遍历通常有两种遍历次序方案: 深度优先遍历和广度优先遍历。深度优先遍历（DepthFir...
数据结构与算法学习-图的遍历
图的遍历可以分为：深度优先遍历和广度优先遍历一、深度优先遍历深度优先遍历的实现思路将图的顶点和边信息输⼊入到...
哈夫曼实现图：十字链表，邻接多重链表，邻接表（无向），邻接表
图的遍历：无论是广度优先，还是深度优先都是以箭头方向右边的优先遍历；广度优先遍历（无向图）：深度优先（无向图...
图的DFS && BFS遍历
对图的深度优先遍历：对图的广度优先遍历：
搜索
一、深度优先搜索图深度优先遍历、深度优先搜索算法求有权图两点最短路径二、广度优先搜索图广度优先遍历、广度优先...
数据结构—图的遍历
根据图的存储方式可分为邻接矩阵的深度优先遍历和邻接表的深度优先遍历。一、深度优先遍历 1、邻接矩阵的深度优先遍历...
图的遍历
1.前言对于图的遍历来说通常有两种遍历次序，它们是深度优先遍历和广度优先遍历 2.深度优先遍历深度优先遍历（D...
基本数据结构
一.图二.树一.图 1.图的遍历：通过深度优先遍历DFS和广度优先遍历BFS两种方式。深度优先遍历0 1 2 ...
无向图DFS和BFS
基本结构 DFS深度优先遍历 BFS广度优先遍历符号图
数据结构之图的遍历-深度优先搜索(DFS)和广度优先搜索(BFS
两种遍历图的遍历分为深度优先搜索(Depth First Search)和广度优先搜索深度优先搜索(DFS) ...