[Java] DFS , BFS 개념, 연결리스트로 구현하기

1) 그래프 탐색

그래프 탐색은 여러 정점들이 연결되어 있는 그래프가 있을때, 한 정점으로부터 시작해서 탐색하는 것을 말합니다.

ex) 한붓 그리기, 최단 경로 구하기 , 한 도시에서 다른 도시로 갈 수 있는지등에 이용됩니다.

 

그래프 Class 예시

 static class Graph {
        class Node{
        	// 정점 번호
            int data;
            // 자식 노드들
            LinkedList<Node> adjacent;
            // 방문 여부
            boolean marked;
            
            Node(int data){
                this.data = data;
                this.adjacent = new LinkedList<Node>();
                this.marked = false;
            }// constructor
        }//Node

        Node[] nodes;
        Graph(int size){
            this.nodes = new Node[size];
            for (int i = 0; i < size; i++) {
                this.nodes[i] = new Node(i);
            }
        }// constructor

        void addEdge(int i1 , int i2){
            Node n1 = nodes[i1];
            Node n2 = nodes[i2];
            if(!n1.adjacent.contains(n2)){
                n1.adjacent.add(n2);
            }
            if(!n2.adjacent.contains(n1)){
                n2.adjacent.add(n1);
            }
        }

        // Search Fuctions (Dfs & Bfs) //

        public void dfs(int index) {
        //
        }

        //DFS Recursion
        void dfsR(Node root){
        //
        }

        //BFS
        public void bfs(int index) {
		//
        }
    
        public void visit(Node n) {
            System.out.print(n.data+" ");
        }
    }//Graph

---

2) 깊이 우선 탐색(DFS)

루트 노드(정점)에 연결된 여러 분기(루트와 연결된 정점들)가 있을 것입니다.

한 분기를 탐색하고 바로 다른 분기로 넘어가는것이 아니라, 한 분기에 대해서 모든 탐색을 끝내고, 다음 분기의 탐색을 시작하는 방법입니다.

그래서 넓게가 아닌 깊게 탐색한다고 하는 것입니다. 그렇기 때문에 미로 탐색 문제 등에 어울립니다.

아래는 DFS로 탐색하는 순서입니다. 정점에 쓰여져 있는 숫자는 n번째, 즉 순서를 의미합니다.

보시면 알겠지만 루트(1번)의 첫번째 분기(2번)에 대해서 모든 정점들을 차례대로 방문한 다음에 다음 분기(7번)으로 넘어가는것을 볼수 있습니다.

---

DFS 구현

• 스택(Stack) 자료 구조를 이용해서 구현
• 재귀호출을 이용해서 구현

재귀호출 자체가 스택 형식이기 때문에 재귀호출로도 구현할수 있는 것입니다.

 

 

스택을 이용해서 구현

스택은 FILO(first in, last out) 먼저 스택에 넣은 것이 나중에 나오는 자료구조 입니다.

루트와 직접 연결된 분기들을 가장 나중에 탐색하므로 먼저 스택에 넣은후, 한 분기의 자식들을 나중에 넣어서 탐색해 줍니다. 

adjacent는 노드에 연결된 모든 자식 노드들의 연결리스트 입니다.

 public void dfs(int index) {
            Node root = nodes[index];
            Stack<Node> stack = new Stack<Node>();
            stack.push(root);
            root.marked = true;
            while (!stack.isEmpty()) {
                Node parent = stack.pop();
                for (Node child : parent.adjacent) {
                    if (!child.marked) {
                        child.marked = true;
                        stack.push(child);
                    }
                }//for
                visit(parent);
            }//while
        }

 

재귀호출을 이용해서 구현

루트의 탐색을 시작하면, 한 분기의 탐색을 호출하고, 한분기의 자식에 대해서 호출하는 방법입니다.

void dfsR(Node root){
            root.marked = true;
            visit(root);
            for (Node n : root.adjacent) {
                if (n.marked == false) {
                    dfsR(n);
                }
            }
        }

---

3) 너비 우선 탐색(BFS)

루트 노드에 바로 직접 인접한 분기들 먼저 전부 방문하고, 분기들의 직속 자식 노드들을 방문하는 방법입니다.

그래서 넓게 방문한다고 불립니다.

