특정 가장자리에 MST가 포함되어 있지 않은지 확인

Question

MST와 Directed-Graph에 대한 질문이 있습니다. 가중치 함수 w : E -> R이있는 그래프 G가 있고 E 그룹 (u, v)의 에지 e가 있다고 가정 해 봅시다. 전자가 MST에 포함되어 있지 않은지 확인하는 알고리즘을 o (E + V)에서 찾아야합니다.

Answer 1

숫자를 가중치로 사용하는 대신 숫자 쌍의 벡터를 가중치로 사용하십시오. 추가는 구성 요소 단위입니다. 비교는 첫 번째 숫자에 해당하며 두 번째 숫자에 대한 연결을 끊습니다. (매우 편리하게, 파이썬이 튜플을 불공평에 대해 비교하는 기본 규칙입니다.)

각 가장자리에 지정 x(w(x), 0)의 무게. 그러나 귀하의 특별한 요소 인 e의 무게는 (w(e), -1)입니다.

이제 MST를 검색하십시오. 원본 그래프에 e이 포함 된 MST가있는 경우에만 MST에 e이 포함됩니다.