kruskal演算法復雜度

A. 最小生成樹 普里姆演算法和克魯斯卡爾演算法

kruskal演算法的時間復雜度主要由排序方法決定，其排序演算法只與帶權邊的個數有關，與圖中頂點的個數無關，當使用時間復雜度為O（eloge）的排序演算法時，克魯斯卡演算法的時間復雜度即為O（eloge），因此當帶權圖的頂點個數較多而邊的條數較少時，使用克魯斯卡爾演算法構造最小生成樹效果最好！

克魯斯卡爾演算法
假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，則按照克魯斯卡爾演算法構造最小生成樹的過程為：先構造一個只含 n 個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n 棵樹的一個森林。之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。

普里姆演算法
假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，TV 是 WN 上最小生成樹中頂點的集合，TE 是最小生成樹中邊的集合。顯然，在演算法執行結束時，TV=V，而 TE 是 E 的一個子集。在演算法開始執行時，TE 為空集，TV 中只有一個頂點，因此，按普里姆演算法構造最小生成樹的過程為：在所有「其一個頂點已經落在生成樹上，而另一個頂點尚未落在生成樹上」的邊中取一條權值為最小的邊，逐條加在生成樹上，直至生成樹中含有 n-1條邊為止。
--以上傳自http://hi..com/valyanprogramming/blog/item/1bc960e6095f9726b93820d9.html

1.Kruskal
//題目地址:http://acm.pku.e.cn/JudgeOnline/problem?id=1258

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e[10000];//定義邊集
int cmp(const void *a,const void *b)//快排比較函數
{
return ((node*)a)->len-((node*)b)->len;
}
int v[100],a[100][100];//v為點集
void makeset(int n)
{
for(int i=0;i<n;i++)
v[i]=i;
}
int find(int x)
{
int h=x;
while(h!=v[h])
h=v[h];
return h;
}
int main()
{
int n,i,j,r1,r2,p,total;
while(scanf("%d",&n)!=EOF)
{
p=0;
total=0;
makeset(n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
e[p].v1=i;
e[p].v2=j;
e[p].len=a[i][j];
p++;
}
}
qsort(e,p,sizeof(e[0]),cmp);
for(i=0;i<p;i++)
{
r1=find(e[i].v1);
r2=find(e[i].v2);
if(r1!=r2)
{
total+=e[i].len;
v[r1]=r2;
}
}
printf("%d\n",total);
}
system("pause");
return 0;
}

2.Prim
//題目地址同上

#include <iostream>
using namespace std;

#define M 101
#define maxnum 100001
int dis[M][M];

int prim(int n)
{
bool used[M]={};
int d[M],i,j,k;
for(i=1; i<=n; i++)
d[i] = dis[1][i];
used[1] = true;
int sum=0;
for(i=1; i<n; i++){
int temp=maxnum;
for(j=1; j<=n; j++){
if( !used[j] && d[j]<temp ){
temp = d[j];
k = j;
}
}
used[k] = true;
sum += d[k];
for(j=1; j<=n; j++){
if( !used[j] && dis[k][j]<d[j] )
d[j] = dis[k][j]; // 與Dijksta演算法的差別之處
}
}
return sum;
}

int main()
{
int n,i,j;
while( cin>>n ){

for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d",&dis[i][j]);
if( !dis[i][j] )
dis[i][j] = maxnum;
}
}

cout<<prim(n)<<endl;
}
return 0;
}

代碼來自網路

B. 求最小生成樹 利用Kruskal演算法求圖G的一棵最小生成樹T，用c語言

