오늘 배운 것

알고리즘_그래프 탐색

하나의 버텍스(Vertex)으로부터 시작하여 모든 정점들을 순회하는 것.

그래프(Graph) 탐색의 종류에는 DFS(Depth First Search)와 BFS(Breadth First Search)가 있다.

트리(Tree) 자료구조는 방향성 있는 그래프이므로, DFS와 BFS를 활용해 모든 노드를 탐색할 수 있다.

DFS(Depth First Search)

버텍스의 자식들을 우선으로 탐색하는 방식.

스택(Stack)이나 재귀(Recursive)를 활용해 구현할 수 있다.

• 방향성이 없는 그래프의 경우
  1. 시작 정점(Vertex)를 스택에 넣고, 방문 여부를 표시한다.
  2. 스택에서 꺼내면서 출력(명령)한다.
  3. 방문하지 않은 인접 버텍스들을 스택에 넣고, 방문 여부를 표시한다.
  4. 스택에서 꺼내면서 출력(명령)한다.
  5. 마지막 버텍스에 도달할 때 까지 3~4 반복
• 방향성이 있는 그래프(트리)의 경우
  1. 시작 정점(Vertex)를 스택에 넣는다.
  2. 스택에서 꺼내면서 출력한다.
  3. 자식 노드들을 스택에 넣는다.
  4. 스택에서 꺼내면서 출력한다.
  5. 마지막 노드에 도달할 때 까지 3~4 반복
• 스택(Stack) 대신 재귀(Recursive)를 이용할 수도 있다.

BFS(Breadth First Search)

버텍스의 형제들을 우선으로 탐색하는 방식.

큐(Queue)를 활용해 구현할 수 있다.

• 방향성이 없는 그래프의 경우
  1. 시작 정점(Vertex)를 큐에 넣고, 방문 여부를 표시한다.
  2. 큐에서 꺼내면서 출력(명령)한다.
  3. 방문하지 않은 인접 버텍스들을 큐에 넣고, 방문 여부를 표시한다.
  4. 큐에서 꺼내면서 출력(명령)한다.
  5. 마지막 버텍스에 도달할 때 까지 3~4 반복
• 방향성이 있는 그래프(트리)의 경우
  1. 시작 정점(Vertex)를 스택에 넣는다.
  2. 스택에서 꺼내면서 출력한다.
  3. 자식 노드들을 스택에 넣는다.
  4. 스택에서 꺼내면서 출력한다.
  5. 마지막 노드에 도달할 때 까지 3~4 반복