오은이 하우스

- 위키백과 - 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. 그래프의 너비 우선 탐색 알고리즘을 Java로 구현해보자. 우선 빈번히 사용 Node 클래스를 작성한다. Node.java public class Node { int info;//정점에 대응된 데이터 boolean visited;//방문 여부 List neighbours;//정점에 인접한 정점들의 연결 목록 public Node(int info..

트리의 순회 방법에는 3가지가 있다. 전위 순회 중위 순회 후위 순회 한 가지씩 자세히 알아보자. 1. 전위 순회( preorder ) 전위 순회란 루트 노드를 가장 먼저 방문하고, 왼쪽과 오른쪽 서브트리를 방문하는 순회 방법이다. 다음과 같은 예제에서 전위 순회 방법을 사용한다면 방문 순서가 어떻게 될까? 루트노드를 가장 먼저 방문해야 하므로 처음엔 0번을 방문할 것이고, 그 다음엔 왼쪽과 오른쪽의 서브트리가 남는다. 왼쪽을 먼저 방문하면, 왼쪽 서브트리에는 또 루트노드인 1이 있다. 따라서 루트노드인 1을 방문하고, 왼쪽 노드와 오른쪽 자식노드인 3, 4를 방문한다. 그렇게 하면 방문 순서는 다음과 같다. 2. 중위 순회( Inorder ) 중위 순회는 루트 노드를 중간에 방문하기에 중위 순회라고 생..