[알고리즘] 02. DFS & BFS

DFS는 모든 친구 관계를 살펴보며, BFS는 A와 가까운 친구부터 살펴본다

Depth First Search

DFS

깊이 우선 탐색
: 임의의 노드에서 시작해, 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다

: Stack과 Recursive으로 구현할 수 있으며, Tree Traversal이 DFS의 종류에 속한다

 

• 모든 노드를 방문하고자 할 때
• 백트래킹, 미로찾기
• 트리의 깊이가 매우 크거나, 무한대가 될 때는 사용 X

 

DFS with Stack

public class DFS_stack {
    private int numOfVertex;
    private boolean[] visited;
    private LinkedList<Integer>[] headOfAdjacencyList;

    public DFS_stack(int numOfVertex) {
        this.numOfVertex = numOfVertex;
        this.visited = new boolean[numOfVertex];
        this.headOfAdjacencyList = new LinkedList[numOfVertex];
        for (int i = 0; i < numOfVertex; i++)
            headOfAdjacencyList[i] = new LinkedList<>();
    }

    public void push(int tail, int head) {
        headOfAdjacencyList[tail].add(head);
    }

    private void DFS(int start) {
        Stack<Integer> stack = new Stack<>();
        visited[start] = true;
        stack.push(start);

        while (!stack.isEmpty()) {
            int target = stack.peek();
            Iterator<Integer> e = headOfAdjacencyList[target].iterator();
            while (e.hasNext()) {
                int value = e.next();
                if (!visited[value]) {
                    this.visited[value] = true;
                    stack.push(value);
                    break;
                }
            }
            if (!e.hasNext()) stack.pop();
        }
    }
}

 

DFS with Recursive

public class DFS_recursive {
    private int numOfVertex;
    private boolean[] visited;
    private LinkedList<Integer>[] headOfAdjacencyList;

    public DFS_recursive(int numOfVertex) {
        this.numOfVertex = numOfVertex;
        this.visited = new boolean[numOfVertex];
        this.headOfAdjacencyList = new LinkedList[numOfVertex];
        for (int i = 0; i < numOfVertex; i++)
            headOfAdjacencyList[i] = new LinkedList<>();
    }

    public void push(int tail, int head) {
        headOfAdjacencyList[tail].add(head);
    }

    private void DFS(int start) {
        visited[start] = true;
        Iterator<Integer> e = headOfAdjacencyList[start].iterator();

        while(e.hasNext()) {
            int target = e.next();
            if (!visited[target])
                DFS(target);
        }
    }
}

 

---

Breadth First Search

BFS

너비 우선 탐색
: 임의의 노드에서 시작해, 인접한 노드를 먼저 탐색하는 방법이다

: Queue로 구현한다

 

• 두 노드사이의 최단 경로, 임의의 경로를 찾고 싶을 때
• 간선의 가중치가 같은 경우, 최단 경로를 구할 때
• 간선의 가중치가 다른 경우, 최단 경로를 구할 때 (= 다익스트라 알고리즘)
• 지구상의 모든 친구 관계를 그래프로 표현한 후, A와 B 사이에 존재하는 경로를 찾고 싶을 때

 

BFS with Queue

public class BFS_queue {

    private int numOfVertex;
    private boolean[] visited;
    private LinkedList<Integer>[] headOfAdjacencyList;

    public BFS_queue(int numOfVertex) {
        this.numOfVertex = numOfVertex;
        this.visited = new boolean[numOfVertex];
        this.headOfAdjacencyList = new LinkedList[numOfVertex];
        for (int i = 0; i < numOfVertex; i++)
            headOfAdjacencyList[i] = new LinkedList<>();
    }

    public void push(int tail, int head) {
        headOfAdjacencyList[tail].add(head);
    }

    private void BFS(int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);

        while (!queue.isEmpty()) {
            int target = queue.poll();
            Iterator<Integer> e = headOfAdjacencyList[target].iterator();
            while (e.hasNext()) {
                int element = e.next();
                if (!visited[target]) {
                    queue.offer(element);
                    visited[target] = true;
                }
            }
        }
    }
}

---

Time Complexity

	Adjacency List	Adjacency Matrix
DFS	O(V+E)	O(V^2)
BFS	O(V+E)	O(V^2)

하지만 단순 검색에 있어서는, BFS가 더 빠르다!

 

---

 

GitHub - Sinyoung3016/sophomore-lecture: 2020년 충남대학교 컴퓨터융합학부 2학년 때의 과제들을 모아모아