[algorithm] 너비 우선 대 깊이 우선

용어 이해하기 :

이 그림은 너비 와 깊이 라는 단어 가 사용되는 상황에 대한 아이디어를 제공합니다 .

깊이 우선 검색 :

• 깊이 우선 검색 알고리즘은 가능한 한 빨리 시작점에서 멀어 지길 원하는 것처럼 작동합니다.

• 일반적으로 a Stack를 사용 하여 막 다른 곳에 도달했을 때 어디로 가야하는지 기억합니다.

• 따라야 할 규칙 : 첫 번째 정점 A를 Stack

  1. 가능하면 방문하지 않은 인접한 정점을 방문하여 방문한 것으로 표시 한 다음 스택에 밀어 넣습니다.
  2. 규칙 1을 따르지 않으면 가능하면 스택에서 꼭지점을 팝하십시오.
  3. 규칙 1 또는 규칙 2를 수행 할 수 없으면 완료된 것입니다.

• 자바 코드 :

  public void searchDepthFirst() {
      // Begin at vertex 0 (A)
      vertexList[0].wasVisited = true;
      displayVertex(0);
      stack.push(0);
      while (!stack.isEmpty()) {
          int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
          // If no such vertex
          if (adjacentVertex == -1) {
              stack.pop();
          } else {
              vertexList[adjacentVertex].wasVisited = true;
              // Do something
              stack.push(adjacentVertex);
          }
      }
      // Stack is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++)
          vertexList[j].wasVisited = false;
  }
  

• 응용 분야 : 깊이 우선 검색은 종종 게임 시뮬레이션 (실제 게임과 같은 상황)에 사용됩니다. 일반적인 게임에서는 몇 가지 가능한 동작 중 하나를 선택할 수 있습니다. 각 선택은 추가 선택으로 이어지고, 각 선택은 추가 선택으로 이어지고, 계속 확장되는 나무 모양의 가능성 그래프로 이어집니다.

너비 우선 검색 :

• 너비 우선 검색 알고리즘은 가능한 한 시작점에 가깝게 유지하기를 원합니다.
• 이러한 종류의 검색은 일반적으로을 사용하여 구현됩니다 Queue.
• 준수해야 할 규칙 : 정점 A를 현재 정점으로 시작
  1. 현재 정점에 인접한 다음 방문하지 않은 정점 (있는 경우)을 방문하여 표시 한 다음 대기열에 삽입합니다.
  2. 더 이상 방문하지 않은 정점이 없기 때문에 규칙 1을 수행 할 수 없으면 대기열에서 정점을 제거하고 (가능한 경우) 정점으로 만드십시오.
  3. 대기열이 비어있어 규칙 2를 수행 할 수 없으면 완료된 것입니다.

• 자바 코드 :

  public void searchBreadthFirst() {
      vertexList[0].wasVisited = true;
      displayVertex(0);
      queue.insert(0);
      int v2;
      while (!queue.isEmpty()) {
          int v1 = queue.remove();
          // Until it has no unvisited neighbors, get one
          while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
              vertexList[v2].wasVisited = true;
              // Do something
              queue.insert(v2);
          }
      }
      // Queue is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++)
          vertexList[j].wasVisited = false;
  }
  

• 응용 프로그램 : 너비 우선 검색은 먼저 시작점에서 한 모서리 떨어진 정점을 찾은 다음 두 모서리 떨어진 정점 등을 찾습니다. 시작 정점에서 주어진 정점까지의 최단 경로를 찾으려고 할 때 유용합니다.

너비 우선 검색 및 깊이 우선 검색을 이해하기에 충분해야합니다. 자세한 내용은 Robert Lafore의 훌륭한 데이터 구조 책에서 Graphs 장을 참조하십시오.

답변

- Level 1: G
- Level 2: D, I
- Level 3: B, E, H, K
- Level 4: A, C, F

Order Searched: G, D, I, B, E, H, K, A, C, F

1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:
Grab the Root. (G)
Then Check the Left. (It's a tree)
Grab the Root of the Left. (D)
Then Check the Left of D. (It's a tree)
Grab the Root of the Left (B)
Then Check the Left of B. (A)
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)
Check the Right of D. (It's a tree)
Grab the Root. (E)
Check the Left of E. (Nothing)
Check the Right of E. (F, Finish D Tree. Move back to G Tree)
Check the Right of G. (It's a tree)
Grab the Root of I Tree. (I)
Check the Left. (H, it's a leaf.)
Check the Right. (K, it's a leaf. Finish G tree)
DONE: G, D, B, A, C, E, F, I, H, K

2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.
Check the Left of the G Tree. (It's a D Tree)
Check the Left of the D Tree. (It's a B Tree)
Check the Left of the B Tree. (A)
Check the Root of the B Tree (B)
Check the Right of the B Tree (C, finished B Tree!)
Check the Right of the D Tree (It's a E Tree)
Check the Left of the E Tree. (Nothing)
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...
Onwards until...
DONE: A, B, C, D, E, F, G, H, I, K

3) POSTORDER:
LEFT, RIGHT, ROOT
DONE: A, C, B, F, E, D, H, K, I, G