最小生成樹Kruskal算法:首先對邊的權(quán)值進(jìn)行從小到大排列旦装，每次從剩余的邊中選擇權(quán)值較小且邊的兩個頂點(diǎn)不在
同一個集合內(nèi)的邊（就是不會產(chǎn)生回路的邊）锁保，加到生成樹中禁偎，直到加入的邊為n-1為止
時間復(fù)雜度：m 邊數(shù) n頂點(diǎn)數(shù) 對邊進(jìn)行快速排序是O(MlogM) 在m條邊中選擇n-1條邊的是O(MlogN); 故時間
復(fù)雜度為O(MlogM + MlogN);通常M比N大很多杀怠，故時間復(fù)雜度為O(MlogM);
#pragma mark - - 最小生成樹 Kruskal 算法
struct edge {
int u; // 頂點(diǎn)
int v; // 頂點(diǎn)
int w; // 權(quán)值
};
struct edge e[10];
void quicksort(int left,int right) {
if (left>right) {
return ;
}
int I=left;
int j=right;
int temp = e[left].w; //基準(zhǔn)數(shù)
struct edge t;
while (i!=j) {
// 從右往左找 直到找到一個小于基準(zhǔn)數(shù) 停下
while (e[j].w >= temp && i<j) {
j--;
}
// 從左往右找 直到找到一個大于基準(zhǔn)數(shù) 停下
while (e[i].w <= temp && i<j) {
I++;
}
// 如果不相等
if (i<j) {
//交換
t =e[I];
e[i] =e[j];
e[j] = t;
}
}
// 相等 基準(zhǔn)數(shù)歸位 將left 和 i交換
t = e[left];
e[left] = e[I];
e[i] = t;
quicksort(left, i-1); // 繼續(xù)處理左邊的
quicksort(i+1, right); // 繼續(xù)處理右邊的
}
// 并查集尋找祖先 函數(shù)
int getf(int v, int f[]) {
if (f[v] == v) {
return v;
}else {
// 路徑壓縮
f[v] = getf(f[v], f);
return f[v];
}
}
int merge(int v,int u,int f[]) {
int t1;
int t2;
t1 = getf(v, f);
t2 = getf(u, f);
if (t1!=t2) {
f[t2] =t1;
return 1;
}
return 0;
}
-(void)test1 {
int s[10][3] = {{0,0,0},{2,4,11},{3,5,13},{4,6,3},{5,6,4},{2,3,6},{4,5,7},{1,2,1},{3,4,9},{1,3,2}};
int m=9;
int n=6;
// 初始化 邊數(shù)據(jù)
for (int i=1; i<=m; i++) {
struct edge t;
t.u = s[i][0];
t.v = s[i][1];
t.w = s[i][2];
e[i] = t;
}
// 快速排序 邊數(shù)據(jù)
quicksort(1, m);
// 初始化 并查集
int f[10];
for (int i=1; i<=n; i++) {
f[i] = I;
}
//Kruskal算法 核心
int sum=0;
int count=0;
// 從小到大 枚舉每一條邊
for (int i=1; i<=m; i++) {
if (merge(e[i].u, e[i].v, f)) {
count ++;
sum += e[i].w;
printf("{%d,%d,%d} ",e[i].u,e[i].v,e[i].w);
}
if (count==n-1) {
break ;
}
}
printf("\n\n%d\n\n",sum);
}
Prim 算法:
1.從任意一個頂點(diǎn)開始構(gòu)造樹恕汇，假設(shè)從頂點(diǎn)1開始零酪。首先將頂點(diǎn)1加入生成樹中冒嫡，用一個一維數(shù)組Book來標(biāo)記哪些頂點(diǎn)
已經(jīng)加入生成樹
2.用數(shù)組dis記錄生成樹到各個頂點(diǎn)的距離。最初生成樹中只有1個頂點(diǎn)四苇。有直連邊時，數(shù)組dis中存儲的就是1號頂點(diǎn)
到該頂點(diǎn)的邊的權(quán)值方咆，沒有直連邊的時候就是無窮大月腋，即初始化dis數(shù)組
3.從數(shù)組dis中選出離生成樹最近的頂點(diǎn)（假設(shè)這個頂點(diǎn)為j）加入到生成樹中（Book[j]==1）。然后以j為中間點(diǎn)瓣赂，
更新生成樹到每一個非樹頂點(diǎn)的距離（松弛）榆骚，即如果dis[k] > e[j][k]則更新為dis[k]=e[j][k](j在生成樹
中，e[j][k]就是表示非樹頂點(diǎn)k到生成樹的以j為中間點(diǎn)的距離煌集，dis[k]表示非樹頂點(diǎn)k到生成樹的以其他頂點(diǎn)(
頂點(diǎn)j除外)為中間點(diǎn)的最短距離)
4.重復(fù)上述操作妓肢，直到生成樹中有n個頂點(diǎn)為止~
#pragma mark - - 最小生成樹 Prim 算法 (DJP算法)
-(void)test2 {
int s[10][3] = {{0,0,0},{2,4,11},{3,5,13},{4,6,3},{5,6,4},{2,3,6},{4,5,7},{1,2,1},{3,4,9},{1,3,2}};
int m=9;
int n=6;
int z[10][10];
int inf =9999;
// 初始化 邊數(shù)據(jù)
for (int i=0; i<10; i++) {
for (int j=0; j<10; j++) {
if (i==j) {
z[i][j] =0;
}else {
z[i][j] =inf;
}
}
}
for (int i=1; i<=m; i++) {
int s1 = s[i][0];
int s2 = s[i][1];
int s3 = s[i][2];
// 無向圖
z[s1][s2] = s3;
z[s2][s1] = s3;
}
// 初始化化 dis數(shù)組
int dis[10];
for (int i=0; i<10; i++) {
dis[i] = 9999;
}
// 初始化book數(shù)組 標(biāo)記一個頂點(diǎn)是否已經(jīng)加入到生成樹
int book[10] = {0};
// 假設(shè)從頂點(diǎn)1開始
dis[1] =0;
// 記錄總距離
int sum=0;
// Prim算法 核心
for (int j=1; j<=n; j++) {
// 較小值
int min =inf;
// 較小點(diǎn)
int u=0;
// 找到最小值
for (int i=1; i<=n; i++) {
if (book[i]==0 && dis[i]<min) {
min = dis[I];
u=I;
}
}
book[u] =1;
sum+=dis[u];
// 掃描當(dāng)前頂點(diǎn)u所有邊 再以u為中間點(diǎn)，更新生成樹到每一個非樹頂點(diǎn)的距離
for (int k=1; k<=n; k++) {
if (dis[k] > z[u][k] && book[k]==0) {
dis[k] = z[u][k];
}
}
}
printf("\n最短距離為%d\n\n",sum);
}
優(yōu)化方向：
1.dis[]最小值 可以用堆排序
2.掃描當(dāng)前頂點(diǎn)u所有邊 再以u為中間點(diǎn)苫纤，更新生成樹到每一個非樹頂點(diǎn)的距離碉钠，這塊可以用鄰接表
#pragma mark - - 優(yōu)化 Prim 算法
int size=6;
int dis[7];
int h[7]; //保存堆數(shù)據(jù) h[i]=t 表示頂點(diǎn)t
int pos[7]; // pos用來存儲每個頂點(diǎn)在堆中的位置 pos[h[i]] = I;
int book[7]={0};
void siftdown(int i) {
int t=0;
int flag=0;
while (2*i<=size && flag == 0) {
if (dis[h[i]] > dis[h[2*i]]) {
t =2*I;
}else {
t = I;
}
if (1+2*i <= size) {
if (dis[h[t]] > dis[h[2*i+1]]) {
t =2*I+1;
}
}
if (t!=i) {
swap(t, i);
I=t;
}else {
flag=1;
}
}
}
void swap(int x, int y) {
int t = h[x];
h[x] = h[y];
h[y] = t;
// 同步更新 pos
t = pos[h[x]];
pos[h[x]] = pos[h[y]];
pos[h[y]] = t;
return;
}
// 從堆頂取出一個元素
int pop() {
int t;
t = h[1];
pos[t] =0;
h[1] = h[size];
pos[h[1]] = 1;
size --;
siftdown(1);
return t;
}
void siftup(int i) {
if (i==1) {
return ;
}
int flag=0;
while (i!=1 && flag == 0) {
if (dis[h[i]] < dis[h[i/2]]) {
swap(i, i/2);
}else {
flag =1;
}
i=I/2;
}
}
-(void)test3 {
int u[20],v[20],w[20];
int first[20],next[20];
int m=9;
int n=6;
int count=0;
int sum=0;
int inf=9999;
int s[10][3] = {{0,0,0},{2,4,11},{3,5,13},{4,6,3},{5,6,4},{2,3,6},{4,5,7},{1,2,1},{3,4,9},{1,3,2}};
for (int i=1; i<=m; i++) {
u[i] = s[i][0];
v[i] = s[i][1];
w[i] = s[i][2];
}
// 由于是無向圖 所以需要把所有邊反向再存儲一遍
for (int i=m+1; i<=2*m; i++) {
u[i] = v[i-m];
v[i] = u[i-m];
w[i] = w[i-m];
}
//初始化 first
for (int i=0; i<20; i++) {
first[i] = -1;
}
// 鄰接表
for (int i=1; i<=2*m; i++) {
next[i] = first[u[I]];
first[u[i]] = I;
}
// Prim 核心代碼
// 將1號點(diǎn)加入生成樹
book[1] =1;
count++;
// 初始化dis數(shù)組，這里是1號頂點(diǎn)到其余各個頂點(diǎn)的初始距離
for (int i=0; i<=n; i++) {
dis[i] = inf;
}
dis[1]=0;
int k=first[1];
while (k!=-1) {
dis[v[k]] = w[k];
k=next[k];
}
// 初始化堆
for (int i=1; i<=size; i++) {
h[i] =I;
pos[i] =I;
}
for (int i=size/2; i>=1; i--) {
siftdown(i);
}
//先彈出一個堆頂元素 因?yàn)榇藭r堆頂是1號頂點(diǎn)
pop();
while (count<n) {
int j=pop();
book[j]=1;
count++;
sum+=dis[j];
// 掃描當(dāng)前頂點(diǎn)j的所有的邊 再以j為中間頂點(diǎn) 進(jìn)行松弛
k =first[j];
while (k!=-1) {
if (book[v[k]]==0 && dis[v[k]] > w[k]) {
dis[v[k]] =w[k];
siftup(pos[v[k]]);
}
k=next[k];
}
}
printf("\n最短距離為%d\n\n",sum);
}
