快捷導(dǎo)航

Java語言基于無向有權(quán)圖實(shí)現(xiàn)克魯斯卡爾算法代碼示例

更新時(shí)間：2017年11月24日 14:58:40 作者：Coder_py

這篇文章主要介紹了Java語言基于無向有權(quán)圖實(shí)現(xiàn)克魯斯卡爾算法代碼示例，具有一定參考價(jià)值，需要的朋友可以了解下。

所謂有權(quán)圖，就是圖中的每一條邊上都會(huì)有相應(yīng)的一個(gè)或一組值。通常情況下，這個(gè)值只是一個(gè)數(shù)字

如：在交通運(yùn)輸網(wǎng)中，邊上的權(quán)值可能表示的是路程，也可能表示的是運(yùn)輸費(fèi)用（顯然二者都是數(shù)字）。不過，邊上的權(quán)值也有可能是其它東西，比如說是一個(gè)字符串，甚至是一個(gè)更加復(fù)雜的數(shù)據(jù)包，里面集合了更多的數(shù)據(jù)

克魯斯卡爾算法的核心思想是：在帶權(quán)連通圖中，不斷地在邊集合中找到最小的邊，如果該邊滿足得到最小生成樹的條件，就將其構(gòu)造，直到最后得到一顆最小生成樹。

克魯斯卡爾算法的執(zhí)行步驟：

第一步：在帶權(quán)連通圖中，將邊的權(quán)值排序；

第二步：判斷是否需要選擇這條邊（此時(shí)圖中的邊已按權(quán)值從小到大排好序）。判斷的依據(jù)是邊的兩個(gè)頂點(diǎn)是否已連通，如果連通則繼續(xù)下一條；如果不連通，那么就選擇使其連通。

第三步：循環(huán)第二步，直到圖中所有的頂點(diǎn)都在同一個(gè)連通分量中，即得到最小生成樹。

關(guān)于有權(quán)圖的實(shí)現(xiàn)，看如下實(shí)例：

Graph:

package kruskal;
public class Graph {
	final int max=100;
	/*
	 * 頂點(diǎn)節(jié)點(diǎn)
	 */
	public class VexNode{
		int adjvex;
		int data;
	}
	VexNode[] vexNodes;
	int[] thevexs;
	//頂點(diǎn)集合
	int[][] edges = new int[max][max];
	//邊集合
	/*
	 * 創(chuàng)建圖
	 */
	public void createGraph(Graph graph,int[][] A,int[] vexs) {
		thevexs=vexs;
		for (int i = 0; i < vexs.length; i++) {
			for (int j = 0; j < vexs.length; j++) {
				graph.edges[i][j] = A[i][j];
			}
		}
	}
	/*
	 * 輸出圖
	 */
	public void printGraph(Graph graph) {
		for (int i = 0; i < graph.thevexs.length; i++) {
			for (int j = 0; j < graph.thevexs.length; j++) {
				//沒有路徑則輸出/
				if (graph.edges[i][j]==-1) {
					System.out.printf("%4s","/");
				} else {
					System.out.printf("%4d",graph.edges[i][j]);
				}
			}
			System.out.println("\n");
		}
	}
}

算法：

package kruskal;
public class KruSkal {
	public class Edge{
		int start;
		int end;
		int weight;
	}
	public void SortEdge(Edge[] E,int e) {
		Edge temp;
		int j;
		for (int i = 0; i < e; i++) {
			temp=E[i];
			j=i-1;
			while (j>=0&&temp.weight<E[j].weight) {
				E[j+1] = E[j];
				j--;
			}
			E[j+1] = temp;
		}
	}
	public KruSkal(Graph graph) {
		int i,j,u1,v1,sn1,sn2,k;
		int[] vset = new int[100];
		Edge[] E = new Edge[100];
		k=0;
		for (i=0;i<graph.thevexs.length;i++) {
			for (j=0;j<=i;j++) {
				E[k] = new Edge();
				if (graph.edges[i][j]>0) {
					E[k].start=i;
					E[k].end=j;
					E[k].weight=graph.edges[i][j];
					k++;
				}
			}
		}
		SortEdge(E, k);
		for (i=0;i<graph.thevexs.length;i++) {
			vset[i]=i;
		}
		k=1;
		j=0;
		while (k<graph.thevexs.length) {
			u1=E[j].start;
			v1=E[j].end;
			sn1=vset[u1];
			sn2=vset[v1];
			if (sn1!=sn2) {
				System.out.printf("(%d,%d),權(quán)值：%d",u1,v1,E[j].weight);
				System.out.println("\n");
				k++;
				for (i=0;i<graph.thevexs.length;i++) {
					if (vset[i]==sn2) {
						vset[i]=sn1;
					}
				}
			}
			j++;
		}
	}
}

測(cè)試類：

package kruskal;
public class Test {
	public static void main(String[] args) {
		int[] vexs = {0,1,2,3,4};
		int[][] A = {
						{0,1,3,4,7},
						{1,0,2,-1,-1},
						{3,2,0,5,8},
						{4,-1,5,0,6},
						{7,-1,8,6,0}
				};
		Graph graph = new Graph();
		graph.createGraph(graph, A, vexs);
		graph.printGraph(graph);
		KruSkal kruSkal = new KruSkal(graph);
	}
}

總結(jié)

以上就是本文關(guān)于Java語言基于無向有權(quán)圖實(shí)現(xiàn)克魯斯卡爾算法代碼示例的全部內(nèi)容，希望對(duì)大家有所幫助。有什么問題可以隨時(shí)留言，小編盡力為您答復(fù)。

您可能感興趣的文章: