DFS의 복잡성은 인접성 매트릭스에서 O (V2)이고 인접성 목록 표현에서 O (V + E) 인 이유는 무엇입니까?

Question

DFS 알고리즘이 인접성 매트릭스 표현에서 O (V2) 강점을 가지고 있고 인접성 목록 표현에서 O (V + E)를 갖는 이유는 무엇입니까?

Answer 1

매트릭스의 경우 :

각 정점에 대해 하나의 열과 하나의 열이 있습니다. 위치 i, j에는 정점 i에서 정점 j까지의 모서리가 있으면 1이 포함됩니다.

전체 행렬의 크기는 | V |^2

복잡성이 왜 | V |^2?

매트릭스의 각 위치가 한 번 방문되기 때문에. . 복잡성은 왜 정점 V에 대한 목록이 정점 V에 인접한 모든 정점의 목록이되도록 각 정점에 대한 하나 개의 목록으로

을 연결리스트의

컬렉션 | : 인접를 들어

목록을 연결 E | + | V | 인접 링크 된 목록의 각 위치는 한 번 방문되고 | V | 정점과 | E | 가장자리.