게시글

강좌21 - Algorithm - 5년 전 등록 / 일 년 전 수정

그래프 탐색

DFS(깊이 우선)와 BFS(너비 우선)

안녕하세요. 이번 시간에는 그래프를 탐색하는 두 가지 방법인 DFS와 BFS에 대해 알아보겠습니다!

그래프 탐색은 그래프 안에 어떤 버텍스들이 있는지 알고 싶을 때 사용합니다. DFS는 버텍스의 자식들을 먼저 탐색하고, BFS는 버텍스의 형제들을 먼저 탐색합니다. 무슨 소리인지 잘 모르겠죠? 아래의 예시를 보시죠.

들어가기에 앞서

댓글에서 많은 논쟁이 있었는데요. 우선 제 블로그 포스팅은 틀린 점이 없다는 것을 알려드립니다. 다만 여러분들이 오해하는 것(또는 저와 생각이 다를 수 있는 것) 두 가지를 알려드립니다.

첫 번째 오해는 제 포스트를 트리의 DFS라고 생각하는 것입니다. 그래프의 DFS와 트리의 DFS는 다를 수 있습니다. 트리는 보통 끝점이 명확하므로 끝까지 파고들 수 있지만, 그래프에서는 끝점이 명확하지 않은 경우가 많아 어느 순간에 탐색을 멈출지를 정해야 합니다.

여기서 두 번째 오해가 나옵니다. 알고리즘이 하나라고 생각하실 수 있지만, 그래프의 경우는 어느 순간에 멈추느냐에 따라 다양한 알고리즘이 나올 수 있습니다. 제가 선택한 것은 무작정 끝까지 달리는 것도 아니고 하나의 숫자로 정해진 뎁스까지 가는 것도 아니고 스택에 이미 들어있는 요소를 만날 때까지 달리는 것입니다.

이렇게 가정하면 오해가 없으실 것이라 생각되네요. 대학생분들이 많이 찾아오시는 것으로 보이는데 제가 정한 기준과 다른 DFS를 구현하시고 싶으시면 다른 블로그를 찾아가세요.

DFS

Depth First Search의 약자로 깊이 우선 탐색을 뜻합니다. 버텍스의 자식들을 우선으로 탐색한다고 설명했는데 다음과 같은 경우입니다.

undefined

버텍스 옆의 숫자는 탐색 순서입니다. A, X 다음에 G, H 선택지가 두 개가 있는데 G와 H를 고른 후(스택에 넣은 후), G는 내버려두고 H의 자식들로 이동합니다. 형제보다는 자식을 우선 탐색하는 겁니다. 모든 자식을 탐색한 후에 이제 스택에 넣어뒀던 형제를 탐색합니다.

그래프는 트리와는 다르게 아크 관계가 얽혀 있어서 누가 부모고 누가 자식인지 쉽게 구별하기 힘듭니다. 이럴 때는 시작점(A)와의 최단거리를 보면 됩니다. X는 A로부터의 거리가 1입니다. G와 H는 A로부터의 거리가 2입니다. 따라서 G와 H는 X의 자식이 됩니다. P와 E는 A로부터의 거리가 3이 됩니다. 따라서 G 또는 H의 자식이 됩니다. 누구의 자식이 될 것인가는 아크 배치 순서에 따라 다릅니다. 저는 P와 E 모두 H의 자식으로 두었습니다.

코드로 볼까요? 스택 코드그래프 코드 를 재사용합니다. 혹시 스택을 까먹으신건 아니죠? 그렇다면 다시 보고 오세요!

이번 시간에는 지난 시간들과는 예시가 좀 달라졌습니다. 잠시 예시를 먼저 만들어볼까요? 이 예시는 아래 BFS에서도 그대로 사용됩니다.

var graph = new Graph();
graph.insertVertex('A');
graph.insertVertex('X');
graph.insertVertex('G');
graph.insertVertex('H');
graph.insertVertex('P');
graph.insertVertex('E');
graph.insertVertex('Y');
graph.insertVertex('M');
graph.insertVertex('J');
insertTwoWayArc(graph, 1, 'A', 'X');
insertTwoWayArc(graph, 1, 'X', 'G');
insertTwoWayArc(graph, 1, 'X', 'H');
insertTwoWayArc(graph, 1, 'G', 'H');
insertTwoWayArc(graph, 1, 'G', 'P');
insertTwoWayArc(graph, 1, 'H', 'E');
insertTwoWayArc(graph, 1, 'H', 'P');
insertTwoWayArc(graph, 1, 'E', 'M');
insertTwoWayArc(graph, 1, 'E', 'Y');
insertTwoWayArc(graph, 1, 'Y', 'M');
insertTwoWayArc(graph, 1, 'M', 'J');

