💡Graph 탐색

• 하나의 시작점 정점에서 연결된 모든 정점들을 찾는 것을 그래프 탐색이라고 하며, 그래프 순회라고도 한다.
• 그래프 탐색을 통해 그래프의 구조에 대해 의미있는 정보들을 알아낼 수 있다.
• 의미있는 정보들에는 주어진 두 정점이 경로를 통해 연결되었는지 등이 있다.
• Graph 탐색 방법에 따라 Breadth First Search(BFS) 와 Depth First Search(DFS) 로 나뉜다.

📌BFS(Breadth First Search)

• 너비를 우선적으로 탐색하는 Graph 탐색 방법
  

BFS 알고리즘

• 시작 정점을 방문 표시 후에 큐에 넣음
• 큐에 아무 정점이 없을 때까지 반복
  • 큐의 가장 앞 정점을 꺼냄
  • 꺼낸 점정에 인접한 정점들을 모두 확인하면서:
    • 처음 방문한 정점이라면:
      • 방문한 정점 표시를 해줌
      • 큐에 넣어줌

📌DFS(Depth First Search)

• 깊이를 우선적으로 탐색하는 Graph 탐색 방법
  

DFS 알고리즘

• 시작 정점을 옆은 회색으로 표시 후, 스택에 넣음
• 스텍에 아무 정점이 없을 때까지 반복
  • 스택 가장 위 정점을 꺼냄
  • 정점을 짙은 회색으로 방문 표시함
  • 꺼낸 정점에 인접한 정점들을 모두 확인하면서:
    • 처음 방문하거나 스택에 없는 정점이라면:
      • 옆은 회색으로 표시함
      • 스택에 넣어줌