圖的鄰接矩陣表示法可參考：http://www.reibang.com/p/9f27288f6749
測試圖如圖所示：
測試圖.png
普里姆(Prim)算法
思想：先選取一個(gè)頂點(diǎn)加入最小生成樹郑象，再選取與該頂點(diǎn)相連的邊中的最小權(quán)值對(duì)應(yīng)的頂點(diǎn)加入生成樹抑进，將這兩個(gè)頂點(diǎn)作為一棵新的最小生成樹骂倘，繼續(xù)判斷與該樹相連的邊的最小權(quán)值對(duì)應(yīng)的頂點(diǎn)，并將其加入最小生成樹赏僧，直到所有頂點(diǎn)均加入生成樹為止大猛。
//最小生成樹--Prim算法
//每次都是從lowcost數(shù)組中選擇權(quán)值最小的邊加入生成樹
public void MiniSpanTree_Prim(MyGraph graph) {
int min, i, j, k;
//保存相關(guān)頂點(diǎn)下標(biāo)
int[] adjvex = new int[graph.getNumOfVertex()];
//保存相關(guān)頂點(diǎn)間邊的權(quán)值
int[] lowcost = new int[graph.getNumOfVertex()];
/**
* lowcost值為0時(shí)表示此下標(biāo)的頂點(diǎn)已經(jīng)加入最小生成樹,也就是將v0將入生成樹
* 因?yàn)樵摮绦蚰J(rèn)從0號(hào)下標(biāo)頂點(diǎn)開始建立最小生成樹，所以將lowcost初始化為0
* 但最小生成樹的建立并不一定需要從0號(hào)下標(biāo)頂點(diǎn)開始
**/
lowcost[0] = 0;
//初始化第一個(gè)頂點(diǎn)的下標(biāo)為0
adjvex[0] = 0;
for(i = 1; i < graph.getNumOfVertex(); i++) {
//將與v0頂點(diǎn)有邊的權(quán)值存入數(shù)組
lowcost[i] = edges[0][i];
//初始化都為v0的下標(biāo)
adjvex[i] = 0;
}
for(i = 1; i < graph.getNumOfVertex(); i++) {
//初始化最小權(quán)值淀零，一般設(shè)置為一個(gè)不可能的大數(shù)字挽绩，此處是65535
min = INF;
//j用來作為頂點(diǎn)下標(biāo)的循環(huán)變量；k用來存儲(chǔ)最小權(quán)值頂點(diǎn)的下標(biāo)
j = 1; k = 0;
while(j < graph.getNumOfVertex()) {
//如果權(quán)值不為0且權(quán)值小于min
if (lowcost[j] != 0 && lowcost[j] < min) {
//讓當(dāng)前權(quán)值稱為最小值
min = lowcost[j];
//將當(dāng)前最小值的下標(biāo)存入k
k = j;
}
j++;
}
//輸出當(dāng)前頂點(diǎn)邊中權(quán)值最小的邊
System.out.println("("+adjvex[k]+","+k+")");
//將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0驾中，表示此頂點(diǎn)已經(jīng)加入生成樹
lowcost[k] = 0;
for(j =1; j < graph.getNumOfVertex(); j++) {
//若下標(biāo)為k的頂點(diǎn)各邊權(quán)值小于此前這些頂點(diǎn)未被加入生成樹權(quán)值
if (lowcost[j] != 0 && edges[k][j] < lowcost[j]) {
//將較小權(quán)值存入lowcost
lowcost[j] = edges[k][j];
//將下標(biāo)為k的頂點(diǎn)存入adjvex
adjvex[j] = k;
}
}
}
}
測試程序
int n = 9;
String[] vertex = {"v0","v1","v2","v3","v4","v5","v6","v7","v8"};
MyGraph graph = new MyGraph(n);
for (String string : vertex) {
graph.insertVertex(string);
}
graph.insertEdge(0, 1, 10);
graph.insertEdge(0, 5, 11);
graph.insertEdge(1, 2, 18);
graph.insertEdge(1, 6, 16);
graph.insertEdge(1, 8, 12);
graph.insertEdge(2, 8, 8);
graph.insertEdge(2, 3, 22);
graph.insertEdge(3, 8, 21);
graph.insertEdge(3, 6, 24);
graph.insertEdge(3, 4, 20);
graph.insertEdge(3, 7, 16);
graph.insertEdge(4, 5, 26);
graph.insertEdge(4, 7, 7);
graph.insertEdge(5, 6, 17);
graph.insertEdge(6, 7, 19);
graph.MiniSpanTree_Prim(graph);
測試結(jié)果：
普里姆算法測試結(jié)果圖.png
克魯斯卡爾算法(Kruskal)
思想：將圖的存儲(chǔ)結(jié)構(gòu)使用邊集數(shù)組的形式表示唉堪，并將邊集數(shù)組按權(quán)值從小到大排序，遍歷邊集數(shù)組肩民，每次選取一條邊并判斷是否構(gòu)成環(huán)路唠亚，不會(huì)構(gòu)成環(huán)路則將其加入最小生成樹，最終只會(huì)包含n-1條邊(n為無向圖的頂點(diǎn)數(shù))持痰。
邊集數(shù)組的結(jié)構(gòu)如圖所示：
邊集數(shù)組結(jié)構(gòu)圖.png
邊集數(shù)組類
public class Edge implements Comparable<Edge> {
int begin;
int end;
int weight;
public int getBegin() {
return begin;
}
public void setBegin(int begin) {
this.begin = begin;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
//按權(quán)值升序排列
return this.weight - o.weight;
}
}
圖類
public class Graph {
private ArrayList<Object> vertexList; //存放頂點(diǎn)的數(shù)組
Edge[] edges; //邊集數(shù)組
int[][] arr; //鄰接矩陣
public Graph(int v, int e) {
//初始化結(jié)點(diǎn)數(shù)組
vertexList = new ArrayList<>(v);
//根據(jù)邊數(shù)初始化邊集數(shù)組
edges = new Edge[e];
//向邊集數(shù)組添加空對(duì)象
for(int i = 0; i < e; i++){
Edge edge = new Edge();
edges[i] = edge;
}
//初始化鄰接矩陣
arr = new int[v][v];
for (int i = 0; i < v; i++) {
for (int j = 0; j < v; j++) {
if (i == j)
arr[i][j] = 0;
else {
arr[j][i] = 65535;
}
}
}
}
//插入結(jié)點(diǎn)
public void insertVertex(Object vertex) {
vertexList.add(vertexList.size(),vertex);
}
//插入無向邊以及設(shè)置權(quán)值
public void insertEdge(int n1, int n2, int weight) {
arr[n1][n2] = weight;
//該圖為無向圖灶搜，所以矩陣關(guān)于對(duì)角線對(duì)稱
arr[n2][n1] = weight;
}
//獲取頂點(diǎn)個(gè)數(shù)
public int getNumOfVertex() {
return vertexList.size();
}
//獲取頂點(diǎn)n的值
public Object getValueByIndex(int n) {
return vertexList.get(n);
}
//鄰接矩陣轉(zhuǎn)換為邊集數(shù)組
public void MatrixToEdgesArray() {
int k = 0;
//因?yàn)樵搱D為無向圖，所以該矩陣關(guān)于從左上到右下的對(duì)角線對(duì)稱
//因此此處遍歷矩陣只需遍歷右上部分即可
for (int i = 0; i < getNumOfVertex(); i++) {
for (int j = i ; j < getNumOfVertex(); j++) {
if (arr[i][j] < 65535 && arr[i][j] != 0) {
edges[k].begin = i; // 編號(hào)較小的結(jié)點(diǎn)為首
edges[k].end = j; // 編號(hào)較大的結(jié)點(diǎn)為尾
edges[k].weight = arr[i][j];
k++;
}
}
}
//將edges邊集數(shù)組按權(quán)值從小到大排序
Arrays.sort(edges);
}
//最小生成樹--克魯斯卡爾算法
public void MiniSpanTree_Kruskal(Graph graph) {
int i, n, m;
//將鄰接矩陣轉(zhuǎn)換為邊集數(shù)組
MatrixToEdgesArray();
int[] parent = new int[edges.length];
//初始化parent數(shù)組,用于判斷是否產(chǎn)生了環(huán)路
for(i = 0; i < edges.length; i++) {
parent[i] = 0;
}
for(i = 0; i < edges.length; i++) {
//按權(quán)值從小到大拿到每一條邊
Edge edge = edges[i];
n = Find(parent,edge.begin);
m = Find(parent,edge.end);
//n==m時(shí)表示構(gòu)成了環(huán)路工窍，不能納入最小生成樹中
if (n != m) {
System.out.println("(" + edge.begin + "," + edge.end + ")-->" + edge.weight);
parent[n] = m;
}
}
}
public int Find(int[] parent, int f) {
/**當(dāng)i=7時(shí),parent數(shù)組為{1,5,8,7,7,8,0,0,6}
* 對(duì)應(yīng)的下標(biāo)為{0,1,2,3,4,5,6,7,8}
*parent[0] = 1表示頂點(diǎn)0,1已經(jīng)加入生成樹中
*所以此時(shí)頂點(diǎn)0,1,2,5,8,6在一個(gè)邊集合中;頂點(diǎn)3,4,7在一個(gè)邊集合中
**/
while(parent[f] > 0) {
f = parent[f];
}
return f;
}
}
測試程序：
int n = 9, e = 15;
String[] vertex = {"v0","v1","v2","v3","v4","v5","v6","v7","v8"};
Graph graph = new Graph(n,e);
for (String string : vertex) {
graph.insertVertex(string);
}
graph.insertEdge(0, 1, 10);
graph.insertEdge(0, 5, 11);
graph.insertEdge(1, 2, 18);
graph.insertEdge(1, 6, 16);
graph.insertEdge(1, 8, 12);
graph.insertEdge(2, 8, 8);
graph.insertEdge(2, 3, 22);
graph.insertEdge(3, 8, 21);
graph.insertEdge(3, 6, 24);
graph.insertEdge(3, 4, 20);
graph.insertEdge(3, 7, 16);
graph.insertEdge(4, 5, 26);
graph.insertEdge(4, 7, 7);
graph.insertEdge(5, 6, 17);
graph.insertEdge(6, 7, 19);
graph.MiniSpanTree_Kruskal(graph);
測試結(jié)果：
克魯斯卡爾算法測試結(jié)果圖.png
最小生成樹為：
最小生成樹.png
總結(jié)
普里姆算法針對(duì)頂點(diǎn)展開割卖，通過不斷尋找與已構(gòu)建的生成樹的最小邊來不斷構(gòu)建新的生成樹。普里姆算法對(duì)于稠密圖患雏，也就是邊數(shù)非常多的情況會(huì)更好一些鹏溯，因?yàn)槠涫峭ㄟ^頂點(diǎn)來展開的。算法時(shí)間損耗主要來源于嵌套的for循環(huán)纵苛，所以時(shí)間復(fù)雜度為O(n^2)剿涮。
克魯斯卡爾算法針對(duì)邊展開言津，通過對(duì)邊集數(shù)組的遍歷來構(gòu)建最小生成樹攻人，但是過程中必須避免構(gòu)成環(huán)路取试。克魯斯卡爾算法對(duì)于稀疏圖怀吻，也就是邊數(shù)較少的情況效率會(huì)很高瞬浓。此算法的Find函數(shù)由邊數(shù)e決定，時(shí)間復(fù)雜度為O(loge)蓬坡，再加上外層for循環(huán)的e次猿棉，所以時(shí)間復(fù)雜度為O(eloge)。
