내용이 안 보인다면 쿠키/캐시를 지우고 새로고침 하세요!
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌21 - Algorithm - 2년 전 등록 / 10달 전 수정

그래프 탐색

DFS(깊이 우선)와 BFS(너비 우선)
조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

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

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

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) 때문에 자동으로 너비 우선 탐색이 됩니다.

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

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

13개의 댓글이 있습니다.
4달 전
안녕하세요, 코드 잘 보고 있습니다. DFS부분에서 탐색순서를 A-X-H-P 로 진행했다면 그 다음 탐색 순서는 E가 아니라 G가 되어야 하는 것 아닌가요? 작성해주신 알고리즘에 대해 이야기 하는 것이 아니라, DFS의 개념을 생각했을 때요!
4달 전
E든 G든 상관없습니다. 둘 다 DFS입니다. 누구를 누구의 자식으로 볼 건가의 차이입니다.
4달 전
빠른 답변 감사합니다. P와 G 사이에 엣지가 존재하는데, G를 P의 자식 노드로 보지않을 수 있나요..?
4달 전
G는 H 또는 X의 자식으로 여겨지는 경우입니다.
7달 전
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의 스택 사용은 위와 같은데 제로초님께서 말씀하시는 방식으로 스택을 사용하여도 문제가 없는 것인지 궁금합니다.
7달 전
헉, 이렇게 상세하게 설명하실 줄 몰랐네요. 결론부터 말씀드리자면 둘 다 맞습니다. 처음 달라지는 부분이 H나 G나 여기서 시작하는데요. 그래프를 어떻게 트리로 변환하느냐에서 차이가 있는 것입니다. G H 순으로 나오는 것은 H를 G의 자식으로 본거고, H가 먼저 나오는 것은 H랑 G를 형제로 본 것입니다.
7달 전
그리고 저는 제 방식이 더 직관적인 것 같은게, 질문자분의 방식에서는 왜 18단계나 거쳐야 하는지 잘 이해가 되지 않네요.
7달 전
저도 제로쵸님의 방식이 더 직관적인 것 같긴합니다.
다만 제가 의문스러운 것은 알고리즘이란 것이 동일 인풋의 동일 아웃풋이라는 단순한 정의로 살펴본다면..
동일한 인풋에 내부 구현방식에 따라 다양한 아웃풋이 나온 다는 점에서 알고리즘의 하나의 원칙이라고 생각했던 부분 동일 인풋 동일 아웃풋이 손상된다는 점입니다 ㅠㅠ;
다수의 책과 블로거들의 글들을 보면 대부분은 위에 불필요한 18단계를 사용하고 있다는 점에서 정확한 DFS의 정의는 무엇인지 생각을 하게 됩니다... 이래서 또 저의 숙제가 하나 늘었네요 ㅎㅎ;; 근데 답변을 엄청 빨리 달아주시네요! 나름 포인트있는 컨텐츠만 잘 정리해서 개시하시고 운영도 잘하시는 것 같아서 많은 도움을 받고 갑니다.
7달 전
동일 인풋과 동일 아웃풋이 알고리즘의 조건인 건 맞습니다. 그런데 하나 놓치신 게 있습니다. DFS 알고리즘이 하나가 아니라는 겁니다. 저희 둘의 알고리즘은 이름만 같고 다른 알고리즘입니다. 세상에 제로초란 이름을 가진 사람이 둘이라고 해서 같은 사람이 아닌 것 처럼요.
7달 전
엄밀하게 따지면 DFS는 로직이 하나로 정해진 알고리즘이라기 보다는 방법론에 더 가깝다는 게 제 의견입니다.
7달 전
오 저와 같은 생각을 말씀하시네요. 알고리즘이라고 하기 보다는 방법론에 더 가깝다고 생각이 들었습니다.
답변 매우 감사합니다.
9달 전
정리해보자면// () : 권장
트리 최단거리 탐색 - (BFS), DFS, 다익스트라
비가중치 최단거리 탐색 - (BFS), 다익스트라
가중치 최단거리 탐색 - (다익스트라), (마샬 플로이드)
이렇게 정리해두는게 맞을까요?
9달 전
마지막으로 왜 비가중치, 가중치 그래프에서는 최단거리 탐색 시 dfs를 사용할 수 없는지도 궁금합니다. 위에서 dfs 예시에서와 같이 가중치 그래프 역시 완전탐색을 통해서 최단거리를 구할 수 있지 않나요? 안된다는 말은 많은데 간혹가다가 된다고 정리해두신 분들도 있어서 헷갈리네요.
9달 전
완전탐색을 하면 가능하긴 하겠는데 그게 dfs만을 사용했다고 표현할 수 있는지가 논란의 여지가 될 수 있을 것 같습니다. 거의 브루트포스 수준 아닌가요?
9달 전
반면에 트리를 포함하는 개념인 그래프의 경우에는 'dfs와 bfs로 탐색은 가능하지만 비가중치 그래프에서는 bfs로만 최단거리를 구할 수 있고, 가중치 그래프의 경우에는 다익스트라나 마샬을 이용해야된다'고 알고 있는데 맞나요? 여기서 '다익스트라를 비가중치 그래프에도 사용할 수 있지만 bfs가 더 빠르다'고 알고있는데 이 말도 맞나요?
9달 전
dfs로 최단거리 탐색은 매우 비효율적일 것 같은데 아예 불가능한지는 잘 모르겠네요. bfs가 다익스트라보다 효율이 좋긴 합니다.
9달 전
안녕하세요 헷갈리는 개념이 있어서 댓글남깁니다. 쉽게 접할 수 있는 2차원 형태의 배열에서 (0,0)에서(m,n) 까지의 최단거리를 구할때 DFS와 BFS를 모두 사용할 수 있다고 알고 있는데요. 이 경우는 트리 순회라고 보면 되나요? 단방향 그래프로 보고 위랑 오른쪽 길만 가능하다고 생각하면 트리가 늘어났다가 하나로 합쳐지는 트리를 그릴 수 있을 것 같은데 맞을까요? 즉 '일반적인 트리형태에서는 dfs와 bfs로 최단거리를 구할 수 있다' 라는 말이 맞나요?
9달 전
네 맞습니다.
10달 전
트리의 개념 자체가 여러노드가 한 노드를 가르킬수 없다 라고 정의를 하는데 그럼 그래프를 트리로 생각하는거 자체가 오류 아닌가요
10달 전
여러 노드가 한 노드를 가리킬 수 없다라는 게 무슨 뜻이죠? 트리는 기본적으로 여러 노드가 한 노드를 가리킵니다. 그래프는 트리가 아니지만, 트리는 그래프의 일종입니다.
10달 전
트리가 그래프의 일종이어서 하는 말인데 위와 같은 그래프는 트리로 변환을 하려는것 자체가 모순아닌가요? 두 노드를 잇는 길이 하나밖에 없는 그래프만을 트리로 변환을 가능하다고 알고있어서요!
10달 전
그래프를 트리로 변환하라고 하는 게 아니고요. 그래프에서 기준노드를 하나 잡아서 그 노드를 기준으로 최단거리 관계를 따지면 트리처럼 배치할 수 있고 거기서 dfs나 bfs를 생각하면 이해하기 쉽다는 뜻입니다.
10달 전
그래프에서 dfs나 bfs를 적용하려면 그래프를 트리처럼 생각해야하는 것이지 트리로 변환해야하는 것이 아닙니다.
일 년 전
질문있습니다! 소스코드 안보구 알고리즘이랑 그림만 본다고 생각하면 DFS 순서가 A-X-H-E-Y-M-J-P-G 도가능한건가요??
일 년 전
네 가능합니다.
일 년 전
I'm Sorry 오류가 있는 거 같아요 실수로 투표
일 년 전
글쓴이 님께 한표. 당연히 노드를 방문했을때 모든 자식들을 한번에 스택에 넣어야 하고, G를 이미 스택에 넣었으므로 P에서 G로 가지 못함. 그리고 스택에는 자식들을 무조건 왼쪽부터 쌓는게 아니라 아크를 입력한 순서대로 스택에 쌓는게 맞음. 코드에 H와 E가 연결되는 아크를 먼저 넣으셨으므로, 4번에서 스택에 GEP가 맞음.
일 년 전
네네 맞습니다. 그림이 중요한 게 아니라 아크 입력 순서가 중요한 것이죠. 저도 아래 댓글 때문에 매우 황당했습니다.
일 년 전
그래프를 트리처럼 보는자와 아닌자의 싸움 . 재밌었습니다
일 년 전
dfs에서 x다음에 g, h같이 들어가는거 문제있네요. x다음에 형제 둘(g,h)이 같이 들어가는건 bfs입니다. dfs와 bfs 개념이 혼동된거 같습니다.
일 년 전
아뇨, 위에서 설명한 개념이 맞습니다. GH 둘 다 들어가야 됩니다. G는 내버려두고 H의 자식을 먼저 탐색하기 때문에 깊이 우선 탐색이 맞습니다. 이 강좌는 대학교 전공책의 내용을 자바스크립트로 포팅한 것이라 틀림이 없습니다.
일 년 전
아니 그..직접 해보시면 뭔가 이상하다는게 느껴지지 않을까요?..어떤 책을 사용하시는지는 모르겠지만 책에도 오류는 있으니깐요ㅎ 지금 저 그래프만 봐도 A, X, H, P순서로 가는데 P에서 G로 갈수 있음에도 더이상 갈곳이없다고 판단하고 다시 H로 올라간다음 E로 가네요. 애초에 스택에 들어가는 방법이 잘못되었습니다. 심각한 오류라고 생각합니다.
일 년 전
탐색 시 P에서 G로는 못 갑니다. G는 P를 탐색하는 시점에 이미 스택에 들어있어서 inTree가 true입니다. 따라서 G는 무시됩니다. 이 책은 Introduction to algorithms라고 알고리즘 중 최고 책입니다. 절대 오류 없습니다. 제가 직접 이 책으로 해보기도 했고요.
일 년 전
물론 스택에 g가 있으면 무시가 되겠지만 그 자체가 말이안된다고 생각합니다. 애초에 다른걸 떠나서 GH가 같이 들어가는거 부터가 이해가 안가네요. 둘중하나가 먼저들어가고 예를들어 G가 들어갔으면 G의 자식들중 하나를 넣고 그런식으로 깊이우선으로 진행되는것이 DFS인데 어째서 BFS처럼 x의 자식을 같이 집어 넣는 거죠?? 어느책을 봐도 DFS를 설명하면서 스택에 자식들을 동시에 집어넣는것은 보지못하였습니다.
일 년 전
그리고 지금 dfs로 그래프 노드 방문 순서가 A X H P E Y M J G 인데 애초에 단순하게 그래프만 봐도 P를 방문하고 G로 갈수있는데 그러지 않고 다시 되돌아 가잖아요. 깊이우선이면 일단 가는 길이 있으면 땅속까지 파고들기세로 깊게 방문하는건데 길이있는데도 불구하고 안가잖아요. 그럼 스택에 넣는 방법이 잘못된거 아닌가요? 그래프만 보고 생각해도 그러한데..스택에 넣었다는건 방문했다는거 아닌가요?
일 년 전
지금 이 방법은 탐색하는 방법입니다. DFS이니까 최대한 아래로만 탐색하는 방법요. G는 P보다 위에 있어요. P에서 G로 가는 것 자체가 말이 안 됩니다. 스택에 넣는 것은 방문했다는 뜻이 아니라 방문을 위한 중간 도구에요. DFS의 방문은 console.log 부분이 방문입니다. 스택에 자식들을 동시에 집어넣는 것과 DFS는 아무 관련이 없어요. 자식들을 동시에 집어넣는 이유는 나중에 백트래킹을 하기 위해서입니다. 동시에 집어넣더라도 마지막에 넣은 자식 하나만 아래로 먼저 탐색하거든요.
일 년 전
스택에 형제 둘이 들어간다고 BFS인 게 아니고요. 결과가 어떻게 출력되는지가 DFS와 BFS를 결정합니다. 스택과 큐는 그저 DFS, BFS를 구현하는 중간 도구일 뿐입니다.
일 년 전
물론 그건 저도 알고있습니다. 근데 그래프만 보더라도 P에서 G로 갈 수 있는데도 불구하고 가지 않고 H로 되돌아 가잖아요...DFS는 더이상 갈 곳이 없을때 되돌아가는건데 이상하지 않나요?
일 년 전
아뇨. G로 못 간다니깐요. G는 이미 스택에 한 번 들어간 버텍스(P보다 상위에
있는)라서 다시 못 갑니다. 만약 P에서 G로 간다면 G에서는 다시 X로 가고, X에서는 다시 A로 가실 건가요?
일 년 전
아니그러니깐..자료구조는 생각하지 말고 알고리즘만 놓고 볼게요. 지금 A X H P E Y M J G 이순서로 방문하면서 탐색하고 있잖아요? 근데 P를 방문했을때 P는 G와 인접해 있어요. G가 P위에 있건 밑에있건은 DFS에선 중요하지 않아요. 연결되어있으면 가는거에요. P가 갈곳이있는데 H로 돌아갈수는 없어요. 그래프를 보면서 저순서대로 방문을 해보세요 자료구조는 신경쓰지마시구요. 그러면 P다음에 G를 방문 할 수 밖에 없어요. 즉 방문 순서는 A X H P G E Y M J 순서로 나옵니다.
일 년 전
자꾸 스택에 있어서 못간다고 하시는데.. 알고리즘만 생각하고 그래프를 보면서 직접 탐색을 해보시면 방문하게 되요. 그러니까 스택에 넣는 과정이 잘못된거에요...
일 년 전
지금 DFS 개념을 잘못 알고 계시네요. 트리의 DFS랑 그래프의 DFS는 달라요. 연결되어 있으면 가는 게 아닙니다. 그냥 더 하위 뎁스로 가는 거에요. 하위 뎁스는 부모(A)에서부터의 거리가 뎁스가 됩니다. 위키피디아(https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89) 참고하세요. 알고리즘(코드)은 틀린 곳이 없습니다. 설명은 이해하기 쉽도록 조금 수정했습니다.