이제 DFS 코드입니다.

Graph.prototype.dfs = function() {
  var stack = new Stack();
  var temp = this.first;
  while (temp) {
    temp.inTree = false;
    temp = temp.next;
  }
  temp = this.first;
  stack.push(temp); // 스택에 첫 버텍스를 넣음
  temp.inTree = true;
  while (stack.count) { // 탐색을 완료할 때까지
    temp = stack.pop(); // 넣었던 버텍스를 하나씩 꺼냄
    console.log(temp.key);
    temp.inTree = true;
    var arc = temp.arc;
    while (arc) {
      if (!arc.destination.inTree) {
        stack.push(arc.destination); // 꺼낸 것과 연결된 버텍스들을 스택에 넣음
        arc.destination.inTree = true;
      }
      arc = arc.nextArc;
    }
  }
};
graph.dfs(); // A, X, H, P, E, Y, M, J, G

inTree 속성을 사용했는데, 정확히는 inTree라고 이름붙인 게 옳지는 않습니다. 그냥 새로운 속성을 주기 귀찮아서 지난 시간의 inTree 속성을 재사용했습니다. 결과는 위의 그림이랑 순서가 같죠?

BFS

Breadth First Search의 약자로 너비 우선 탐색을 뜻합니다. 버텍스의 형제들을 우선으로 탐색한다고 설명했는데 다음과 같은 경우입니다.

undefined

아까는 G는 내버려두고 H의 자식들로 갔다면, 이번에는 G부터 처리하고, H를 처리한 후 H의 자식으로 이동합니다. 즉 형제들을 먼저 처리하는 거죠. 다익스트라 알고리즘에서 모든 아크들의 가중치가 1인 경우와 유사합니다.

코드로 볼까요? 큐 코드그래프 코드 를 재사용합니다. 큐를 까먹으셨다면 다시 보고 오세요!

Graph.prototype.bfs = function() {
  var queue = new Queue();
  var temp = this.first;
  while (temp) {
    temp.inTree = false;
    temp = temp.next;
  }
  temp = this.first;
  queue.enqueue(temp); // 첫 버텍스를 큐에 넣음
  temp.inTree = true;
  while (queue.count) { // 탐색을 완료할 때까지
    temp = queue.dequeue(); // 큐에서 하나씩 꺼냄
    console.log(temp.key);
    temp.inTree = true;
    var arc = temp.arc;
    while (arc) {
      if (!arc.destination.inTree) {
        queue.enqueue(arc.destination); // 꺼낸 것과 연결된 버텍스들을 큐에 넣음
        arc.destination.inTree = true;
      }
      arc = arc.nextArc;
    }
  }
};
graph.bfs(); // A, X, G, H, P, E, M, Y, J

BFS도 위의 사진과 같이 동작하죠? DFS가 스택의 특징(LIFO)에 의해 자동으로 깊이 우선 탐색이 되는 반면, BFS는 큐의 특징(FIFO) 때문에 자동으로 너비 우선 탐색이 됩니다.

다음 시간에는 마지막으로 네트워크 플로우에 대해 알아보겠습니다!

조회수:
0
목록
투표로 게시글에 관해 피드백을 해주시면 게시글 수정 시 반영됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright 2016- . 무단 전재 및 재배포 금지. 출처 표기 시 인용 가능.

댓글

