수심 우선 그래프 알고리즘의 시간 복잡도

Question

시간 복잡성을 배우기 시작하고 몇 가지 간단한 정렬의 시간 복잡성 예제를 살펴 보았습니다.

|V|=n과 |E|=m이있는 그래프에서 깊이 우선 탐색의 평균 시간 복잡도를 계산하려면 어떻게 시작 노드를 'u'로, 끝 노드를 'v'로 만드는지 알고 싶습니다.

Answer 1

DFS의 시간 복잡도는 O (n + m)입니다. 우리는 각 노드를 한 번만 방문한다는 사실과 모든 에지를 한 번 교차하는 트리 (사이클 없음)를 고려하여이 복잡성을 얻습니다.

예를 들어 시작 노드가 u이고 끝 노드가 v 인 경우 v가 마지막으로 방문한 노드가 될 최악의 시나리오를 생각하고 있습니다. 그래서 우리는 각각의 첫 번째 이웃의 연결 요소, 두 번째 이웃의 연결된 구성 요소 등을 방문하기 시작합니다. 마지막 이웃의 연결된 구성 요소, 여기서 우리는 v를 찾습니다. 우리는 각 노드를 한 번만 방문했고, 같은 가장자리를 두 번 이상 넘어 섰다. 그래프는 인접 행렬의 형태 인 경우의 그래프는 인접리스트하지만 의 형태로 주어지면

Answer 2

그러므로 복잡도는 O (n 개 * 않음) 우리가있다 (N + m) O 것 우리가 가장자리를 찾을 때까지 전체 행을 통과해야합니다.