数据结构图Graph之最小生成树问题克鲁斯卡尔算法

Posted by Naah on Thursday, Aug 17,2017 11:31:07
  1.  算法准备

    a. Edge度对象数组(从小到大)

    b. 查询数组parent

    c. find方法(查找数组中该顶点能到达的最后位置)

  2. 算法思路

    a. 遍历edge数组

    b. 通过find方法取得edge对象头顶点的最后下标

    c. 通过find方法取得edge对象尾顶点的最后下标

    d. 如果头尾下标不相等

    e. 输出度的信息

    f. 将parent数组中头下标位置的值设置为尾下标

//
public class Graph<T extends Comparable<T>> {

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

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

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

	// 度数组
	private Edge[] edges;

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

	// 顶点数量
	private int size;

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

/**
	 * 最小生成树方法-克鲁斯卡尔算法
	 */
	public void kruskal() {

		// 创建查找数组
		// 该数组下标为顶点下边
		// 该数组值为顶点出度顶点下标
		int[] parent = new int[size];

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

		// 构建度数组
		createEdge();

		// 循环出度数组
		for (Edge edge : edges) {

			// 从查找数组中寻找该出度的头所到达的顶点下标
			int n = find(parent, edge.begin);

			// 从查找数组中寻找该出度的尾所到达的顶点下标
			int m = find(parent, edge.end);

			// 如果头尾顶点下标不相等,进入
			// 如果头尾顶点下标相对,则代表该度为多余度
			if (n != m) {

				// 输出该度信息
				System.out.println(
						edge.begin + "顶点---" + edge.end + "顶点:" + edge.weight);

				// 将查询数组中头下标的值设置为尾下标
				parent[n] = m;

				// 累计权值
				sum += edge.weight;
			}
		}

		// 输出权值
		System.out.println(sum);

	}

	/**
	 * 查找数组中该顶点能到达的最后位置
	 * @param parent 查找数组
	 * @param i 顶点下标
	 * @return 最后位置
	 */
	private int find(int[] parent, int i) {

		// 如果该下标位置有出度则循环
		while (parent[i] > 0) {

			// 将出度下标设置为下一次查找的下标
			i = parent[i];
		}

		// 返回最后位置
		return i;
	}
 * 构建度数组
	 */
	public void createEdge() {

		// 创建度的链表,不确定度的数量,所以使用链表
		List<Edge> edgeList = new LinkedList<Edge>();

		// 从第一个顶点开始构建度的链表
		createEdge(edgeList, 0);

		// 创建度的数组
		this.edges = new Edge[edgeList.size()];

		// 数组赋值标记
		int i = 0;

		// 遍历链表,添加到数组
		for (Edge edge : edgeList) {

			// 将链表值添加到数组
			this.edges[i] = edge;

			// 标记自增
			i++;
		}

		// 通过Edge类实现Comparable接口进行排序
		Arrays.sort(this.edges);
	}

	/**
	 * 构建度数组
	 *
	 * 此方法思路与广度优先相同
	 * 但是没有采用上面的递归广度优先思路
	 * 而是使用迭代完成
	 * @param edges 度的链表
	 * @param i 开始节点
	 */
	private void createEdge(List<Edge> edges, int i) {

		// 创建度的队列
		LinkedList<Integer> queue = new LinkedList<Integer>();

		// 将顶点下标添加到队列中
		queue.offer(i);

		// 队列不为空则循环
		while (!queue.isEmpty()) {

			// 取出队首顶点下标
			int n = queue.poll();

			// 取得顶点的第一个邻接点
			int m = getFirstNeighbor(n);

			// 当邻接点连接时循环
			while (m != NO_LINK) {

				// 是否包含度标记
				boolean isHave = false;

				// 遍历度链表
				for (Edge e : edges) {

					// 如果两节点相等
					if (e.equals(n, m, matrix[n][m])) {

						// 将标记设置为真
						isHave = true;
						break;
					}
				}

				// 当没有该度时
				if (!isHave) {

					// 向度链表中添加该度
					edges.add(new Edge(n, m, matrix[n][m]));

					// 将邻接点下标添加到队尾
					queue.offer(m);
				}

				// 得到m邻接点后的一个邻接点
				m = getNextNeighbor(n, m);
			}

		}

	}


/**
 *
 * ClassNameCh 度
 * ClassNameEn Edge
 * Description 度的数据结构
 * Company
 * @author Naah
 * @date 2017年8月14日 下午10:52:53
 */
class Edge implements Comparable<Edge> {

	// 度的头顶点下标
	int begin;

	// 度的尾顶点下标
	int end;

	// 度的权值
	int weight;

	public Edge() {
		super();
	}

