［アルゴリズム］DFS

🚀DFSについてのブログがあり、それを整理したのでリンクを切りました.
https://freestrokes.tistory.com/88
​
👀DFS/BFSアプリケーション判定を参照
「深さ優先」(DFS)と「幅優先」(BFS)を使用した問題のタイプ/適用
DFSとBFSには、それらの特性に応じて、より適切に使用されるいくつかの問題タイプがある.
1)グラフィック内のすべての頂点へのアクセスが主な問題
すべての頂点のみにアクセスするための重要な問題については、DFSとBFSの2つの方法を使用することができます.
二つの中で使いやすいものを使えばいいです.
​
2)パスフィーチャーを格納する必要がある問題
たとえば、各頂点に数字があり、aからbまでのパスが必要ですが、パスに同じ数字がない場合は、パスごとにフィーチャーを保存する必要があります.DFSを使用します.(BFSは経路の特徴を備えていない)
​
3)最短距離の問題
最も短い距離(例えば迷路を探す)を求める必要がある場合、BFSはより有利である.
深度優先検索パスを使用すると、最初に発見された答えは最短距離ではない可能性があります.
幅優先検索は、現在のノードに近い位置から始まるため、パスをナビゲートするときに最初に見つけた答えは最短距離です.
それ以外は

検索した図形が本当に大きい場合はDFSを考える

検索対象の規模が大きくなく、検索起点から遠くない場合はBFS

出典:https://devuna.tistory.com/32[図納開発日記]
​
​

👩‍💻 DFS実装-隣接行列

class dfsGraph{
    private static int nV;
    private int[][] dfsGraph;
    private boolean[] visited;
    
    public dfsGraph(int nV){
        this.nV = nV;
        this.dfsGraph = new int[nV+1][nV+1];
        this.visited = new boolean[nV+1];
    }
    
    public int[][] get(){
        return this.dfsGraph;
    }
    
    public void put(int x, int y){
        this.dfsGraph[x][y] = this.dfsGraph[y][x] = 1;
    }
    
    public void putSingle(int x, int y){
        this.dfsGraph[x][y] = 1;
    }
    
    public void printGraph(){
        for(int i=0; i<this.nV+1; i++){
            for(int j=0; j<this.nV+1; j++){
                System.out.print(this.dfsGraph[i][j] + " ");
            }
            System.out.println("");
        }
    }
    
    public void dfs(int x){
        
        if(visited[x]) return;
        
        this.visited[x] = true;
        System.out.print(x + "-");
        
        for(int i=0; i<dfsGraph.length; i++){
            if(dfsGraph[x][i]==1 && !visited[i]){
                dfs(i);
            }
        }
        
    }
    
    
}


class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int nV = 8;
        
        dfsGraph dfsGraph = new dfsGraph(nV);
        
        dfsGraph.put(1, 2);
        dfsGraph.put(1, 3);
        dfsGraph.put(2, 4);
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);
        
        dfsGraph.printGraph();
        dfsGraph.dfs(1);
        
        
        return answer;
    }
}

👩‍💻 DFS実装-隣接リスト:再帰

import java.util.ArrayList;

class DfsGraph{
    private static int nV;
    private boolean[] visited;
    private ArrayList<ArrayList<Integer>> dfsGraph;
    
    public DfsGraph(int nV){
        this.nV = nV;
        this.visited = new boolean[nV+1];
        this.dfsGraph = new ArrayList<ArrayList<Integer>>();
        
        for(int i=0; i<nV+1; i++){
            this.dfsGraph.add(new ArrayList<Integer>());
        }
    }
    
    public ArrayList<ArrayList<Integer>> getGraph(){
        return this.dfsGraph;
    }
    
    public void put(int x, int y){
        this.dfsGraph.get(x).add(y);
        this.dfsGraph.get(y).add(x);
    }
    
    public void putSingle(int x, int y){
        this.dfsGraph.get(x).add(y);
    }
    
    public void print(){
        for(int i=0; i<this.dfsGraph.size(); i++){
            System.out.print( i + "의 인접리스트 : ");
            for(int j=0; j<this.dfsGraph.get(i).size(); j++){
                System.out.print(" -> " + this.dfsGraph.get(i).get(j));
            }
            System.out.println(" ");
        }
    }
    
    public void dfs(int x){
        if(this.visited[x]) return;
        this.visited[x] = true;
        
        System.out.print(x + "-");
        
        for(int i : this.dfsGraph.get(x)){
            if(!this.visited[i]){
                dfs(i);
            }
        }
    }
    
}

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int nV = 8;
        
        DfsGraph dfsGraph = new DfsGraph(nV);
        
        dfsGraph.put(1, 2);
        dfsGraph.put(1, 3);
        dfsGraph.put(2, 4);
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);
        
        dfsGraph.print();
        
        dfsGraph.dfs(1);

        
        return answer;
    }
}

DFS実装-隣接リスト:スタック

import java.util.ArrayList;
import java.util.Stack;

class DfsGraph{
    private static int nV;
    private ArrayList<ArrayList<Integer>> dfsGraph;
    private boolean[] visited;
    
    public DfsGraph(int nV){
        this.nV = nV;
        this.dfsGraph = new ArrayList<ArrayList<Integer>>();
        this.visited = new boolean[nV+1];
        
        for(int i=0; i<nV+1; i++){
            this.dfsGraph.add(new ArrayList<Integer>());
        }
    }
    
    public ArrayList<ArrayList<Integer>> get(){
        return this.dfsGraph;
    }
    
    public void put(int x, int y){
        this.dfsGraph.get(x).add(y);
        this.dfsGraph.get(y).add(x);
    }
    
    public void putSingle(int x, int y){
        this.dfsGraph.get(x).add(y);
    }
    
    public void print(){
        for(int i=0; i<this.dfsGraph.size(); i++){
            for(int j=0; j<this.dfsGraph.get(i).size(); j++){
                System.out.print(this.dfsGraph.get(i).get(j) + " ->");
            }
            System.out.println();
        }
    }
    
    public void dfs(int x){
        Stack<Integer> st = new Stack<>();
        st.push(x);
        visited[x] = true;
        
        while(!st.isEmpty()){
            int t = st.pop();
            System.out.print(t);
            for(int i : this.dfsGraph.get(t)){
                if(!visited[i]){
                    st.push(i);
                    visited[i] = true;
                }
            }
        }
        
    }
}

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int nV = 8;
        
        DfsGraph dfsGraph = new DfsGraph(nV);
        
        dfsGraph.put(1, 2);
        dfsGraph.put(1, 3);
        dfsGraph.put(2, 4);
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);
        
        dfsGraph.print();
        
        dfsGraph.dfs(1);
        
        return answer;
    }
}