14개의 댓글이 있습니다.
일 년 전
그래프이론의 dfs와 많이 다르네요. 댓글에 링크올리신 unlv교수님과도 코드랑 결과가 달라요. 아랫분 말씀대로 bfs와 dfs의 혼합인거 같습니다. 그리고 이유없이 중간에 탐색을 중단하고 다른 가지로 갈아타는 dfs가 있었나요? 그래프 이론에는 없는것 같습니다.
10달 전
이유가 없다는게 무슨 말씀이신지 모르겠네요. 글에 이유를 적어두었습니다. 그래프 dfs는 이유가 있다면 다른 가지로 갈아타는 경우가 많습니다.
3년 전
흐미.. 안 하던 사람이 하려니 어렵네요...BFS에서 X의 자식이 G랑 H가 있는거잖아요.. 그럼 A X G H에서 A X H G로 해도 되는 건가요? 만약 그렇게 된다면 A X G H E M Y J P가 될 수 있나요?
3년 전
네 순서를 바꿔서 할 수도 있습니다. 그런데 E와 P가 형제이기 때문에 같이 처리해주어야 합니다. A X G H E M Y J P는 E와 P가 떨어져있어 안 됩니다.
3년 전
안녕하세요, 코드 잘 보고 있습니다. DFS부분에서 탐색순서를 A-X-H-P 로 진행했다면 그 다음 탐색 순서는 E가 아니라 G가 되어야 하는 것 아닌가요? 작성해주신 알고리즘에 대해 이야기 하는 것이 아니라, DFS의 개념을 생각했을 때요!
3년 전
E든 G든 상관없습니다. 둘 다 DFS입니다. 누구를 누구의 자식으로 볼 건가의 차이입니다.
3년 전
빠른 답변 감사합니다. P와 G 사이에 엣지가 존재하는데, G를 P의 자식 노드로 보지않을 수 있나요..?
3년 전
G는 H 또는 X의 자식으로 여겨지는 경우입니다.
4년 전
DFS에서 저와 다르게 스택을 사용하고 있는 것 같아서 문의를 드립니다..
제가 알고 있는 DFS의 스택은 정점의 인접한 정점을 담는 것이 아니라
방문한 정점의 순서를 스택으로 넣어서 관리하는 형태인데요..
글로 설명을 잘 못할 것 같아서 한번 차근차근 정리해보았습니다.
먼저 소스에서 간선을 그린 순서를 정리해보면
1. A-X
2. X-G
3. X-H
4. G-H
5. G-P
6. H-E
7. H-P
8. E-M
9. E-Y
10. M-Y
11. M-J
입니다.
인접한 정점의 탐색은 큐형태로 하던 스택형태로하던 상관 없으나 일단 큐형태로 진행하여 설명해보겠습니다.
탐색하는 정점이 첫 방문일 때는 스택에 넣고, 재방문 시 방문하지 않은 인접한 정점이 없을 때는 스택을 빼도록 하겠습니다.
탐색은 A부터 진행한다면
1. 첫번째 탐색은 A이고 스택에 A를 넣습니다.
순서 : A
스택 : A
2. A에 인접한 정점은 X이므로 X를 탐색하고 스택에 X를 넣습니다.
순서 : A X
스택 : A X
3. X에 인접한 정점은 G, H(방문한 정점 A는 제외하겠습니다)인데 먼저 연결된 G로 탐색을 하고 스택에 G를 넣습니다.
순서 : A X G
스택 : A X G
4. G에 인접한 정점은 H, P인데 먼저 연결된 H로 탐색을 하고 스택에 H를 넣습니다.
순서 : A X G H
스택 : A X G H
5. H에 인접한 정점은 P, E인데 먼저 연결된 E로 탐색을 하고 스택에 E를 넣습니다.
순서 : A X G H E
스택 : A X G H E
6. E에 인접한 정점은 M, Y인데 먼저 연결된 M으로 탐색을 하고 스택에 M을 넣습니다.
순서 : A X G H E M
스택 : A X G H E M
7. M에 인접한 정점은 Y, J인데 먼저 연결된 Y로 탐색을 하고 스택에 Y를 넣습니다.
순서 : A X G H E M Y
스택 : A X G H E M Y
8. Y에 인접한 정점이 없으므로 스택에서 J를 제외하고 다음 스택값을 탐색하겠습니다.
순서 : A X G H E M Y
스택 : A X G H E M
9. M에 인접한 정점은 J 하나 남았으므로 J를 탐색하고 스택에 J를 넣습니다.
순서 : A X G H E M Y J
스택 : A X G H E M J
10. J에 인접한 정점이 없으므로 스택에서 제외하고 다음 M으로 탐색합니다.
순서 : A X G H E M Y J
스택 : A X G H E M
11. M은 위에서 확인한 것 처럼 인접한 정점이 없으니 스택에서 제외하고 다음 E로 탐색합니다.
순서 : A X G H E M Y J
스택 : A X G H E
12. E는 더이상 인접한 정점이 없으니 스택에서 제외하고 다음 H로 탐색합니다.
순서 : A X G H E M Y J
스택 : A X G H
13. H에 인접한 정점은 P 하나 남았으므로 P를 탐색하고 스택에 P를 넣습니다.
순서 : A X G H E M Y J P
스택 : A X G H P
14. P는 더이상 인접한 정점이 없으니 스택에서 제외하고 다음 H로 탐색합니다.
순서 : A X G H E M Y J P
스택 : A X G H
15. H는 더이상 인접한 정점이 없으니 스택에서 제외하고 다음 G로 탐색합니다.
순서 : A X G H E M Y J P
스택 : A X G
16. G는 더이상 인접한 정점이 없으니 스택에서 제외하고 다음 X로 탐색합니다.
순서 : A X G H E M Y J P
스택 : A X
17. X는 더이상 인접한 정점이 없으니 스택에서 제외하고 다음 X로 탐색합니다.
순서 : A X G H E M Y J P
스택 : A
18. A는 더이상 인접한 정점이 없으니 스택에서 제외하고 더이상 스택에 남은 값이 없으므로 탐색을 종료합니다.
순서 : A X G H E M Y J P
스택 :
물론 인접 정점을 검색하는 방식을 큐형태에서 스택형태로 바꾸면 순서는 A X H P G E Y M J로 나옵니다.
제가 아는 DFS의 스택 사용은 위와 같은데 제로초님께서 말씀하시는 방식으로 스택을 사용하여도 문제가 없는 것인지 궁금합니다.
4년 전
헉, 이렇게 상세하게 설명하실 줄 몰랐네요. 결론부터 말씀드리자면 둘 다 맞습니다. 처음 달라지는 부분이 H나 G나 여기서 시작하는데요. 그래프를 어떻게 트리로 변환하느냐에서 차이가 있는 것입니다. G H 순으로 나오는 것은 H를 G의 자식으로 본거고, H가 먼저 나오는 것은 H랑 G를 형제로 본 것입니다.
4년 전
그리고 저는 제 방식이 더 직관적인 것 같은게, 질문자분의 방식에서는 왜 18단계나 거쳐야 하는지 잘 이해가 되지 않네요.
4년 전
저도 제로쵸님의 방식이 더 직관적인 것 같긴합니다.
다만 제가 의문스러운 것은 알고리즘이란 것이 동일 인풋의 동일 아웃풋이라는 단순한 정의로 살펴본다면..
동일한 인풋에 내부 구현방식에 따라 다양한 아웃풋이 나온 다는 점에서 알고리즘의 하나의 원칙이라고 생각했던 부분 동일 인풋 동일 아웃풋이 손상된다는 점입니다 ㅠㅠ;
다수의 책과 블로거들의 글들을 보면 대부분은 위에 불필요한 18단계를 사용하고 있다는 점에서 정확한 DFS의 정의는 무엇인지 생각을 하게 됩니다... 이래서 또 저의 숙제가 하나 늘었네요 ㅎㅎ;; 근데 답변을 엄청 빨리 달아주시네요! 나름 포인트있는 컨텐츠만 잘 정리해서 개시하시고 운영도 잘하시는 것 같아서 많은 도움을 받고 갑니다.
4년 전
동일 인풋과 동일 아웃풋이 알고리즘의 조건인 건 맞습니다. 그런데 하나 놓치신 게 있습니다. DFS 알고리즘이 하나가 아니라는 겁니다. 저희 둘의 알고리즘은 이름만 같고 다른 알고리즘입니다. 세상에 제로초란 이름을 가진 사람이 둘이라고 해서 같은 사람이 아닌 것 처럼요.
4년 전
엄밀하게 따지면 DFS는 로직이 하나로 정해진 알고리즘이라기 보다는 방법론에 더 가깝다는 게 제 의견입니다.
4년 전
오 저와 같은 생각을 말씀하시네요. 알고리즘이라고 하기 보다는 방법론에 더 가깝다고 생각이 들었습니다.
답변 매우 감사합니다.
4년 전
정리해보자면// () : 권장
트리 최단거리 탐색 - (BFS), DFS, 다익스트라
비가중치 최단거리 탐색 - (BFS), 다익스트라
가중치 최단거리 탐색 - (다익스트라), (마샬 플로이드)
이렇게 정리해두는게 맞을까요?
4년 전
마지막으로 왜 비가중치, 가중치 그래프에서는 최단거리 탐색 시 dfs를 사용할 수 없는지도 궁금합니다. 위에서 dfs 예시에서와 같이 가중치 그래프 역시 완전탐색을 통해서 최단거리를 구할 수 있지 않나요? 안된다는 말은 많은데 간혹가다가 된다고 정리해두신 분들도 있어서 헷갈리네요.
4년 전
완전탐색을 하면 가능하긴 하겠는데 그게 dfs만을 사용했다고 표현할 수 있는지가 논란의 여지가 될 수 있을 것 같습니다. 거의 브루트포스 수준 아닌가요?
4년 전
반면에 트리를 포함하는 개념인 그래프의 경우에는 'dfs와 bfs로 탐색은 가능하지만 비가중치 그래프에서는 bfs로만 최단거리를 구할 수 있고, 가중치 그래프의 경우에는 다익스트라나 마샬을 이용해야된다'고 알고 있는데 맞나요? 여기서 '다익스트라를 비가중치 그래프에도 사용할 수 있지만 bfs가 더 빠르다'고 알고있는데 이 말도 맞나요?
4년 전
dfs로 최단거리 탐색은 매우 비효율적일 것 같은데 아예 불가능한지는 잘 모르겠네요. bfs가 다익스트라보다 효율이 좋긴 합니다.
4년 전
안녕하세요 헷갈리는 개념이 있어서 댓글남깁니다. 쉽게 접할 수 있는 2차원 형태의 배열에서 (0,0)에서(m,n) 까지의 최단거리를 구할때 DFS와 BFS를 모두 사용할 수 있다고 알고 있는데요. 이 경우는 트리 순회라고 보면 되나요? 단방향 그래프로 보고 위랑 오른쪽 길만 가능하다고 생각하면 트리가 늘어났다가 하나로 합쳐지는 트리를 그릴 수 있을 것 같은데 맞을까요? 즉 '일반적인 트리형태에서는 dfs와 bfs로 최단거리를 구할 수 있다' 라는 말이 맞나요?
4년 전
네 맞습니다.
4년 전
트리의 개념 자체가 여러노드가 한 노드를 가르킬수 없다 라고 정의를 하는데 그럼 그래프를 트리로 생각하는거 자체가 오류 아닌가요
4년 전
여러 노드가 한 노드를 가리킬 수 없다라는 게 무슨 뜻이죠? 트리는 기본적으로 여러 노드가 한 노드를 가리킵니다. 그래프는 트리가 아니지만, 트리는 그래프의 일종입니다.
4년 전
트리가 그래프의 일종이어서 하는 말인데 위와 같은 그래프는 트리로 변환을 하려는것 자체가 모순아닌가요? 두 노드를 잇는 길이 하나밖에 없는 그래프만을 트리로 변환을 가능하다고 알고있어서요!
4년 전
그래프를 트리로 변환하라고 하는 게 아니고요. 그래프에서 기준노드를 하나 잡아서 그 노드를 기준으로 최단거리 관계를 따지면 트리처럼 배치할 수 있고 거기서 dfs나 bfs를 생각하면 이해하기 쉽다는 뜻입니다.
4년 전
그래프에서 dfs나 bfs를 적용하려면 그래프를 트리처럼 생각해야하는 것이지 트리로 변환해야하는 것이 아닙니다.
4년 전
질문있습니다! 소스코드 안보구 알고리즘이랑 그림만 본다고 생각하면 DFS 순서가 A-X-H-E-Y-M-J-P-G 도가능한건가요??
4년 전
네 가능합니다.
4년 전
I'm Sorry 오류가 있는 거 같아요 실수로 투표
4년 전
글쓴이 님께 한표. 당연히 노드를 방문했을때 모든 자식들을 한번에 스택에 넣어야 하고, G를 이미 스택에 넣었으므로 P에서 G로 가지 못함. 그리고 스택에는 자식들을 무조건 왼쪽부터 쌓는게 아니라 아크를 입력한 순서대로 스택에 쌓는게 맞음. 코드에 H와 E가 연결되는 아크를 먼저 넣으셨으므로, 4번에서 스택에 GEP가 맞음.
4년 전
네네 맞습니다. 그림이 중요한 게 아니라 아크 입력 순서가 중요한 것이죠. 저도 아래 댓글 때문에 매우 황당했습니다.
4년 전
그래프를 트리처럼 보는자와 아닌자의 싸움 . 재밌었습니다
4년 전
inTree 에 대해서는 무슨 의미인지 설명이 없네요. 컬럼 처음부터 다 살펴봐도
4년 전
탐색 완료되었음을 나타내는 속성입니다.