📌 그래프 탐색

하나의 정점으로부터 시작하여 차례대료 모든 정점들을 한 번씩 방문하는 것

💻 깊이 우선 탐색(DFS, Depth First Search)

루트 노드 혹은 다른 임의의 노드에서 시작해서 다음 분기(branch) 로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법. 즉, 넓게 탐색하기 전에 깊게 탐색하는 방법이다.

➕ 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
• 전위 순회(Pre-Order Traversals) 를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 이 알고리즘을 구현하는데 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
• 깊이 우선 탐색(DFS) 는 너비 우선 탐색(BFS) 보다 좀 더 간단하지만, 검색 속도 자체는 너비 우선 탐색에 비해서 느리다.

➕ 과정

➕ 구현

Node 와 Graph

import java.util.ArrayList;
import java.util.List;

public class Graph {

    private Node rootNode;

    public Graph(Node rootNode){
        this.rootNode = rootNode;
    }

    public void dfs(){
        this.dfs(rootNode);
    }

    public void dfs(Node rootNode){
        System.out.println(rootNode.getNumber() + "번 노드 방문시작");

        List<Node> nodes = rootNode.getNodes();
        for(Node node : nodes){
            if(!node.isVisited()){
                node.setVisited(true);
                dfs(node);
            }
        }
        System.out.println(rootNode.getNumber() + "번 노드 방문완료");
    }

}

class Node {

    private int number;
    private boolean visited;
    private List<Node> nodes;

    public Node(int number){
        this.number = number;
        this.visited = false;
        this.nodes = new ArrayList<>();
    }

    public boolean isVisited(){
        return this.visited;
    }

    public void setVisited(boolean visited){
        this.visited = visited;
    }

    public int getNumber(){
        return this.number;
    }

    public List<Node> getNodes(){
        return this.nodes;
    }
}

DFS 사용

public class Main {

    public static void main(String[] args) {
        Node rootNode = initRootNode();
        Graph dfsGraph = new Graph(rootNode);
        dfsGraph.dfs();
    }

    private static Node initRootNode() {
        Node rootNode = new Node(1);

        Node subNode2 = new Node(2);
        Node subNode3 = new Node(3);
        Node subNode4 = new Node(4);
        Node subNode5 = new Node(5);

        Node subSubNode6 = new Node(6);
        Node subSubNode7 = new Node(7);
        Node subSubNode8 = new Node(8);
        Node subSubNode9 = new Node(9);

        Node subSubSubNode10 = new Node(10);
        Node subSubSubNode11 = new Node(11);
        Node subSubSubNode12 = new Node(12);

        subSubNode6.getNodes().add(subSubSubNode10);
        subSubNode6.getNodes().add(subSubSubNode11);
        subSubNode7.getNodes().add(subSubSubNode12);

        subNode2.getNodes().add(subSubNode6);
        subNode2.getNodes().add(subSubNode7);
        subNode3.getNodes().add(subSubNode8);
        subNode5.getNodes().add(subSubNode9);

        rootNode.getNodes().add(subNode2);
        rootNode.getNodes().add(subNode3);
        rootNode.getNodes().add(subNode4);
        rootNode.getNodes().add(subNode5);

        return rootNode;
    }
}

출력 결과

1번 노드 방문시작
2번 노드 방문시작
6번 노드 방문시작
10번 노드 방문시작
10번 노드 방문완료
11번 노드 방문시작
11번 노드 방문완료
6번 노드 방문완료
7번 노드 방문시작
12번 노드 방문시작
12번 노드 방문완료
7번 노드 방문완료
2번 노드 방문완료
3번 노드 방문시작
8번 노드 방문시작
8번 노드 방문완료
3번 노드 방문완료
4번 노드 방문시작
4번 노드 방문완료
5번 노드 방문시작
9번 노드 방문시작
9번 노드 방문완료
5번 노드 방문완료
1번 노드 방문완료

Process finished with exit code 0

📖 REFERENCE

➕ 깊이 우선 탐색(DFS)이란 (https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html)