minimum-spanning-tree

3열

2답변

일부 가장자리가 고정되어있는 경우 MST에 대한 표준 Kruskal 형 접근 방식이 적용됩니까?

문제 : 그래프의 최소 스패닝 트리 (예 : 그래프에서 가장자리의 집합 S가 각 꼭지점과 함께 S에서 모서리가 트리를 형성 함)를 찾아야하며, 추가적으로 그러한 모든 집합에서 S 내의 모든 에지 비용은 최소가되어야한다). 그러나 잡을 거리가 있습니다. K가 S에 포함되어야하는 고정 된 가장자리 K의 초기 세트가 주어집니다. 즉, 고정 된 가장자리의 시작 세

2열

1답변

특정 노드의 차수를 최소화하는 최소 스패닝 트리

(모든 최소 스패닝 트리 중에서) 노드의 차수를 최소화하는 최소 스패닝 트리를 어떻게 찾을 수 있습니까? 동일한 무게의 여러 가장자리가있는 경우 v을 만지지 않는 것을 선택하면 Kruskal 알고리즘이 문제를 해결할 수 있습니까?

3열

2답변

유클리드 최소 스패닝 트리 및 들로네 삼각

나는 2 차원 평면에 점 세트 사이의 유클리드 거리에 따라 최소 스패닝 트리를 계산할 . 내 현재 코드는 모든 가장자리를 저장 한 다음 Prim의 알고리즘을 수행하여 최소 스패닝 트리를 얻습니다. 그러나, 나는 이것을 수행하는 것이 모든 가장자리에 대해 O(n^2) 공간을 차지한다는 것을 알고 있습니다. 몇 가지 조사를 한 후 처음으로 delaunay 삼각

0열

1답변

Prim의 알고리즘에 대한 최악의 경우 그래프

My Algorithms 클래스는 가중치 그래프의 최소 스패닝 트리를 찾는 방법으로 Prim의 알고리즘에 대해 설명합니다. 교수님은 Prim 's Algorithm이 풀기 위해 N^2 시간 (N = Vertices 수)이 걸리는 그래프의 예를 생각해 보라고했습니다. 수업 중에 아무도 머리 꼭대기에서 벗어난 사람을 생각할 수 없습니다. 그래서 나는 당신에게

0열

1답변

자바 - MST에서 가장 큰 가중치를 찾는 방법은 무엇입니까?

제목과 같이 질문은 매우 간단합니다. V 꼭지점이있는 가중치가있는 에지가없는 기존 MST가 있습니다. 주어진 시작 노드와 끝 노드에는 MST에서 가장 큰 가중치를 반환하는 O(V) 시간에 실행되는 효율적인 알고리즘이 있습니까? 감사합니다.

0열

1답변

배열 목록에서 최소 스패닝 트리

ArrayList에서 최소 스패닝 트리를 찾을 수 있는지 궁금합니다. 난 그냥 각 정점에서 최소 수를 찾는 것에 대해 생각했지만, 난 너무 확실하지 않았다 import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Scanne

4열

1답변

최소 스패닝 트리 quesiton에 적합한 솔루션입니까?

나는 시험에서 질문을하고 나의 접근 방식이이 질문에 맞는지 알고 싶다. Input: graph G(V,E),weight function f:E->R and edge e=(u,v). output: algorithm that finds a minimum spanning tree with edge e in it. 내 솔루션은 나무가 N-1 가장자리를하기 때

0열

2답변

Kruskal의 최소 스패닝 트리 프로그램 (C) 자신이 아닌 다른 컴퓨터에서 실행하려고 할 때 세그먼트 오류 (코어 덤프) 오류가 발생합니다.

최소 스패닝 트리를 찾기 위해 프로그램에 문제가 있습니다. 문제없이 올바르게 작동합니다. 내 컴퓨터에서 다른 컴퓨터에서 실행하려고 할 때 세그먼트 오류 (코어 덤프) 오류가 발생했습니다. 왜 그런 일이 발생하는지 이유를 찾을 수 없습니다. 라인 (188)에 #include <stdio.h> #include <stdlib.h> #include <strin

-1열

1답변

고유 최소 스패닝 트리 충분하고 필요한 조건

충분하고 필요한 조건 인 그래프 G가 주어지면이 그래프는 고유 한 최소 스패닝 트리를 갖습니다. 지금까지, 나는 그 조건이 있음을 발견했다 : 두 부분 집합으로 V (G)의 모든 파티션에 대한 1), 각 부분 집합에서 하나의 엔드 포인트와 최소 무게 에지가 유일하다. 2) G의 모든 사이클에서 최대 가중치는 고유합니다. 그러나 이것이 맞는지 확실하지 않습니

1열

1답변

최소 확장 포리스트를 찾는 데 사용되는 알고리즘은 무엇입니까? 위키 백과으로

는 말한다 : 최소 걸쳐 숲 의 연결 구성 요소의 최소 스패닝 트리의 조합이다. 우리가 예를 Prim's algorithm, Kruskal's algorithm, 또는 Borůvka's algorithm에 사용할 수있는 최소 스패닝 트리를 찾는 . 최소 확장 포리스트를 찾기 위해 어떤 알고리즘을 사용할 수 있습니까?