가장 인접한 노드들을 최우선적으로 방문하기 때문에 최단거리 구하는 문제에 적합합니다.

아래는 DFS로 탐색하는 순서입니다. 정점에 쓰여져 있는 숫자는 n번째, 즉 순서를 의미합니다.

 

BFS 구현

너비 후선 탐색은 큐로 구현할수 있습니다. 큐는 FIFO(First in, First out) 먼저 넣어준것을 먼저 출력하는 자료구조를 가지고 있습니다.

루트 노드에 가장 가까이 인접한 노드들을 먼저 입력해서 가장 인접한 노드들을 우선적으로 탐색합니다.

adjacent는 노드에 연결된 모든 자식 노드들의 연결리스트 입니다.

 public void bfs(int index) {
            Node root = nodes[index];
            Queue<Node> queue = new LinkedList<Node>();
            queue.add(root);
            root.marked = true;
            while (!queue.isEmpty()) {
                Node parent = queue.poll();
                for (Node child : parent.adjacent) {
                    if (!child.marked) {
                        child.marked = true;
                        queue.add(child);
                    }
                }//for
                visit(parent);
            }//while
        }

---

4) 전체 코드

보여주는 코드들은 하나의 구현 '예시'입니다.

알고리즘이나 백준 문제를 풀때 당연히 그 조건에 맞게 코드를 짜야되고, 이 코드를 그대로 복사해서 쓰면 안됩니다.

 

문제의 상황에 맞게 DFS , BFS탐색하는 '아이디어'만 그대로 가져와서 스스로 문제에 맞게 다르게 구현하시기 바랍니다.

(예를 들어 BFS는 큐로 구현하되, 구현은 문제에 맞게 다른게 구현!)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;


public class DfsBfs_LinkedList {
    // Inner Class needs static
    static class Graph {
        class Node{
            int data;
            LinkedList<Node> adjacent;
            boolean marked;
            Node(int data){
                this.data = data;
                this.adjacent = new LinkedList<Node>();
                this.marked = false;
            }// constructor
        }//Node

        Node[] nodes;
        Graph(int size){
            this.nodes = new Node[size];
            for (int i = 0; i < size; i++) {
                this.nodes[i] = new Node(i);
            }
        }// constructor

        void addEdge(int i1 , int i2){
            Node n1 = nodes[i1];
            Node n2 = nodes[i2];
            if(!n1.adjacent.contains(n2)){
                n1.adjacent.add(n2);
            }
            if(!n2.adjacent.contains(n1)){
                n2.adjacent.add(n1);
            }
        }

        // Search Fuctions (Dfs & Bfs) //

        //DFS
        public void dfs() {
            dfs(0);
        }
        public void dfs(int index) {
            Node root = nodes[index];
            Stack<Node> stack = new Stack<Node>();
            stack.push(root);
            root.marked = true;
            while (!stack.isEmpty()) {
                Node parent = stack.pop();
                for (Node child : parent.adjacent) {
                    if (!child.marked) {
                        child.marked = true;
                        stack.push(child);
                    }
                }//for
                visit(parent);
            }//while
        }

        //DFS Recursion
        void dfsR(Node root){
            root.marked = true;
            visit(root);
            for (Node n : root.adjacent) {
                if (n.marked == false) {
                    dfsR(n);
                }
            }
        }

        //BFS
        public void bfs() {
            bfs(0);
        }
        public void bfs(int index) {
            Node root = nodes[index];
            Queue<Node> queue = new LinkedList<Node>();
            queue.add(root);
            root.marked = true;
            while (!queue.isEmpty()) {
                Node parent = queue.poll();
                for (Node child : parent.adjacent) {
                    if (!child.marked) {
                        child.marked = true;
                        queue.add(child);
                    }
                }//for
                visit(parent);
            }//while
        }
    
        public void visit(Node n) {
            System.out.print(n.data+" ");
        }
    }//Graph


    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int numberOfNodes = scan.nextInt();
        int numberOfEdges = scan.nextInt();
        int start = scan.nextInt();
        Graph graph = new Graph(numberOfNodes);

        for (int i = 0; i < numberOfEdges; i++) {
            graph.addEdge(scan.nextInt(), scan.nextInt());
        }
        graph.dfs(start); //startIndex = start - 1
        graph.dfsR(graph.nodes[start]);
        scan.close();
    }
}