#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 並查集存儲結構
// Tags: 值為-1則表示為根節點
struct DisjointSet
{
int *arr;// 值為父節點下標
int number;// arr元素個數
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化並查集結構
// Input: number - 元素的個數
// Output:s - number個元素自成一集的並查集
void InitSet(DisjointSet &s, int number)
{
s.number = number;
s.arr = new int[number];
memset(s.arr, -1, sizeof(int) * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 刪除並查集結構
// Input: s - 並查集存儲結構
// Output:s - 回收內存後的結構
void FreeSet(DisjointSet &s)
{
if (s.arr)
{
delete []s.arr;
s.number = 0;
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 獲得某個結點的根節點
// Input: s - 並查集; index - 結點下標
// Output: return - 根節點下標
int GetRoot(DisjointSet &s, int index)
{
while (s.arr[index] != -1)
index = s.arr[index];

return index;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 合並index1和index2所在的兩個集合
// Input: index1 - 結點1下標, index2 - 結點2下標
// Output: s - 並查集
void Union(DisjointSet &s, int index1, int index2)
{
int root1 = GetRoot(s, index1);
int root2 = GetRoot(s, index2);

s.arr[root1] = root2;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 判斷兩個結點是否在同一個集合中
// Input: s - 並查集, index1 - 結點1下標, index2 - 結點2下標
// Output: return - true: 在 false: 不在
bool Find(DisjointSet &s, int index1, int index2)
{
return GetRoot(s, index1) == GetRoot(s, index2);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 圖的鄰接矩陣
struct Graph
{
int **value;// 權值,-1表示無法到達
int number;
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化一個圖
// Input: g - 圖的存儲結構, number - 結點個數
// Output: g - 圖
void InitGraph(Graph &g, int number)
{
int i = 0;

g.value = new int *[number];
for (i = 0; i < number; i++)
g.value[i] = new int[number];

g.number = number;
memset(*g.value, -1, sizeof(int) * number * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 回收一個圖
// Input: g - 圖, number - 結點個數
// Output: g - 圖的存儲結構
void FreeGraph(Graph &g)
{
int i = 0;

for (i = 0; i < g.number; i++)
delete []g.value[i];

delete []g.value;

g.value = 0;
g.number = 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 為圖在a，b間添加一條邊
// Input:e1, e2 - 兩個結點, value - 權值
// Output: graph - 加邊後的圖
void AddEdge(Graph &graph, int e1, int e2, int value)
{
graph.value[e1][e2] =value;
graph.value[e2][e1] = value;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 顯示一條邊
struct OneEdge
{
OneEdge(int _a = 0, int _b = 0, int _value = 0):
a(_a), b(_b), value(_value){}

int a, b;// 邊的兩個結點
int value; // 邊的權值
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 根據權值判斷兩個邊的大小
// Tags: 由於priority_queue是最大堆，所以這里小於號變成大於號，從而使priority_queue變成最小堆
bool operator <(OneEdge e1, OneEdge e2)
{
if (e1.value > e2.value) return true;
else return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用戶輸入圖的邊
// Input: n - 加邊的個數
// Output: graph - 加邊後的圖
// Tags: Console下用戶輸入點對(a, b, v)
void InputEdge(Graph &graph, int n)
{
int i = 0, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d %d %d", &a, &b, &v);
AddEdge(graph, a, b, v);
}
}

int main()
{
const int NODE_NUMBER = 6;
const int EDGE_NUMBER = 9;

Graph graph;// 圖
DisjointSet set;// 並查集
priority_queue<OneEdge> edge;// 2叉堆

InitGraph(graph, NODE_NUMBER);// 初始化圖
InputEdge(graph, EDGE_NUMBER);
InitSet(set, NODE_NUMBER); // 初始化並查集

int i = 0, j = 0;// 初始化堆
for (i = 0; i < NODE_NUMBER; i++)
for (j = i; j < NODE_NUMBER; j++)
if (graph.value[i][j] > 0)
edge.push(OneEdge(i, j, graph.value[i][j]));

int min_pay = 0;// 最小耗費值
int add_num = 0;// 已經添加了幾個邊
OneEdge min_value_edge;// 當前權值最小邊

while (add_num < NODE_NUMBER - 1)
{
min_value_edge = edge.top();
// 這里是因為了STL中2叉堆的結構中有一個緩沖區
// 需要將緩沖區中的每一個元素彈出來
if(min_value_edge.value > 0 && !Find(set, min_value_edge.a, min_value_edge.b))
{
Union(set, min_value_edge.a, min_value_edge.b);
min_pay += min_value_edge.value;
add_num++;
}
edge.pop();
}

printf("%d", min_pay);
return 0;
}

這個是c++語言的，最小權值存儲在min_pay中，樹存儲在並查集set中，且在獲取最小權值路徑的時候用了STL中的2叉堆，演算法復雜度為O(|V| * lgE)
不知是否滿足您的要求

C. kruskal演算法的舉例描述

克魯斯卡爾演算法(Kruskal's algorithm)是兩個經典的最小生成樹演算法的較為簡單理解的一個。這裡面充分體現了貪心演算法的精髓。大致的流程可以用一個圖來表示。這里的圖的選擇借用了Wikipedia上的那個。非常清晰且直觀。
首先第一步，我們有一張圖，有若干點和邊
第一步我們要做的事情就是將所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這里再次體現了貪心演算法的思想。資源排序，對局部最優的資源進行選擇。
排序完成後，我們率先選擇了邊AD。這樣我們的圖就變成了
.
.
.
.
.
.
第二步，在剩下的邊中尋找。我們找到了CE。這里邊的權重也是5
.
.
.
.
.
.
依次類推我們找到了6,7,7。完成之後，圖變成了這個樣子。
.
.
.
.
.
.
下一步就是關鍵了。下面選擇那條邊呢？ BC或者EF嗎？都不是，盡管現在長度為8的邊是最小的未選擇的邊。但是他們已經連通了（對於BC可以通過CE,EB來連接，類似的EF可以通過EB,BA,AD,DF來接連）。所以我們不需要選擇他們。類似的BD也已經連通了（這里上圖的連通線用紅色表示了）。
最後就剩下EG和FG了。當然我們選擇了EG。最後成功的圖就是下圖：
.
.
.
.
.
.
到這里所有的邊點都已經連通了，一個最小生成樹構建完成。
Kruskal演算法的時間復雜度由排序演算法決定，若採用快排則時間復雜度為O(N log N)。

D. 克魯斯卡爾演算法的時間復雜度為多少

時間復雜度為O(|E|log|E|)，其中E和V分別是圖的邊集和點集。

基本思想是先構造一個只含 n 個頂點、而邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結點，之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹。

反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n-1 條邊為止。

(4)kruskal演算法復雜度擴展閱讀：

克魯斯卡爾演算法證明

假設G=(V,E) 是一個具有n個頂點的連通網，T=(U,TE)是G的最小生成樹，U的初值等於V，即包含有G中的全部頂點，TE的初值為空集。該演算法的基本思想是：將圖G中的邊按權值從小到大的順序依次選取。

若選取的邊使生成樹T不形成迴路，則把它並入TE中，保留作為T的一條邊，若選取的邊使生成樹T形成迴路，則將其舍棄，如此進行下去直到TE中包含n-1條邊為止，此時的T即為最小生成樹。

克魯斯卡爾演算法，至多對e條邊各掃描一次，每次選擇最小代價的邊僅需要O(loge)的時間。因此，克魯斯卡爾演算法的時間復雜度為O(eloge)。

E. prim演算法與kruskal演算法時間復雜度哪個小

令到圖中所有節點都連通的最小代價.就是最小生成樹
簡單點說
有幾個城市
你要設計一個路線 這個路線能走完所有的這幾個城市 而且路程最短
這個路線就是最小生成樹的含義

F. Kruskal(pascal)

這是不用並查集的版本

var
x:array[1..100,1..3] of integer;
n,xlen:integer;
s:longint;
procere init;
var i,j,t,k:integer;
begin
fillchar(x,sizeof(x),0);
assign(input,'prim.txt');
reset(input);
readln(n);k:=0;
for i:=1 to n do
begin
for j:=1 to i do
begin
read(t);
if t>0 then
begin inc(k);x[k,1]:=i;x[k,2]:=j;x[k,3]:=t;end;
end;
for j:=i+1 to n do
read(t);
end;
close(input);
xlen:=k;
for i:=1 to xlen-1 do
begin
k:=i;
for j:=i+1 to xlen do
if x[j,3]<x[k,3] then
k:=j;
t:=x[i,1];x[i,1]:=x[k,1];x[k,1]:=t;
t:=x[i,2];x[i,2]:=x[k,2];x[k,2]:=t;
t:=x[i,3];x[i,3]:=x[k,3];x[k,3]:=t;
end;
end;
procere main;
var
y:array[1..100] of set of 0..255;
i,j:integer;
p1,p2:integer;
begin
for i:=1 to xlen do
y[i]:=[];
for i:=1 to xlen do
begin
p1:=0;p2:=0;
for j:=1 to xlen do
begin
if p1=0 then
if x[i,1] in y[j] then
p1:=j;
if p2=0 then
if x[i,2] in y[j] then
p2:=j;
end;
if p1+p2=0 then
begin y[i]:=[x[i,1]]+[x[i,2]];s:=s+x[i,3];end;
if (p1>0) and (p2=0) then
begin y[p1]:=y[p1]+[x[i,2]];s:=s+x[i,3];end;
if (p1=0) and (p2>0) then
begin y[p2]:=y[p2]+[x[i,1]];s:=s+x[i,3];end;
if (p1>0) and (p2>0) and (p1<>p2) then
begin y[p1]:=y[p1]+y[p2];y[p2]:=[];s:=s+x[i,3];end;

end;
end;
begin
init;
main;
writeln(s);
end.

G. Prim演算法和Kruskal演算法的空間復雜度

O(n^2)

H. 含有n個頂點e條邊的無向連通圖,利用Kruskal演算法生成最小生成樹，其時間復雜度為多少

O（nloge）

I. Kruskal演算法和Prim演算法構造它的一棵最小代價生成樹的過程

Prim演算法復雜度：O(n2), 與邊無關，適合求邊稠密的網的最小生成樹。

演算法思想：假設N={V,{E}}是連通網，TE是N上最小生成樹中邊的集合。演算法從U={u0},TE ={}開始，重復執行下述操作：在所有u∈U,v∈V-U的邊（u，v）∈E中找一條代價最小的邊（u0,v0）並入集合TE，同時v0並入U，直至U=V為止。

Kruskal演算法復雜度：O(eloge)，相對於Prim而言，適合求邊稀疏的網的最小生成樹。

演算法思想：最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=(V,{})，圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則捨去次邊而選擇下一條代價最小的邊。直至T中所有頂點都在同一連通分量上為止。