`
狂盗一枝梅
  • 浏览: 17731 次
  • 性别: Icon_minigender_1
  • 来自: 青岛
社区版块
存档分类
最新评论

【数据结构】【图论】【最小生成树】Kruskal算法

阅读更多

一、Kruskal算法核心

  1. Kruskal算法和Prime算法一样也是计算最小生成树的一种算法。考虑问题的出发点: 为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小。
  2. 具体做法: 先构造一个只含 n 个顶点的子图 SG,然后从权值最小的边开始,若它的添加不使SG 中产生回路,则在 SG 上加上这条边,如此重复,直至加上 n-1 条边为止。
  3. 算法演示

 

 二、代码实现(Java版)

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

class Edge {
	int node1;
	int node2;
	int edgeValue;
}

class MySort implements Comparator<Edge> {
	public int compare(Edge o1, Edge o2) {
		return o1.edgeValue > o2.edgeValue ? 1 : -1;
	}

}

public class Kruskal {
	static final int maxNodeValue = (1 << 31) - 1;

	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		Set<Edge> edges = new TreeSet<Edge>(new MySort());
		Map<Integer, Integer> preNode = new HashMap<Integer, Integer>();
		while (scanner.hasNext()) {
			int edgeCounts = scanner.nextInt();
			for (int i = 0; i < edgeCounts; i++) {
				int node1 = scanner.nextInt();
				int node2 = scanner.nextInt();
				int edgeValue = scanner.nextInt();
				Edge oldEdge = findOldEdge(node1, node2, edges);
				if (oldEdge != null) {
					if (oldEdge.edgeValue > edgeValue) {
						Edge edge = new Edge();
						edge.edgeValue = edgeValue;
						edge.node1 = node1;
						edge.node2 = node2;
						edges.add(edge);
					}
				} else {
					Edge edge = new Edge();
					edge.edgeValue = edgeValue;
					edge.node1 = node1;
					edge.node2 = node2;
					edges.add(edge);
				}
			}
			int cost = kruskal(edges, preNode);
			System.out.println(cost);
			edges.clear();
			preNode.clear();
		}
	}

	private static Edge findOldEdge(int node1, int node2, Set<Edge> edges) {
		Iterator<Edge> iterator = edges.iterator();
		while (iterator.hasNext()) {
			Edge edge = iterator.next();
			if ((edge.node1 == node1 && edge.node2 == node2) || (edge.node1 == node2 && edge.node2 == node1)) {
				return edge;
			}
		}
		return null;
	}

	public static int findRootNode(Integer node, Map<Integer, Integer> preNode) {
		while (preNode.get(node) != null) {
			node = preNode.get(node);
		}
		return node;
	}

	public static int kruskal(Set<Edge> edges, Map<Integer, Integer> preNode) {
		Iterator<Edge> it = edges.iterator();
		int cost = 0;
		while (it.hasNext()) {
			Edge edge = it.next();
			int node1 = edge.node1;
			int node2 = edge.node2;
			int edgeValue = edge.edgeValue;
			int node1_parent=findRootNode(node1, preNode) ;
			int node2_parent=findRootNode(node2, preNode);
			if (node1_parent!=node2_parent) {
				preNode.put(node1_parent, node2_parent);
				cost += edgeValue;
			}
		}
		return cost;
	}
}

 三、测试用例

输入
11
1 2 19
1 5 14
1 7 18
2 3 5
2 4 7
2 5 12
3 4 3
4 5 8
4 6 21
5 7 16
6 7 27

输出
67

 拓扑图和算法筛选过程:


 四、ACM

题目链接:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2144
AC代码:

import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

class Edge {
	int node1;
	int node2;
	int edgeValue;
}

class MySort implements Comparator<Edge> {
	public int compare(Edge o1, Edge o2) {
		return o1.edgeValue > o2.edgeValue ? 1 : -1;
	}

}

public class Main{
	static final int maxNodeValue = (1 << 31) - 1;

	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		Set<Edge> edges = new TreeSet<Edge>(new MySort());
		Map<Integer, Integer> preNode = new HashMap<Integer, Integer>();
		while (scanner.hasNext()) {
			int nodeCounts = scanner.nextInt();
			int edgeCounts = scanner.nextInt();
			for (int i = 0; i < edgeCounts; i++) {
				int node1 = scanner.nextInt();
				int node2 = scanner.nextInt();
				int edgeValue = scanner.nextInt();
				Edge oldEdge = findOldEdge(node1, node2, edges);
				if (oldEdge != null) {
					if (oldEdge.edgeValue > edgeValue) {
						Edge edge = new Edge();
						edge.edgeValue = edgeValue;
						edge.node1 = node1;
						edge.node2 = node2;
						edges.add(edge);
					}
				} else {
					Edge edge = new Edge();
					edge.edgeValue = edgeValue;
					edge.node1 = node1;
					edge.node2 = node2;
					edges.add(edge);
				}
			}
			int cost = kruskal(edges, preNode);
			System.out.println(cost);
			edges.clear();
			preNode.clear();
		}
	}

	private static Edge findOldEdge(int node1, int node2, Set<Edge> edges) {
		Iterator<Edge> iterator = edges.iterator();
		while (iterator.hasNext()) {
			Edge edge = iterator.next();
			if ((edge.node1 == node1 && edge.node2 == node2) || (edge.node1 == node2 && edge.node2 == node1)) {
				return edge;
			}
		}
		return null;
	}

	public static int findRootNode(Integer node, Map<Integer, Integer> preNode) {
		while (preNode.get(node) != null) {
			node = preNode.get(node);
		}
		return node;
	}

	public static int kruskal(Set<Edge> edges, Map<Integer, Integer> preNode) {
		Iterator<Edge> it = edges.iterator();
		int cost = 0;
		while (it.hasNext()) {
			Edge edge = it.next();
			int node1 = edge.node1;
			int node2 = edge.node2;
			int edgeValue = edge.edgeValue;
			int node1_parent=findRootNode(node1, preNode) ;
			int node2_parent=findRootNode(node2, preNode);
			if (node1_parent!=node2_parent) {
				preNode.put(node1_parent, node2_parent);
				cost += edgeValue;
			}
		}
		return cost;
	}
}

        AC代码和上面的代码只有一点不同,那就是输入了节点的个数nodeCount,然而这个数在创建生成树的过程中并没有被使用到。
 

  • 大小: 393.5 KB
分享到:
评论

相关推荐

    数据结构课程设计报告最小生成树Kruskal算法

    数据结构课程设计报告最小生成树Kruskal算法 数据结构课程设计报告中,我们将使用Kruskal算法来生成最小生成树,该算法是图论中的一种经典算法,能够在给定的图中找到最小生成树。下面,我们将对Kruskal算法的实现...

    最小生成树kruskal算法

    ### 最小生成树Kruskal算法详解 #### 算法背景与定义 最小生成树(Minimum Spanning Tree,简称MST)是图论中的一个经典问题,涉及到在一个加权图中寻找一棵包含所有顶点的子图,使得这棵子图的总权重最小。在实际...

    最小生成树Kruskal算法

    最小生成树Kruskal算法 标题:最小生成树Kruskal算法 描述:java编写的最小生成树Kruskal算法,参考:算法设计和分析 标签:最小生成树 Kruskal算法 JAVA 知识点概述: 1. 最小生成树(Minimum Spanning Tree)...

    最小生成树kruskal算法并查集版+C语言实现

    最小生成树(Minimum Spanning Tree, MST)是图论中的一个重要概念,主要应用于网络设计、数据传输优化等领域。它寻找一个树形子图,包含了原图的所有顶点,并且所有边的权重之和尽可能小。Kruskal算法是一种求解...

    cpp-图论算法最小生成树Prim算法和Kruskal算法C实现

    本文将详细介绍两种经典算法来解决最小生成树问题:Prim算法和Kruskal算法,并以C语言实现为例进行讲解。 ### Prim算法 Prim算法是一种贪心算法,其基本思想是从一个初始节点开始,逐步添加最短的边,直到连接到...

    图论最小生成树Kruskal避圈算法

    用Kruskal避圈算法求最小生成树的源代码

    MATLAB源码集锦-最小生成树kruskal算法离散型优化问题代码

    MATLAB源码集锦中的"最小生成树kruskal算法离散型优化问题代码"很可能是对上述步骤的具体实现,包括读取输入、处理数据、执行Kruskal算法并显示结果。通过学习和理解这段代码,你可以更深入地了解Kruskal算法及其在...

    用Prim和Kruskal算法构造最小生成树

    ### 使用Prim和Kruskal算法构建最小生成树 在图论中,最小生成树(Minimum Spanning Tree, MST)是一个非常重要的概念。对于一个连通的无向图来说,如果存在一个子图,它包含原图的所有顶点,并且这些顶点通过边...

    数据结构最小生成树算法

    普利姆算法(Prim's Algorithm)和克鲁斯卡尔算法(Kruskal's Algorithm)是两种常用的求解最小生成树的方法。 1. **普利姆算法**: - 普利姆算法从一个起始顶点开始,逐步添加边,每次添加的边都是当前生成树与图...

    最小生成树Kruskal算法.zip,无向网的邻接矩阵生成最小生成树

    最小生成树Kruskal算法.exe文件则是编译后的可执行程序,用户可以直接运行该程序,输入合适的无向网数据,然后程序会计算并输出最小生成树的邻接矩阵。 总结来说,Kruskal算法是解决最小生成树问题的有效方法,通过...

    最小生成树Kruskal算法.pdf

    最小生成树Kruskal算法是图论中的一个经典算法,主要应用于寻找加权无向图的最小生成树。最小生成树是由原图的所有顶点组成的树形子图,且包含的边的权重之和最小。Kruskal算法是解决这个问题的一种有效方法。 1. *...

    最小生成树Kruskal算法_最小生成树_

    最小生成树是图论中的一个重要概念,用于解决网络中连接所有顶点的最经济路径问题。在实际应用中,例如城市间的公路建设、电力网络设计等,都需要找到一种方案,使得构建连接所有点的网络所需的资源(如距离、成本或...

    MATLAB源码集锦-最小生成树Kruskal算法代码

    Kruskal算法是一种经典的解决最小生成树问题的方法,由Joseph B. Kruskal在1956年提出。在MATLAB环境中实现Kruskal算法可以帮助我们更直观地理解和运用这一算法。 Kruskal算法的基本步骤如下: 1. **边的排序**:...

    Prim算法与Kruskal算法求最小生成树

    最小生成树是图论中的一个重要概念,用于寻找一个无向加权图的边集合,使得这些边连接了图中的所有顶点,同时整个边集合的总权重尽可能小。在这个问题中,Prim算法和Kruskal算法是两种常用的方法。 1. Prim算法: ...

    数据结构课程设计-最小生成树Kruskal算法.doc

    本次课程设计的核心是实现**最小生成树Kruskal算法**。该算法属于图论中的经典算法之一,主要用于解决带权图中的最小生成树问题。课程设计旨在让学生通过实践掌握Kruskal算法的工作原理及其应用,并学会如何运用合适...

    最小生成树Kruskal算法 (2).pdf

    最小生成树Kruskal算法是一种在加权无向图中寻找代价最小的树形子集的算法,这个子集包含了图中的所有顶点且没有形成环路。在本课程设计中,学生需要实现一个程序,该程序能创建带权重的图,并应用Kruskal算法找出该...

    最小生成树Kruskal算法.docx

    最小生成树Kruskal算法是图论中的一个经典算法,用于寻找给定加权无向图的边集合,这些边连接了所有顶点且总权重最小。Kruskal算法主要应用于网络设计、优化问题和数据结构中。在这个课程设计中,你将学习如何实现这...

    最小生成树Kruskal算法报告范本模板.pdf

    最小生成树Kruskal算法是图论中的一个重要算法,用于解决如何找到连接所有顶点的最经济的边集的问题,即在保证图连通性的前提下,使得这些边的总权重最小。本报告将深入探讨Kruskal算法的原理、实现、数据结构分析...

    最小生成树Kruskal算法报告范本模板.docx

    最小生成树Kruskal算法是图论中的一个重要概念,它在计算机科学,特别是网络优化问题中有着广泛应用。本文将深入探讨Kruskal算法的基本原理、数据结构分析以及调试与分析的过程。 1. 课程设计介绍 Kruskal算法是...

    Prim与Kruskal算法的最小生成树matlab实现

    在通信网理论作业3-最小生成树这个项目中,你可能会学习如何用MATLAB编写代码,实现Prim和Kruskal算法,并对给定的网络图数据进行最小生成树的构造。这将涉及到数据结构的设计、图的遍历以及最小生成树的验证等编程...

Global site tag (gtag.js) - Google Analytics