DFS(Depth-First Search) - 깊이 우선 탐색법

● 개념

 루트 노트에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

 - 한 방향으로 끝까지 가다가 더 이상 갈 수없게 되면 이전 갈림길로 돌아가서 다시 탐색을 진행하는 방법과 유사하다.

 - 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.

 - 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다. 

 

● 특징

 - 자기 자신은 호출하는 순환 알고리즘의 형태를 가지고 있다.

 - 전위 순회(Pre Order)를 포함한 다른 형태(In Order, Post Order)의 트리 순회는 모두 DFS의 한 종류다.

 - 특정 노드를 방문했는지 여부를 반드시 검사를 해야 한다. ( 무한루프 위험이 있음)

 

● 시간 복잡도

 - DFS는 그래프의 모든 간선을 조회한다.(정점의 수 : N, 간선의 수 : E)

   1) 인접 리스트로 표현된 그래프 : O(N+E)

   2) 인접 행렬로 표현된 그래프 : O(N^2)

 - 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는게 유리

 

● 접근 방법

 - Stack

 - Recursion(재귀)

class Graph {
	class Node {
    	int data;
        LinkedList<Node> adjacent;
        boolean marked;
        Node(int data) {
         this.data = data;
         this.marked = false;
         adjacent = new LinkedList<Node>();
        
        }
    }
    Node[] nodes;
    Graph(int size) {
    	nodes = new Node[size];
        for(int i =0; i<size; i++) {
        	nodes[i] = new Node(i);
        }
    }
    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);
    }
    void dfs() {
    	dfs(0);
    }
    void dfs(int index) {
    	Node root = nodes[index];
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        root.marked = true;
        while(!stack.isEmpty()) {
        	Node r= stack.pop();
            for(Node n : r.adjacent) {
            	if(n.marked == false) {
                	n.marked = true;
                    stack.push(n);
                }
            }
            visit(r);
        }
    }
    
    void bfs() {
    	bfs(0);
    }
    
    void bfs(int index) {
    	Node root = nodes[index];
        Queue<Node> queue = new Queue<Node>();
        queue.enqueue(root);
        root.marked = true;
        while(!queue.isEmpty()) {
        	Node r = queue.dequeue();
            for(Node n : r.adjacent) {
            	if (n.marked == false) {
                	n.marked = true;
                    queue.enqueue(n);
                }
            }
            visit(r);
        }
    }
    
    void dfsR(Node r) {
    	if(r == null) return;
        r.marked = true;
        visit(r);
        for(Node n : r.adjacent) {
        	if(n.marked == false) {
            	dfsR(n);
            }
        }
    }
    
    void dfsR(int index) {
    	Node r = nodes[index];
        dfsR(r);
    }
    
    void dfsR() {
    	dfsR(0);
    }
    
    void visit(Node n) {
    	System.out.print(n.data + " ");
    }
}
/*
    0
  /
1 -- 3     7
|  / | \  /
| /  |  5
2 -- 4   \
          6 - 8
*/
public class Test {
	public static void main(String[] args) {
    	Graph g = new Graph(9);
    	g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
        g.addEdge(3, 5);
        g.addEdge(5, 6);
        g.addEdge(5, 7);
        g.addEdge(6, 8);
        g.dfs();
        g.bfs();
        g.dfsR();
        g.dfs(3);
        g.bfs(3);
        g.dfsR(3);
        g.bfs();
    }
}