그래프 순회 문제(Graph Traversal Problem) ; 그래프 탐색 문제(Graph Search Problem)

그래프 순회 문제(Graph Traversal Problem) ; 그래프 탐색 문제(Graph Search Problem)

• 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제
• 그래프 순회 문제를 수학적으로 표현할 경우
  • 그래프 G = <V, E>가 주어질 떄, 특정 정점 s로부터 시작하여 모든 정점 v ∈ V를 방문하는 문제라고 할 수 있음.
• 그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도 로 사용될 수 있기 떄문에 그래프 탐색 문제(Graph Search Problem) 라고도 부름.
• 여러 그래프 탐색 알고리즘이 존재하고, 각각은 서로 다른 순서로 모든 정점을 방문함.
• 종류
  • 너비 우선 탐색(BFS, Breadth-First Search)
  • 깊이 우선 탐색(DFS, Depth-First Search)

 

예 : 우리집과 식당

• 우리집과 식당을 그래프의 정점으로 표시하고, 연결된 도로를 에지로 표현한 후, 우리집에서 시작하여 모든 식당에 방문하려고 할 경우

• 정점 옆에 빨간색으로 쓰인 숫자 : 정점의 ID
  • 1번 정점 : 우리집
  • R1부터 R7까지의 정점 : 식당
• 모든 길은 어느 방향으로든 이동할 수 있으므로, 에지에 화살표가 없는 무방향 에지 로 표현함.