1
그래프의 모든 버텍스를 찾아야하는이 CLRS 문제를 해결했습니다 G(V,E). 우리는 모든 꼭지점의 각도를 찾기 위해 모든 가장자리를 스캔해야하기 때문에 솔루션이 O(|E|) 인 것을 알았습니다.인접 목록 indegree
그러나 해결책의 대부분은 내가 온라인이라고 말하면서 그것이 O(|V|+|E|)이라고 말합니다. 어째서? 버텍스는 시간을 어떻게 고려하고 있습니까?
A
답변
0
다이 그래프의 구현에서 정점에 대한 오브젝트를 사용한다고 가정하고 각 정점이 후속 항목의 관련 목록과 추가 데이터 구조가없는 경우 직접 가장자리를 반복 할 수 없습니다.
그래프가 연결된 경우 각 vertext에는 적어도 하나의 연관된 가장자리가 있습니다. 즉, 정점에 대한 반복을 통해 에지를 반복하는 데 걸리는 시간은 O(|E|)입니다. 즉, 정점에 대한 반복은 실행 시간을 증가시키지 않으며, 이는 가장자리 수에 의해 좌우됩니다.
만약 자 그래프가 이 아니고이면, 꼭지점에 걸친 반복은 반드시 모서리 수에 의해 좌우되지는 않습니다. 고립 된 꼭지점을 처리해야만 O(|V|+|E|) 시간에 수행 할 수있는 연결된 호가 없음을 알 수 있습니다.
O(|V|+|E|)의 런타임 경계는 두 경우 모두 동일합니다. 그러나, 연결된 고리 그래프 (또는 정점 수에 관계없이 가장자리를 통해 직접 반복을 허용하는 구현)의 경우 런타임 경계가보다 좁은 O(|E|)을 얻을 수 있습니다.