	/**
	 * 构造函数
	 * @param begin 头顶点下标
	 * @param end 尾顶点下标
	 * @param weight 权值
	 */
	public Edge(int begin, int end, int weight) {
		super();
		this.begin = begin;
		this.end = end;
		this.weight = weight;
	}

	/**
	 * 判断相等方法
	 * @param begin
	 * @param end
	 * @param weight
	 * @return true/false
	 */
	public boolean equals(int begin, int end, int weight) {

		// 首先判断权值相等
		if (weight == this.weight) {

			// 判断下标是否相同,包括头尾互换
			if ((begin == this.begin && end == this.end)
					|| (end == this.begin && begin == this.end)) {

				// 返回相等
				return true;
			}

		}

		// 返回不相等
		return false;

	}

	@Override
	public String toString() {
		return "Edge [begin=" + begin + ", end=" + end + ", weight=" + weight
				+ "]";
	}

	/**
	 * 判断大小方法
	 * 以权值大小判断,为度数组的从小到大排序
	 */
	@Override
	public int compareTo(Edge o) {

		if (this.weight > o.weight) {
			return 1;
		} else if (this.weight < o.weight) {
			return -1;
		}
		return 0;
	}

}
 * 构建度数组
	 */
	public void createEdge() {

		// 创建度的链表,不确定度的数量,所以使用链表
		List<Edge> edgeList = new LinkedList<Edge>();

		// 从第一个顶点开始构建度的链表
		createEdge(edgeList, 0);

		// 创建度的数组
		this.edges = new Edge[edgeList.size()];

		// 数组赋值标记
		int i = 0;

		// 遍历链表,添加到数组
		for (Edge edge : edgeList) {

			// 将链表值添加到数组
			this.edges[i] = edge;

			// 标记自增
			i++;
		}

		// 通过Edge类实现Comparable接口进行排序
		Arrays.sort(this.edges);
	}

	/**
	 * 构建度数组
	 *
	 * 此方法思路与广度优先相同
	 * 但是没有采用上面的递归广度优先思路
	 * 而是使用迭代完成
	 * @param edges 度的链表
	 * @param i 开始节点
	 */
	private void createEdge(List<Edge> edges, int i) {

		// 创建度的队列
		LinkedList<Integer> queue = new LinkedList<Integer>();

		// 将顶点下标添加到队列中
		queue.offer(i);

		// 队列不为空则循环
		while (!queue.isEmpty()) {

			// 取出队首顶点下标
			int n = queue.poll();

			// 取得顶点的第一个邻接点
			int m = getFirstNeighbor(n);

			// 当邻接点连接时循环
			while (m != NO_LINK) {

				// 是否包含度标记
				boolean isHave = false;

				// 遍历度链表
				for (Edge e : edges) {

					// 如果两节点相等
					if (e.equals(n, m, matrix[n][m])) {

						// 将标记设置为真
						isHave = true;
						break;
					}
				}

				// 当没有该度时
				if (!isHave) {

					// 向度链表中添加该度
					edges.add(new Edge(n, m, matrix[n][m]));

					// 将邻接点下标添加到队尾
					queue.offer(m);
				}

				// 得到m邻接点后的一个邻接点
				m = getNextNeighbor(n, m);
			}

		}

	}

	/**



}
class Edge implements Comparable<Edge> {

	// 度的头顶点下标
	int begin;

	// 度的尾顶点下标
	int end;

	// 度的权值
	int weight;

	public Edge() {
		super();
	}

	/**
	 * 构造函数
	 * @param begin 头顶点下标
	 * @param end 尾顶点下标
	 * @param weight 权值
	 */
	public Edge(int begin, int end, int weight) {
		super();
		this.begin = begin;
		this.end = end;
		this.weight = weight;
	}

	/**
	 * 判断相等方法
	 * @param begin
	 * @param end
	 * @param weight
	 * @return true/false
	 */
	public boolean equals(int begin, int end, int weight) {

		// 首先判断权值相等
		if (weight == this.weight) {

			// 判断下标是否相同,包括头尾互换
			if ((begin == this.begin && end == this.end)
					|| (end == this.begin && begin == this.end)) {

				// 返回相等
				return true;
			}

		}

		// 返回不相等
		return false;

	}

	@Override
	public String toString() {
		return "Edge [begin=" + begin + ", end=" + end + ", weight=" + weight
				+ "]";
	}

	/**
	 * 判断大小方法
	 * 以权值大小判断,为度数组的从小到大排序
	 */
	@Override
	public int compareTo(Edge o) {

		if (this.weight > o.weight) {
			return 1;
		} else if (this.weight < o.weight) {
			return -1;
		}
		return 0;
	}

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

}