[Graph] 순회, Traversal

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 순회 (Traversal)

• 그래프의 모든 정점을 방문하는 체계적인 방법

 

- 깊이 우선 탐색 (DFS, Depth First Traversal)

DFS, 출처 위키피디아

• DFS는 임의의 정점에서 시작하여 이웃하는 하나의 정점을 방문하고, 방금 방문한 정점의 이웃 정점을 방문하며 이웃하는 정점들을 모두 방문한 경우에는 이전 정점으로 되돌아가서 탐색을 수행하는 방식으로 진행
• 특징
  • DFS(v)는 v의 연결 성분에 대하여 모든 정점 및 간선을 방문
  • DFS(v)의 Discovery edge는 v의 연결 성분에 대하여 신장 트리를 생성
• 수행 시간
  • DFS의 수행 시간은 모든 정점과 간선에 대하여 한 번씩 방문하므로 O(m+n)
    
    • m : 간선 개수
    • n : 정점 개수

 

- 너비 우선 탐색 (BFS, Breadth First Traversal)

BFS, 출처 위키피디아

• BFS는 임의의 정점 s에서 시작하여 s의 모든 이웃하는 정점들을 방문하고, 방문한 정점들의 이웃 정점들을 모두 방문하는 방식으로 그래프의 모든 정점을 방문
• 특징
  • BFS(v)는 v의 연결 성분에 대하여 모든 정점과 간선을 방문
  • BFS(v)의 Discovery edge는 v의 연결 성분에 대하여 신장 트리를 생성
• 수행 시간
  • BFS의 수행 시간은 모든 정점과 간선에 대하여 한 번씩 방문하므로 O(m+n)
    
    • m : 간선 개수
    • n : 정점 개수