최종적으로 정리하자면, 지금 현재 트리의 DFS를 생각하고 계신 것 같습니다. 그래프의 DFS 알고리즘은 트리와는 다르고요. 그래프 DFS 시에는 논리적으로 그래프를 트리 모양으로 바꾸어주어야 합니다. 이 때 시작점(A)으로부터의 거리가 뎁스가 되는 트리로 바꾸셔야 하고요. 이 바꾸는 과정에서 P와 G의 연결점이 끊어집니다. 물론 아크 순서를 바꾼다면 다른 트리로 만들 수도 있습니다. 근데 제 코드 상에서는 P와 G의 연결점이 끊어지도록 아크 순서를 배치해서 그렇습니다.
일 년 전
그래프를 트리모양으로 바꾸는거 알고 있습니다..근데 그래프든 트리든 DFS는 같아요. 지금 저 그래프를 트리로 만들면 g는 depth가 2이고 P는 3입니다. 그렇다고 위에있다고 못 올라가지 않아요. 위에 있어도 연결만 되어있고 아직 방문하지 않았으면 올라갈 수 있습니다. 그리고 그래프를 트리로 바꾼다고 해서 연결점이 끊어질수는 없습니다. 데이터가 유실될 수는 없어요. 지금 저 그래프만 해도 모든 연결점을 유지한 트리로 바꾸는데 아무 이상없습니다. 혹시 dfs는 부모노드로 올라갈 수 없다는 말씀을 하시는 건가요??
일 년 전
제 알고리즘 상으로는 못 올라갑니다. 연결점은 개념상으로 트리로 표현할 때 끊어진다고 표현한 것이지 실제로는 끊어지는 것은 아닙니다. 제 알고리즘 코드를 돌려보시긴 하셨나요?

