0부터 n -1까지 번호가 매겨진 n개의 꼭짓점을 포함하는 그래프가 있다고 가정합니다. 그래프는 무향이며 각 간선에는 가중치가 있습니다. 따라서 그래프가 주어지면 그래프 MST에서 임계 및 의사 임계 에지를 찾아야 합니다. 해당 간선을 삭제하면 MST 가중치가 증가하는 경우 해당 간선을 임계 간선이라고 합니다. 유사 임계 간선은 모든 그래프 MST에 나타날 수 있지만 전부는 아닌 간선입니다. 그래프가 입력으로 주어졌을 때 모서리의 인덱스를 찾습니다.
따라서 입력이 다음과 같으면
정점의 수가 5이면 출력은 [[], [0, 1, 2, 3, 4]]가 됩니다. 주어진 그래프에 임계 모서리가 없고 모든 모서리가 의사 임계입니다. 모든 간선의 가중치가 같으므로 그래프의 3개 간선이 모두 MST가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
find_mst() 함수를 정의합니다. 이것은 num_vertices, graph, init :=null, exl :=null
을 취합니다. -
하나의 도우미 함수 visit() 을 정의합니다. 이것은 당신을 걸릴 것입니다
-
k[u] :=참
-
그래프[u, 빈 목록]의 각 v, w에 대해 수행
-
exl과 u가 exl에 있고 v가 exl에 있으면
-
다음 반복으로 이동
-
-
k[v]가 True가 아니면
-
삼중항(w,u,v)을 힙 tmp로 푸시
-
-
-
해상도 :=0
-
k :=False 값을 포함하는 num_arrays 크기의 새 목록
-
tmp :=새 힙
-
init가 null이 아니면
-
유 :=초기화
-
v :=초기화
-
w :=초기화
-
res :=res + w
-
k[u] :=참
-
k[v] :=참
-
방문(u) 또는 방문(v)
-
-
그렇지 않으면
-
방문(0)
-
-
tmp가 비어 있지 않은 동안 수행
-
w :=힙 tmp에서 가장 작은 항목 팝
-
u :=힙 tmp에서 가장 작은 항목 팝
-
v :=힙 tmp에서 가장 작은 항목 팝
-
k[u] 및 k[v]가 0이 아닌 경우
-
다음 반복으로 이동
-
-
res :=res + w
-
k[u]가 True가 아니면
-
방문(u)
-
-
k[v]가 True가 아니면
-
방문(v)
-
-
-
k가 모두 True이면 res를 반환하고, 그렇지 않으면 무한대를 반환합니다.
-
기본 방법에서 다음을 수행합니다.
-
그래프 :=주어진 그래프
-
temp :=find_mst(num_vertices, 그래프)
-
c_edge :=새 목록
-
p_edge :=새 목록
-
범위 0에서 가장자리 크기까지의 i에 대해
-
find_mst(num_vertices, graph, exl =edge[i, index 2 to end])> temp, then
-
c_edge의 끝에 i 삽입
-
-
그렇지 않고 find_mst(num_vertices, graph, init =edge[i])가 temp와 같으면
-
p_edge의 끝에 i 삽입
-
-
-
반환 [c_edge, p_edge]
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
from heapq import heappop, heappush
def solve(num_vertices, edges):
graph = dict()
for u, v, w in edges:
graph.setdefault(u, []).append((v, w))
graph.setdefault(v, []).append((u, w))
temp = find_mst(num_vertices, graph)
c_edge, p_edge = [], []
for i in range(len(edges)):
if find_mst(num_vertices, graph, exl = edges[i][:2]) > temp:
c_edge.append(i)
elif find_mst(num_vertices, graph, init = edges[i]) == temp:
p_edge.append(i)
return [c_edge, p_edge]
def find_mst(num_vertices, graph, init = None, exl = None):
def visit(u):
k[u] = True
for v, w in graph.get(u, []):
if exl and u in exl and v in exl:
continue
if not k[v]:
heappush(tmp, (w, u, v))
res = 0
k = [False] * num_vertices
tmp = []
if init:
u, v, w = init
res += w
k[u] = k[v] = True
visit(u) or visit(v)
else:
visit(0)
while tmp:
w, u, v = heappop(tmp)
if k[u] and k[v]: continue
res += w
if not k[u]:
visit(u)
if not k[v]:
visit(v)
return res if all(k) else inf
print(solve(5, [[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,0,10]])) 입력
5, [[0,1,10],[1,2,10],[2,3,10],[3,4,10],[4,0,10]]
출력
[[], [0, 1, 2, 3, 4]]