그래프 - 새로운 에지 여기

Question

추가 후 최소 스패닝 트리를 업데이트 구현 소비세에게이다

가정하자 우리 G (N 개의 정점과 m 가장자리) 주어진 그래프의 최소 확장 트리 T 주어진다 그리고 우리가 G에 추가 할 가중치 w 의 새로운 에지 e = (u, v)를 제공합니다. 그래프 G + e의 최소 스패닝 트리를 찾는 효율적인 알고리즘을 제공하십시오. 귀하의 알고리즘은 O (n) 전체 크레딧을받을 시간 내에 실행되어야합니다.

나는이 아이디어가 :

In the MST, just find out the path between u and v. Then find the edge (along the path) with maximum weight; if the maximum weight is bigger than w, then remove that edge from the MST and add the new edge to the MST.

---

까다로운 부분은 O에서 (n)이 시간이 작업을 수행하는 방법입니다 그리고 내가 문제가 발생할 수도 있습니다.

질문은 MST가 저장되는 방식입니다. 통상의 Prim의 알고리즘에서, MST는 부모 어레이로서 저장된다. 즉, 각 요소는 대응하는 정점의 부모이다.

그러면 소비세가 MST를 나타내는 상위 배열을 제공한다고 가정하면 위의 알고리즘을 O (n)에서 어떻게 풀 수 있습니까?

먼저 부모 배열에서 u와 v 사이의 경로를 식별 할 수 있습니까? u와 v에 대해 두 조상 배열을 가질 수 있습니다. 그런 다음 공통 조상을 확인한 다음 거꾸로도 경로를 얻을 수 있습니다. 나는 공통 조상을 찾기 위해이 부분을 생각합니다. 적어도 O (n^2)에서해야합니다. 맞습니까?

그런 다음 경로가 있습니다. 그러나 우리는 여전히 경로를 따라 각 가장자리의 무게를 찾아야합니다. 그래프에서 Prim의 알고리즘에 대한 adjacency-list를 사용한다고 가정하기 때문에 가장자리의 각 가중치를 찾으려면 O (m) (m은 가장자리의 수)를 수행해야합니다.

...

그래서 나는 그것을 볼 수 없습니다는 O (N)의 알고리즘을 수행 할 수 있습니다. 내가 잘못?

Answer 1

당신이 갖고있는 아이디어가 옳습니다. u과 v 사이의 경로는 O(n)입니다. MST를 확인하기 위해 parent array이 있다고 가정합니다. u에서 v 또는 u에서 root vertex까지 경로를 추적하려면 O(n) 만 가져야합니다. root vertex에 도달하면 v에서 u 또는 root vertex까지 경로를 추적하면됩니다. 이제 u -> u1 ... -> max_path_vert1 -> max_path_vert2 -> ... -> v에서 경로를 가지고

, (이 추가 된 가장자리보다 더 큰 가정) 가장자리 max_path_vert1->max_path_vert2를 제거하고 u->...->max_path_vert1의 부모 역 및 parent[u] = v을 표시합니다.

편집 : MST에서 정점의 쌍 사이에 정확히 하나 개의 경로가 될 것

주 명확성에 대한 자세한 설명. 따라서 u->y 및 v->y에서 추적 할 수있는 경우 최대 점은 n 개입니다. n 개 이상의 정점을 추적하면 정점을 두 번 방문했음을 의미합니다. MST에서는 발생하지 않습니다. 자, 이제 O (n)가 u->y과 v->y에서 추적 할 것이라 확신합니다.이 경로가 있으면 u->v 경로를 설정했습니다. 어떻게 보이니? 유향 그래프의 MST를 찾는 것은 그 자체로는 다른 개념이기 때문에 이것은 무향 그래프라고 가정합니다. 방향이 지정되지 않은 그래프의 경우 x->y 경로가 있으면 y-x 경로가 있습니다. 따라서 u->y->v이 존재합니다. v->y의 가중치는 y->v의 가중치와 같으므로 y->v에서 추적 할 필요조차 없습니다. u->y과 v->y에서 추적 할 때 최대 무게로 가장자리를 찾으십시오.

이제 O (1)에서 에지 가중치를 찾습니다. 현재 무게를 어떻게 보관하고 있습니까? 인접 목록 또는 인접 행렬? O (1) 액세스의 경우 부모 정점 배열이 저장되는 방식으로 저장합니다. 그래서 weight[v] = weight(v, parent[v]). O (1) 액세스 권한이 있습니다. 희망이 도움이됩니다.

Answer 2

음 - 해결책은 정확합니다.

구현과 관련하여, 왜 T 대신에 G를 사용하여 U와 V 사이의 경로를 찾지 못하는지 알 수 없습니다. T에서 U와 V 사이의 경로를 검색하여 O (n)을 제공합니다. - 즉, v가 루트이고 깊이 우선 탐색 알고리즘을 수행한다고 가정 할 수 있습니다 (이 경우 v의 모든 이웃을 자식이라고 가정해야 함) - 일단 u를 발견하면 DFS를 중지하십시오. 스택의 노드는 u와 v 사이의 경로에 해당합니다.

경로 (O (n))에서 각 가장자리의 비용을 찾기가 쉽고 가장자리를 삭제/추가하는 것이 쉽습니다. 총 O (n).

어떻게 든 도움이됩니까?

O (n^2)의 T에서 정점 v의 자식에 액세스 했으므로 어쩌면 O (n^2)를 얻고있는 것일 수 있습니다 - 여기에서 데이터 구조를 a 비용을 O (1)로 줄 이도록 매핑 된 배열을 만듭니다. [instace, {a, b, c, u, w} (정점) -> {0,1,2,3,4} (정점의 인덱스).