http://www.egr.unlv.edu/~larmore/Courses/CSC477/bfsDfs.pdf

제 코드랑 비슷한(참조한 책과도 비슷한) 수도 코드를 찾았습니다. 미국 수학자의 코드고 대학 강의 교재니 틀리진 않았겠죠. visited가 제 코드의 inTree라고 보시면 됩니다. 보시다시피 같은 DFS더라도 알고리즘이 여러 개입니다. 제 알고리즘에는 어떠한 오류도 없습니다.
일 년 전
네 님 소스코드에 문제가 있는거 같네요. 저 수도코드는 잘못된거 없고요 저도 확인했습니다. 님 저 위에 그림에서 4번째 스택 쌓이는 순서가 G E P 가 아니고 G P E면 정상구동합니다. 아무래도 순서에서 착오가 있으셨던거 같은데. 님 소스코드보면 ARC삽입한 순서로 스택에 쌓는데 지금 님 소스코드를 보면 ARC 삽입하는 순서에서 H E랑 H P랑 순서가 바뀐거 같네요. 쉽게 말해서 트리라고 치면 왼쪽우선으로 DFS하다가 갑자기 오른쪽으로 방향이 바뀐거랄까요? 확인 부탁드립니다. 그래서 맞게 수정하시면 A X H E Y M J P G 이순서가 되네요 ㅎ
일 년 전
이해가 잘 안 되네요. 제 소스코드의 결과는 AXHPEYMJG로 그림과 똑같이 출력됩니다. 저는 그림의 설명을 그대로 소스코드로 옮긴 것 뿐입니다. AXHEYMJPG는 제가 의도하는 설명이 아닙니다. AXHEYMJPG는 그림에도 없고 아무 곳에도 없는데 왜 이렇게 해야 하는지 잘 모르겠네요.

