primAlgorithm普利姆算法

背景

• 修路问题（最短路径）

代码实现（Java）

package test01;

import java.util.Arrays;


/*
 * 普利姆算法解决修路最短路径的问题
 * 满足条件为：
 * 1要把所有的地点都连接，总有一条路径我能到另外一个地点
 * 2要求总的连接路径长度最短
 * 算法基本思路：最小生成树
 * 选择一个起始点，开始搜索，选择路径最短的连接，然后标记已连接的点。下次选择从已标记的点的相邻点出发
 * 选择最短的路径，循环此过程，直到全部点遍历完。
 */
public class primeAlgorithm {
	public static void main(String args[]) {
		char[] data = new char[] {'A','B','C','D','E','F','G'};
		//矩阵中的100代表两点之间无法直接到达
		int[][] weight=new int[][] {
			
			{100,5,7,100,100,100,2},
			{5,100,100,9,100,100,3},
			{7,100,100,100,8,100,100},
			{100,9,100,100,100,4,100},
			{100,100,8,100,100,5,4},
			{100,100,100,4,5,100,6},
			{2,3,100,100,4,6,100},
		};
		int verxs=data.length;
		MGraph graph=new MGraph(verxs);
		MinTree minTree=new MinTree();
		minTree.creatGraph(graph, verxs, data, weight);
		minTree.showGraph(graph);
		minTree.prim(graph, 0);
	}
	
}
class MinTree{
	//创建图的临接矩阵
	/*
	 * graph: 图对象
	 * verxs：图的质点个数
	 * data： 图中各质点的值
	 * weight：图的邻接矩阵
	 */
	public void creatGraph(MGraph graph,int verxs,char data[],int[][] weight) {
		int i,j;
		for(i=0;i<verxs;i++) {
			graph.data[i]=data[i];
			for(j=0;j<verxs;j++) {
				graph.weight[i][j]=weight[i][j];
			}
				
		}
	}
	public void showGraph(MGraph graph) {
		for(int[] link:graph.weight) {
			System.out.println(Arrays.toString(link));
			
		}
	}
	public void prim(MGraph graph,int v) {
		int visited[]=new int[graph.verxs];
		//java中默认int数组元素为0；否则就要人为for循环遍历
		visited[v]=1;
		//起始点为1，因为已经遍历。
		int h1 = -1;
		int h2 = -1;
		int minWeight = 10000;//存储一个大值，后面遍历过程会被替代
		for(int k=1;k<graph.verxs;k++) {
			//因为至少要有verxs-1条边，所以寻找verxs-1次
			
			//遍历已经访问过的结点
			for(int i = 0;i<graph.verxs;i++) {
				//遍历没有访问的结点
				for(int j=0;j<graph.verxs;j++) {
					if(visited[i]==1 && visited[j]==0 && graph.weight[i][j]<minWeight) {
						minWeight = graph.weight[i][j];
						//寻找访问过程中长度最小的邻边，替换minweight
						h1=i;//记录访问起点
						h2=j;//记录访问终点
						
						
					}
				}
			}
		System.out.println("边<"+graph.data[h1]+","+graph.data[h2]+">权值："+minWeight);
		//将已经访问的结点进行标记visited值为1
		visited[h2]=1;
		minWeight=10000;
		
		}
		
	}
}
class MGraph{
	int verxs;//图结点个数
	char[] data;//存放结点的数据ABCDEFG
	int[][] weight;//存放边的长度，即为相邻的矩阵
	public MGraph(int verxs) {
		this.verxs=verxs;

		data = new char[verxs];		//用来存放地点的名称
		weight = new int[verxs][verxs];
		//用来定义边的长度，如果不相邻就定义为无穷大或者其他大数
		
	}
	
}