210915. Graph2

sylph0105·2021년 9월 21일
0

With Codestates

목록 보기
105/114
post-thumbnail

공부시간 : 19:30 ~ 22:00

오늘의 공부
[자료구조/알고리즘] 자료구조 기초 : Graph

💡 Graph 탐색

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

🤍 BFS 알고리즘

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

🤍 DFS 알고리즘

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

0개의 댓글