아 그림을 다시 보니 무슨 말씀이신지 이해는 갑니다. 그림은 그래프가 오른쪽 먼저 탐색을 했다 왼쪽 탐색을 했다 섞여있네요. 그림이 조금 이상하긴 하지만 제 코드는 그림의 결과를 기준으로 작성한 것입니다. 그리고 P 대신 E가 4번이 되어야한다는 것은 DFS의 필요조건이 아닙니다. 그래프에서 왼쪽 오른쪽은 아무 의미가 없습니다. 그냥 180도 회전을 하면 그만이니까요.
일 년 전
뭔가 이상한점이 있죠? 제가 봤을 땐 그림에 약간 오류가 있는 것 같습니다. 저명한 책이어도 오류는 있을 수 있으니까요. P대신 E가 4번이 된다는 게 필수조건은 아닙니다. 컴퓨터공학을 전공하고 졸업한 사람으로서 많은 분들이 보시는 포스팅에 오류를 지적해드리고 싶은 거구요. 당장 저 그래프를 트리로 바꿔서 손으로 직접 풀어보더라도 절대 저 순서로는 답이 나올 수 없습니다. 왼쪽 우선이든 오른쪽 우선이든 알파벳순서든 depth우선이든 규칙에 통일성이 없으면 옳은 답이 나올 수가 없습니다. 그래프에서 왼쪽 오른쪽은 의미가 없다고 하셨는데 일관된 규칙을 가정하지 않는 알고리즘은 아무 의미가 없습니다. 님이 누워있든 서있든 왼팔 왼다리는 같은 방향이니까요. 다시 말씀드리지만 그림은 잘못되었습니다. P를 방문한 이상 G를 건너 뛸 수는 없습니다. DFS는 부모라고 올라가지 못하는 알고리즘이 아닙니다. 님이 링크걸어주신 자료가 지금 이 포스팅의 정리와 일치하지만 예제는 잘못되었습니다.
일 년 전
저는 동의하지 않습니다. 그림은 헷갈리긴 하지만 아무런 오류도 없고요. 직접 풀어보면 저 순서로 답이 나옵니다. 제 코드가 저 순서로 답이 나옴을 증명하는데 어떻게 다르게 설명하실 수가 있는지 궁금하네요. 현재 알고리즘 상 DFS는 명백히 부모를 거슬러 올라갈 수 없습니다. 다른 DFS 알고리즘이라면 몰라도요. 처음에 모든 형제를 스택에 넣어버리고 그 다음부터는 연결된 노드 중 스택에 들어있는 노드만 빼고 모두 추가하는데 어떻게 자식이 부모 노드로 올라갑니까?

