数据结构图Graph之最小生成树问题普里姆算法

Posted by Naah on Thursday, Aug 17,2017 11:25:46

一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。我们把构造连通网的最小代价生成树。称为最小生成树

 

通过邻接矩阵进行计算

  1.  算法准备

    a. 邻接矩阵

    b. 最小权值数组least

    c. 上一个顶点下标数组lastIndex

    d. 最小权值和sum

  2. 算法思路

    a. 将least数组初始化为邻接矩阵中第一个节点的出度数组

    b. 开始循环

    c. for循环least数组中最小的值,记录为min,并记录下标为minIndex

    d. 输出度的信息,累加min到sum

    e. for遍历minIndex数组中的权值

    f. Least数组中该位置不为0(未遍历过)并且权值比least数组中小

    g. 将该权值覆盖到least数组中的位置

    h.设置lastIndex该位置为minIndex

 

public class Graph> {

	// 顶点数组
	private T[] vertexs;

	// 邻接表元素数组
	private VertexNeighborNode[] neighborArray;

	// 邻接矩阵
	private int[][] matrix;

	// 泛型对象的类文件
	private Class Class;

	// 顶点数量
	private int size;

// 常亮:未连接
	public static final int NO_LINK = -1;

	/**
	 * 构造方法
	 * @param Class 类对象
	 * @param vertexs 顶点可选数组
	 */
	public Graph(Class<T> Class, T... vertexs) {
		super();
		this.vertexs = vertexs;
		this.size = vertexs.length;
		this.Class = Class;

	}

	/**
	 * 构造方法
	 * @param vertexs 可选数组
	 */
	public Graph(T... vertexs) {
		super();
		this.vertexs = vertexs;
		this.size = vertexs.length;

	}


	/**
	 * 得到邻接矩阵
	 * @return
	 */
	public int[][] getMatrix() {
		return matrix;
	}

	/**
	 * 设置邻接矩阵
	 * @param matrix 邻接矩阵
	 * @throws Exception 数组长度不对
	 */
	public void setMatrix(int[][] matrix) throws Exception {
		if (matrix.length != this.vertexs.length) {
			throw new Exception("二维数组长度不对");
		}
		for (int i = 0; i < matrix.length; i++) {
			if (matrix[i].length != this.vertexs.length) {
				throw new Exception("二维数组长度不对");
			}

		}
		this.matrix = matrix;
	}

/**
	 * 最小生成树方法-普里姆算法
	 *
	 */
	public void prim() {

		// 创建最小权值数组
		int[] least = new int[size];

		// 上一个顶点下标数组
		int[] lastIndex = new int[size];

		// 最小权值和
		int sum = 0;

		// 初始化最小权值数组
		for (int i = 0; i < least.length; i++) {
			least[i] = matrix[0][i];
		}

		// 循环查找最小生成树
		for (int i = 1; i < least.length; i++) {

			// 将最小权值设置为int最大值
			int min = Integer.MAX_VALUE;

			// 将最小权值下标设置为0
			int minIndex = 0;

			// 循环查找最小权值数组中的最小值
			for (int j = 1; j < least.length; j++) {

				// 大于0的最小权值
				if (least[j] > 0 && least[j] < min) {

					// 设置为最小值
					min = least[j];

					// 将当前下标设置为最小权值下标
					minIndex = j;
				}
			}

			// 输出已找到的最小顶点
			System.out.println(
					lastIndex[minIndex] + "顶点---" + minIndex + "顶点:" + min);

			// 将已找到的最小权值点设置为0,标记为已找到
			least[minIndex] = 0;

			// 将最小权值累加到最小权值和中
			sum += min;

			// 将上一个顶点的所有出度权值添加到最小权值数组中
			for (int j = 1; j < least.length; j++) {

				// 没遍历的顶点 并且 上一个顶点所到该顶点的权值 小于 最小权值数组中到该顶点的权值时 进入
				// 最小权值数组中无法到达的顶点 并且上一个顶点能到达该顶点时 进入
				if ((least[j] > 0 && matrix[minIndex][j] != NO_LINK
						&& matrix[minIndex][j] < least[j])
						|| (least[j] == NO_LINK
								&& matrix[minIndex][j] != NO_LINK)) {

					// 将上一个顶点到该顶点的出度权值添加到最小权值数组中
					least[j] = matrix[minIndex][j];

					// 将上一个顶点设置为该顶点的入度顶点
					lastIndex[j] = minIndex;
				}
			}

		}

		// 输出最小权值和
		System.out.println(sum);
	}


}