연결리스트 표현의 그래프 탐색시간 - 아래 제시된 문제에 대한 해설

[홍재연]

아래 해설과 알고리즘은 이석호 교수의 자료구조론 내용을 참조하여

파이썬 코드로 구현한 것입니다.

==========================================================================

• 함수 dfs()의 수행시간은 O(e)이다.

• 함수 connected()의 수행시간은 O(n+e)이다.

• 단절그래프에서 함수 dfs()만 있으면 모든 정점이 방문되지 않는다.

• 단절그래프에서 함수 dfs()만 있으면 하나의 연결요소 정점만 방문된다.

• 연산시간 Ο(e)와 Ο(n+e)의 차이는 그래프가 연결그래프냐? 단절그래프냐? 에 의한다.

• 즉, 그래프가 연결그래프냐? 단절그래프냐? 에 따라 탐색 알고리즘 차이가 있다.

• 연결그래프 : O(e)

• 단절그래프 : O(n+e)

• 그러면, 지금까지 시험에서는 어떻게 출제되었나?

• 그래프가 연결그래프냐? 단절그래프냐?를 구분하지 않고 출제되고 있고,

• 또 알고리즘은 연결그래프 기준으로 제시하고 있다.

• 알고리즘은 연결그래프 기준으로 제시하고, 정답은 단절그래프 기준으로 발표하고 있다.

• 연결그래프 알고리즘이면, dfs()의 연산시간은 O(e)인데, 정답은 O(n+e) 발표하고 있다.

• 지금까지 dfs()의 연산시간 관련 내용은 몇 번 출제되었다.

• 그런데, dfs()의 연산시간은 O(e)이냐? O(n+e)이냐?로 정답이 결정되는 것은 오직 한번 출제되었다.

• 그러면, 앞으로 또 이런 내용이 혹시 출제되면 어떻게 해야 하는가?

• 즉, dfs()의 연산시간은 O(e)이냐? O(n+e)이냐? 정답을 무엇으로 해야 하느냐?

• 제시된 알고리즘에 따라 연산시간은 O(e) 또는 O(n+e)을 정답으로 해야 한다.

• 그리고, 정답이 잘못 발표되면 이의신청해야 한다.

• 지금까지 어떻게 출제되었든지 상관없이 잘못된 것을 정답으로 체크할 수는 없다.

==========================================================================