나는 이것으로 고민하고있다.빠른 MST 알고리즘?
MST는 Kruskal의 알고리즘이나 Prim의 알고리즘을 사용하여 얻을 수 있습니다.
그리고 "차선"MST에 대한
, 내가 할 수그러나이 실행 O에 (VE) 정점의 납입 및 E는 모서리의 수입니다.
Union-find disjoint set 또는 LCA (lowest common ancester)를 사용하여 속도를 높이려면 어떻게해야합니까?
힌트, pseodo 코드 또는 웹 링크 포인터.
도움이 되었으면 좋겠습니다. 고마워요 :)
V을 정점 집합으로하고 E을 모서리 집합이라고합시다.
T을 표준 알고리즘을 사용하여 얻은 MST라고합시다.
maxEdgeInPath(u,v)을 T의 정점 u에서 정점 v까지 고유 경로의 최대 모서리라고합시다.
각 버텍스에 대해 u은 T에서 BFS를 수행합니다. V-u에 속하는 모든 x에 대해 maxEdgeInPath (u, x)를 제공합니다.
2ndMST의 w(x,y) - w(maxEdgeInPath(x,y))
무게를 최소화 T에 속하지 않는 가장자리 (x,y) 찾기 W(T) + w(x,y) - maxEdgeInPath(x,y)
이이 link에서 제공하는 알고리즘을 기반으로합니다. 나는 이것이 정확하고 누군가가 여기에 증거를 추가하기를 바랍니다.
Compexity : O(V^2)
#include <iostream>
#include <conio.h>
using namespace std;
#define ROW 7
#define COL 7
#define infi 5000 //infi for infinity
class prims
{
int graph[ROW][COL],nodes;
public:
prims();
void createGraph();
void primsAlgo();
bool checkforcrossline(int*,int,int);
};
prims :: prims(){
for(int i=0;i<ROW;i++)
for(int j=0;j<COL;j++)
graph[i][j]=0;
}
void prims :: createGraph(){
int i,j;
cout<<"Enter Total Nodes : ";
cin>>nodes;
cout<<"\n\nEnter Adjacency Matrix : \n";
for(i=0;i<nodes;i++)
for(j=0;j<nodes;j++)
cin>>graph[i][j];
//Assign infinity to all graph[i][j] where weight is 0.
for(i=0;i<nodes;i++){
for(j=0;j<nodes;j++){
if(graph[i][j]==0)
graph[i][j]=infi;
}
}
}
void prims :: primsAlgo(){
int selected[ROW],i,j,ne; //ne for no. of edgesintfalse=0,true=1,min,x,y;
int min,x,y;
int Answer=0;
for(i=0;i<nodes;i++)
selected[i]=false;
selected[0]=true;
ne=0;
while(ne < nodes-1){
min=infi;
for(i=0;i<nodes;i++)
{
if(selected[i]==true)
{
for(j=0;j<nodes;j++)
{
if(selected[j]==false)
{
if((min > graph[i][j]) && checkforcrossline(selected,i,j))
{
min=graph[i][j];
x=i;
y=j;
}
}
}
}
}
selected[y]=true;
cout<<"\n"<<x+1<<" --> "<<y+1;
Answer+=graph[x][y];
ne=ne+1;
}
cout<<"\nCost : "<<Answer ;
}
bool prims :: checkforcrossline(int* selectedArr,int n1,int n2)
{
int big,small;
if(n1>n2)
{
big=n1;small=n2;
}
else
{
big=n2;small=n1;
}
int restNodes[ROW];
int count=0;
for(int i=0;i<small;i++)
{
if(selectedArr[i]==true)
{
restNodes[count]=i;
count++;
}
}
for(int j=big+1;j<nodes;j++)
{
if(selectedArr[j]==true)
{
restNodes[count]=j;
count++;
}
}
int start=small+1;
int end = big;
for(;start<end;start++)
{
if(selectedArr[start] == true)
{
for(int find=0;find<count;find++)
{
if(graph[start][restNodes[find]]!= infi)
return false;
}
}
}
return true;
}
int main(){
prims MST;
cout<<"\nPrims Algorithm to find Minimum Spanning Tree\n";
MST.createGraph();
MST.primsAlgo();
return 0;
}
설정 Δ이다 O(V+E) = O(V)T 따라서 전체 시간 복잡도에 E = V-1로 1 개 정점 BST를 계산하는 데 걸리는 | T | = ∞.
Enew = -1 및 Eold = -1로 설정하십시오.
트리에없는 모든 가장자리 e에 대해 다음을 수행하십시오.
- 트리에 가장자리를 추가하여주기를 만듭니다. k! = e가되도록 사이클에서 최대 가중치를 찾는다.
- 제거 k
- 나무 무게 δ = 무게 (e) - 무게 (k)의 변화를 계산하십시오.
- δ 일 경우 < Δ | T | 그때 Δ | T | = δ 및 Enew = e 및 Eold = k이다.
새 트리는 Eold를 Enew로 바꾸는 결과입니다.
실행 시간 가장자리
수에 비례
용액 참조 : 그것은 에지를 추가 한 후, 다른 점을 추가 할 필요가 여기 http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf
을 형성된 사이클의 최대 가중 에지를 계산하여 새로운 에지와 이전 에지 사이의 차이를 발견하면, 차이를 m으로 만드는 에지의 트랙을 유지해야한다 inimum. 이 특정 에지를 추가하여 두 번째로 가장 작은 최소 스패닝 트리를 형성 할 수 있습니다.
이 링크는 질문에 대답 할 수 있지만 답변의 핵심 부분을 여기에 포함시키고 참조 용 링크를 제공하는 것이 좋습니다. 링크 된 페이지가 변경되면 링크 전용 답변이 유효하지 않게 될 수 있습니다. – Marusyk
문제에 대한 다결정 해를 설명합니다. 몇 가지 정의를 소개합시다. 우리는 나타내는 것이다 : 그래프의 정점의
V에 의해, E에 의해 그래프의 모서리의 설정 T에 의해 MST 가장자리의 집합입니다.v 및 u은 {v, u}입니다.e은 W(e)이고 MST의 무게는 W(T)이다. 이다 T이 속하는 v 및 u 간의 간단한 경로에 큰 가중치 에지 같다 MaxEdge(v, u) 기능을 고려하자. 최대 가중치가있는 여러 개의 가장자리가있는 경우 MaxEdge(v, u)과 같을 수 있습니다.
x = {p, q}을 찾을 필요, 그 두 번째 최고의 MST를 확인하는 방법은 다음과 같습니다
x는 T에 속하지 않습니다.W(x) - W(MaxEdge(p, q))은 가능한 최소입니다.그것은 최고의 두 번째 MST가 T에서 MaxEdge(p, q)을 제거하고 T에 x = {p, q}을 추가하여 구성 할 수 있음을 증명하는 것이 가능하다.
이제 MaxEdge(p, q)을 O(log|V|)에 계산할 수있는 데이터 구조를 만들자.
트리의 루트를 선택하자. T (모든 정점이 될 수 있음). 꼭지점 v과 루트 인 꼭지점 깊이 v 사이의 단순 경로에서 가장자리 수를 호출하고 Depth(v)으로 지정합니다. O(|V|)에있는 모든 정점에 대해 Depth(v)을 depth first search으로 계산할 수 있습니다.Depth(v) - 2^i 동일한 깊이와 부모 정점 같다
Parent(v, i)는, 정점 v의 (비 직접 부모가 될 수 있음) : MaxEdge(p, q)을 계산하는 데 도움이 될 것입니다 의 두 가지 기능을 계산하자
, .MaxParentEdge(v, i)이고, 이는 MaxEdge(v, Parent(v, i))과 동일하다.둘 다 O(|V|log|V|)에 암기를 갖는 반복 함수에 의해 계산 될 수 있습니다.
// Assumes that 2^i <= Depth(v)
Vertex Parent(Vertex v, Vertex i) {
if (i == 0) return direct_parent[v];
if (Memorized(v, i)) return memorized_parent[v][i];
memorized_parent[v][i] = Parent(Parent(v, i - 1), i - 1);
return memorized_parent[v][i];
}
Edge MaxParentEdge(Vertex v, Vertex i) {
if (i == 0) return Edge(v, direct_parent[v]);
if (Memorized(v, i)) return memorized_parent_edge[v][i];
Edge e1 = MaxParentEdge(v, i - 1);
Edge e2 = MaxParentEdge(Parent(v, i - 1), i - 1);
if (W(e1) > W(e2)) {
memorized_parent_edge[v][i] = e1;
} else {
memorized_parent_edge[v][i] = e2;
}
return memorized_parent_edge[v][i];
}
MaxEdge(p, q)을 계산하기 전에 최종 정의를 소개하겠습니다. Lca(v, u)은 루트 트리 T에서 정점 v 및 u의 lowest common ancestor을 나타냅니다. Lca(v, u) 쿼리를 O(log|V|) 또는 심지어 O(1)에 계산할 수있는 잘 알려진 데이터 구조가 많이 있습니다 (Wikipedia에서 기사 목록을 찾을 수 있습니다). p에서 Lca(p, q)에 Lca(p, q)에서 q에 :
우리는 두 부분으로 p와 q 사이의 경로를 나눕니다 MaxEdge(p, q)을 계산합니다. 이 각각의 부분은 정점에서부터 부모까지의 경로처럼 보입니다. 따라서 Parent(v, i) 및 MaxParentEdge(v, i) 함수를 사용하여이 부분에 MaxEdge을 계산할 수 있습니다.
Edge MaxEdge(Vertex p, Vertex q) {
Vertex mid = Lca(p, q);
if (p == mid || q == mid) {
if (q == mid) return QuickMaxEdge(p, mid);
return QuickMaxEdge(q, mid);
}
// p != mid and q != mid
Edge e1 = QuickMaxEdge(p, mid);
Edge e2 = QuickMaxEdge(q, mid);
if (W(e1) > W(e2)) return e1;
return e2;
}
Edge QuickMaxEdge(Vertex v, Vertex parent_v) {
Edge maxe = direct_parent[v];
string binary = BinaryRepresentation(Depth(v) - Depth(parent_v));
for (int i = 0; i < binary.size(); ++i) {
if (binary[i] == '1') {
Edge e = MaxParentEdge(v, i);
if (W(e) > W(maxe)) maxe = e;
v = Parent(v, i);
}
}
return maxe;
}
기본적 QuickMaxEdge(v, parent_v) 길이 2^i의 점프가 parent_v 및 v 사이의 간격을 덮도록 작동하지. 점프하는 동안 미리 계산 된 MaxParentEdge(v, i) 값을 사용하여 답변을 업데이트합니다.
MaxParentEdge(v, i) 및 Parent(v, i) 초기 문제에 대한 O(|E|log|V|) 솔루션으로 우리를 인도하는 O(log|V|)에 MaxEdge(p, q) 작품, 미리 계산 된 것을 고려. T에 속하지 않는 모든 가장자리를 반복하고 각각에 대해 W(e) - MaxEdge(p, q)을 계산하면됩니다.
psedocode를 추가 할 수 있다면 더 적절하고 사람들이 쉽게 대답을 이해할 수 있습니다. – arunmoezhi
이유가 무엇인지 자세히 설명해 주시겠습니까? – Math