最小生成樹是指一個有 n 個結(jié)點的連通圖的生成樹是原圖的極小連通子圖,且包含原圖中的所有 n 個結(jié)點,并且有保持圖連通的最少的邊。
創(chuàng)新互聯(lián)堅持“要么做到,要么別承諾”的工作理念,服務(wù)領(lǐng)域包括:成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù),滿足客戶于互聯(lián)網(wǎng)時代的浦江網(wǎng)站設(shè)計、移動媒體設(shè)計的需求,幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴!Prim算法:圖論中的一種算法,可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中,不但包括了連通圖里的所有頂點(英語:Vertex (graph theory)),且其所有邊的權(quán)值之和亦為最小。該算法于1930年由捷克數(shù)學(xué)家沃伊捷赫·亞爾尼克(英語:Vojtěch Jarník)發(fā)現(xiàn);并在1957年由美國計算機(jī)科學(xué)家羅伯特·普里姆(英語:Robert C. Prim)獨立發(fā)現(xiàn);1959年,艾茲格·迪科斯徹再次發(fā)現(xiàn)了該算法。
思路:將結(jié)點分為標(biāo)記點和未標(biāo)記點,任取一個初始點作為標(biāo)記點,依次從未標(biāo)記點中找到里標(biāo)記點最短的一條路徑,并將該未標(biāo)記點納入標(biāo)記點內(nèi),依次重復(fù)執(zhí)行,直至所有點均為標(biāo)記點。
分析:
1、以0作為初始點,記為第一個標(biāo)記點。從未標(biāo)記點中尋找離0最近的一點1,將1納入標(biāo)記點。
2、再以0、1位對象,尋找離0或1最近的未標(biāo)記點2,將2納入標(biāo)記點。
3、同理,再以0、1、2為對象,尋找到未標(biāo)記點4。
4、依次類推,得到5。
5、最后一點3。
代碼實現(xiàn)(C語言):
#include#include#define N 10000
typedef struct Ver {
char id;
struct Ver *father;
int minLength;
int flag;//1 標(biāo)記,0未標(biāo)記
} Ver,*Vertex;
//初始化結(jié)構(gòu)體指針數(shù)組
void InitialVertex(Vertex vertex[]) {
//讓0作為初始點
vertex[0]=(Vertex)malloc(sizeof(Ver));
vertex[0]->id='0';
vertex[0]->father=NULL;
vertex[0]->minLength=0;//無所謂
vertex[0]->flag=1;
for(int i=1; i<6; i++) {
vertex[i]=(Vertex)malloc(sizeof(Ver));
vertex[i]->id=i+'0';
vertex[i]->minLength=N;
vertex[i]->flag=0;
}
return;
}
//尋找李標(biāo)記點最短的未標(biāo)記點
int FindVer(Vertex vertex[],int matrix[][6]) {
int M=10000;
int order;//接收未標(biāo)記點下標(biāo)
//遍歷未標(biāo)記點
for(int i=0; i<6; i++) {
if(vertex[i]->flag==0) {
//遍歷標(biāo)記點
for(int j=0; j<6; j++) {
if(vertex[j]->flag!=0) {
int all_p=matrix[i][j];
//尋找最短路徑
if(all_pfather=vertex[j];
vertex[i]->minLength=all_p;
order=i;
M=all_p;
}
}
}
}
}
return order;
}
//建立最小生成樹
void BuildMinTree(Vertex vertex[],int matrix[][6]) {
//一共要尋找5次
for(int i=0; i<5; i++) {
int order=FindVer(vertex,matrix);//接受未標(biāo)記點
vertex[order]->flag=1;//將未標(biāo)記點轉(zhuǎn)化為標(biāo)記點
printf("第%d次,選擇的結(jié)點為%c,路徑長度為%d,連接關(guān)系為(%c,%c)\n",i+1,vertex[order]->id,vertex[order]->minLength,vertex[order]->id,vertex[order]->father->id);
}
}
int main() {
int matrix[6][6]= {
{ N, 3, 5, N, N, N },
{ 3, N, 2, 7, 4, N },
{ 5, 2, N, N, 3, N },
{ N, 7, N, N, N, 2 },
{ N, 4, 3, N, N, 1 },
{ N, N, N, 2, 1, N }
};
Vertex vertex[6];
InitialVertex(vertex);
BuildMinTree(vertex,matrix);
return 0;
}
代碼實現(xiàn)(Java):
import java.util.ArrayList;
import java.util.List;
public class Prim {
final static int N = 10000;
static int[][] matrix = new int[6][6];
public static void main(String[] args) {
// TODO Auto-generated method stub
matrix[0] = new int[] { N, 3, 5, N, N, N };
matrix[1] = new int[] { 3, N, 2, 7, 4, N };
matrix[2] = new int[] { 5, 2, N, N, 3, N };
matrix[3] = new int[] { N, 7, N, N, N, 2 };
matrix[4] = new int[] { N, 4, 3, N, N, 1 };
matrix[5] = new int[] { N, N, N, 2, 1, N };
// 建立標(biāo)記點集合
Listmarked = new ArrayList();
// 默認(rèn)使0作為初始點
marked.add(new Vertexs(0, null, 0));
// 建立未標(biāo)記點集合
ListunMarked = new ArrayList();
// 將其他結(jié)點作為未標(biāo)記點添加到集合中
for (int i = 1; i<= 5; i++) {
unMarked.add(new Vertexs(i, null, N));
}
int count=1;
//將未標(biāo)記點集合中的點轉(zhuǎn)移到已標(biāo)記點集合
while (!unMarked.isEmpty()) {
Vertexs ver = findVer(marked, unMarked);
marked.add(ver);
unMarked.remove(ver);
System.out.println("第"+(count++)+"次,選擇的結(jié)點為"+ver.id+",路徑長度為"+ver.minLength+",連接關(guān)系為("+ver.father.id+","+ver.id+")");
}
}
public static Vertexs findVer(Listmarked, ListunMarked) {
int M = 10000;
Vertexs v = null;
for (Vertexs ve : unMarked) {
for (Vertexs vr : marked) {
int all_p = matrix[vr.id][ve.id];
if (all_p< M) {
ve.minLength = all_p;
ve.father = vr;
M=all_p;
v=ve;
}
}
}
return v;
}
}
class Vertexs {
public int id;
public Vertexs father;
public int minLength = 10000;
public Vertexs(int id, Vertexs father, int minLength) {
this.id = id;
this.father = father;
this.minLength = minLength;
}
}
一言:
不是每一場雨都有彩虹,但是晴天總會到來。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級服務(wù)器適合批量采購,新人活動首月15元起,快前往官網(wǎng)查看詳情吧