규칙에 통일성도 있습니다. 연결된 아크 순서대로 DFS가 처리하는 것이죠. 그래프에서는 방향이 아무런 상관이 없습니다. 저 그림을 저렇게 그린 이유는 선이 교차하는 것을 없애기 위함입니다. 아래 이미지를 보시면
https://imgur.com/a/K4Ox0
제가 imgur에 올린 이미지랑 포스팅의 그래프는 동일합니다.
일 년 전
1. 님 코드는 저 그림을 보고 짠거니까요.
2. 현재 알고리즘이든 다른 알고리즘이든 DFS는 다 같습니다. 연결된 길인데 가지 않고 되돌아 갈수 있는 방법은 없습니다.
3. 스택을 언급하시면서 자식이 부모로 갈 수 없다고 하셨는데 4번째 스택에 G E P가 아닌 G P E로 바꾸시고 손으로 따라가 보시면 이해하실 것 같습니다. 스택 특성상 뒤에 것부터 연결된 애들을 하나씩 처리하고 오기 때문에 g p e 순서로 삽입되면 마지막에 g p 만 남아서 가능합니다.
4. 그래프는 방향이 상관없다고 하셨는데 E M과 E Y 삽입 순서만 바꿔도 답은 다르게 나옵니다.
5. 연결된 아크순서가 잘못된 것입니다. 님 말대로 아크순서대로 DFS를 처리하고 있기 때문에 H E랑 H P가 순서가 잘 못되었습니다. 아크순서가 규칙인데
'A', 'X' // 'X', 'G' // 'X', 'H' // 'G', 'H' // 'G', 'P' 등등 이 순서를 아무렇게나 하면 알고리즘은 아무의미가 없어집니다. 전 이 순서를 얘기하고 있는 거구요.
6. 저 그림이 선이 교차하든 안하든 아무런 상관이 없습니다. 그저 님이 보는 사람 보기 편하게 그렸겠지요.
7. 다 떠나서 님의 DFS알고리즘이 다른 DFS와 다를 이유가 없습니다. 다르면 잘못 된거구요. 좀 더 효율적으로 짤 수는 있어도 결과가 달라선 안 됩니다. 어떤 방법으로 해도 P를 방문한 상황에서 G를 건너뛸 수는 없습니다. 제가 말하고 싶은 요점은 이거에요. 이 개념을 놓치면 엄청난 혼란이오구요. DFS는 부모의 개념이 없습니다. 연결되어있으면 가는거에요. 그리고 님이 어떤 규칙으로 아크순서를 정한건진 모르지만 그 순서를 정하는데도 규칙이 있어야합니다. 저 순서는 아무 규칙이 없어서 일반화 되지 못하는 것뿐입니다. 정 답답하시면 스택오버플로나 다른 커뮤니티에 물어보시면 잘못 된 점을 알 수 있으실 겁니다.
8. 자료의 오류를 인정할 수 있어야 하구요.
일 년 전
황당하네요. 먼저 수도 코드가 잘못된 게 아니죠? 수도 코드 상에서는 부모로 거슬러 올라갈 수 없게 되어 있습니다. 연결되어있다고 부모로 올라가고 그런 개념이 아니란 말입니다. 그리고 수도 코드의 그래프 DFS 특성상 아크 연결 순서가 섞이면 당연히 결과도 다르게 나옵니다. 순서를 섞는 것은 input을 섞는 것이기 때문에 당연히 알고리즘의 output도 다르게 나오죠. input과 output은 언제든지 바뀔 수 있는 겁니다.

