dfs 알고리즘 질문드립니다.

Question

질문내용: 그래프 간의 edge를 연결하는 방식을, 인접리스트로 구현했을때 dfs 시간복잡도가(V&#43;E)가 되는지 궁금해서 질문드립니다.(V:node, E:edge)1번 node 부터 시작 시, 1번 node에 연결된 edge 만큼 for이 수행되고2번 node 부터 시작 시, 2번 node에 연결된 edge 만큼 for이 수행되고...v번 node 부터 시작 시, 2번 node에 연결된 edge 만큼 for이 수행되므로 O(V*E)만큼의 시간복잡도가 나오지 않나요?

maringo · Answer

그래프 알고리즘에서모든 노드에 붙어있는 edge에 대해서 확인 하지 않자나요. 그렇기 때문에 O(E&#43;V) 아닐까요?첫 노드에선 첫노드에 붙어있는 모든 edge를 검사하지만, 그 다음 노드가 선택 되고 나서 최적의 길로 찾아가기 때문에 그런걸로 알아요. 그래프 알고리즘이 시간복잡도가 각각 다르긴 하지만요.

dfs 알고리즘 질문드립니다.

1개의 답변

Q&A 목록