알고리즘 [그래프 순회]

🔎 그래프의 순회!

그래프에서 순회란, 모든 정점과 간선을 검사하며 그래프를 탐험하는 체계적인 절차

수도권의 모든 전철, 항공사의 모든 노선(간선), 웹에서 검색한 키워드에 대한 모든 간선등을 예로 들 수 있다.

주요 전략으로 깊이우선탐색, 너비우선탐색이 있다.

DFS(깊이우선탐색)

• 그래프의 모든 정점과 간선을 방문할 수 있다.
• 그래프가 연결 그래프인지 알수있다.

• 그래프의 연결요소를 알수있다.

• n개의 정좀과 m개의 간선을 가진 그래프라면 O(n+m)시간 소요