dfs 트리1 [알고리즘] ep5-2) 그래프 순회 그래프 순회(graph traversal): 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차- 수도권 전철망의 모든 역(정점)의 위치를 출력- 항공사의 모든 항공편(간선)에 대한 노선 정보를 수집- 웹 검색엔진의 데이터 수집 부문은 웹의 하이퍼텍스트 문서(정점)와 문서 내 링크(간선)를 검사함으로써 서핑 그래프의 순회로는 DFS, BFS 두 가지가 있다그래프 G에 대한 DFS 순회 또는 BFS 순회의 활용은 아래와 같다- G의 모든 정점과 간선을 방문- G가 연결그래프인지 결정- G의 연결요소들을 계산- G의 신장 숲을 계산 ① 깊이우선탐색(DFS, Depth-First Search) by 스택(재귀)n개의 정점과 m개의 간선을 가진 그래프에 대한 DFS는 O(n + m) 시간 소요 "D.. 2024. 7. 21. 이전 1 다음