일단 수도 코드와 그것을 구현한 제 코드(알고리즘)은 틀린 부분이 없고, 문제는 저기 저 그림인데요. 일단 output은 AXHPEYMJG로 정해져 있습니다. output에서 input을 역추적하면 위의 Graph 예제가 되는 것이고요. 당연히 위의 Graph 예제를 알고리즘에 넣으면 AXHPEYMJG라는 output이 나오고요. 예제는 그냥 예제일 뿐입니다. 고정된 알고리즘이 있고, 고정된 output이 있습니다. 당연히 고정된 input이 있어야죠. 그게 제가 코드로 구현한 Graph란 말입니다.
일 년 전
수도코드를 A로한건지 B로한건진 모르겠지만 부모로 올라가지 못하는 개념은 없구요. 아웃풋이 잘못된경우 백트래킹은 의미가 없습ㄴ디ㅏ.
일 년 전
수도코드 A고요. visited때문에 부모나 삼촌 레벨로 못 올라갑니다. 코드 분석해보세요. 아웃풋이 뭐가 잘못되었다는 건지 도무지 이해가 안 가네요.
일 년 전
수도코드 아무이상 없는거 알아요. 그리고 Visit 때문에 부모나 삼촌레벨로 못올라 가지 않습니다. visit은 그저 스택에서 pop하는노드 하나 한테만 true로 하는거에요. 아무 이상없습니다. 제 말대로 4번째 스택 [G E P]를 [G P E]로 바꿔서 해보세요 손으로요. 그럼 부모나 삼촌으로 올라가잖아요 님 소스코드로 돌려볼려면 아크 입력하는 부분에서 16줄이라 17줄을 바꾸면 되겠네요. P에서 G로 가는 길이있는데 스킵하고 돌아갈수는 없어요..
일 년 전
17번째 줄 if (!arc.destination.inTree)에서 부모로 올라가는 게 차단됩니다. 16, 17번째 줄 바꿀 필요도 없고요. GPE로 바궜을 때 E 먼저 처리하고 P로 가는 것은 스택 안에 그 순서대로 들어가있어서 그런 것이지 pop할 때 부모를 거슬러 올라가는 것은 아니죠. P를 pop할 때 A, X, H, G는 이미 inTree가 다 true라서 아무 일도 일어나지 않습니다.

이 강좌에서 핵심은 알고리즘인데 알고리즘은 틀린 부분이 하나도 없습니다. 그리고 그림은 알고리즘을 사용하는 예제 중 하나일 뿐입니다. 예제도 결과가 정확히 출력됩니다. 아무 문제도 없다는 뜻입니다.
일 년 전
그래도 덕분에 좋은거 알아가네요~ 평소에 DFS탐색할때 스택에 하나씩 순차적으로 내려갈 생각만했지 한꺼번에 자식들 올려놓는 방법은 생각못했는데.. 생각해보니 어짜피 후입선출이라 깊이우선이 되는군요. 편리한 방법알아갑니다~
일 년 전
추가적으로 재귀로 하는 DFS도 있으니 그 방법도 알아두시면 좋습니다~
일 년 전
inTree 에 대해서는 무슨 의미인지 설명이 없네요. 컬럼 처음부터 다 살펴봐도
일 년 전
탐색 완료되었음을 나타내는 속성입니다.