实施Kruskalls算法当测试电路算法、电路、测试、Kruskalls
我试图写一个程序，将发现的最小生成树。但是有一个问题，我有这个算法，正在测试的电路。什么是做到这一点在Java中的最佳方式。
确定这里是我的code
进口java.io. *;
导入的java.util。*;
公共类JungleRoads
{
公共静态INT FindMinimumCost（ArrayList的图形，诠释大小）
{
INT总= 0;
INT []标记=新INT [尺寸] //跟踪了整数的MST
//转换一个ArrayList到一个数组
名单＆LT;字符串＆GT;包装=图;
的String [] arrayGraph = wrapper.toArray（新的String [wrapper.size（））;
的String []临时=新的String [尺寸]
HashMap的访问=新的HashMap（）;
的for（int i = 0; I＆LT;大小;我++）
{
//的System.out.println（arrayGraph [I]）;
TEMP = arrayGraph [I] .split（）;
//遍历当前节点的连接
为（诠释J = 2; J＆其中;的Integer.parseInt（温度[1]）* 2 + 2; J ++）
{
如果（临时[J] .matches（[0-9] +））
{
的System.out.println（TEMP [J]）;
}
}
}
graph.clear（）;
总回报;
}
公共静态无效的主要（字串[] args）抛出IOException异常
{
的FileReader鳍=新的FileReader（jungle.in）;
的BufferedReader INFILE =新的BufferedReader（翅）;
FileWriter的FOUT =新的FileWriter（jungle.out）;
BufferedWriter将OUTFILE =新的BufferedWriter（FOUT）;
串线;
行= infile.readLine（）;
ArrayList的图=新的ArrayList（）;
做
{
INT NUM =的Integer.parseInt（线）;
如果（NUM！= 0）
{
INT大小=的Integer.parseInt（线）-1;
的for（int i = 0; I＆LT;大小;我++）
{
行= infile.readLine（）;
graph.add（线）;
}
outfile.write（FindMinimumCost（图形，尺寸））;
}
行= infile.readLine（）;
}而（line.equals（0）！）;
}
}
解决方案
Kruskall的算法不会搜索周期，因为它不是性能更高;但试图创建一个组分是树，然后将它们相互连接。正如你，如果你连接一个新的边缘两个不同的树就知道你会创造新的树，没有必要检查周期。
如果你看一下维基页面算法如下：
1。创建森林F（一组树），其中，图中的每个顶点都是一个独立的树
2.创建一个包含图中所有边的集合S
3，而S是为非空和F尚未跨越
一个。删除边缘与s最小重量
湾如果边连接两个不同的树，然后将其添加到森林，结合
两棵树到一棵树
C。否则丢弃该边缘。
您应该使用不相交集数据结构这一点。再从维基：
第一边缘重量使用比较排序为O（E登录E）排序 时间;这使得一步以最小的重量选自S删除边缘 工作在固定的时间。接下来，我们使用了一个不相交集数据 结构（联盟＆安培;查找），以跟踪哪些顶点是在 组件。我们需要执行O（E）的操作，两个发现操作 并有可能为每边一个工会。即使是一个简单的不相交集数据 结构，如不相交集森林，工会按等级可以执行 为O O（E）操作（E日志V）的时间。因此，总的时间是O（E日志E） = O（E日志V）。
创建脱节森林
现在你可以看看 Boost图库-incremental组件的一部分。 您应该实现一些方法： MakeSet 查找 联盟，之后就可以实现kruskall的算法。所有你做的是正与一些集和简单的方式这样做是使用链表。
每个组有一个元素命名为再presentative元素这是在设定的第一要素。
1 - 首先实施 MakeSet 按链接列表：
这prepares不相交集合数据结构增量 连通分量算法通过使每个顶点在图中 它自己的组件的成员（或设置）。
您应该只初始化每个顶点（元素）作为新的设定重新presentative元素，你可以将其设定为自己的父母这样做
函数MakeSet（X）
x.parent：= X
2 - 实施查找方式：
查找重新$一系列的对$ psentative元素包含顶点 X ：
函数查找（X）
如果x.parent == x
返回X
其他
返回查找（x.parent）
在如果部分检查元素重新presentative元素与否。我们设置了所有将其设定为自己的父母再套作为自己的第一个元素presentative元素。
3。最后，当你把所有previous繁为简的部分正在实施的联盟方式：
函数联盟（X，Y）
xRoot：=查找（X）//找到第一个元素（套）的再presentative元
yRoot：=查找（Y）//找到第二个元素（套）的再presentative元
xRoot.parent：= yRoot //重新设置presentative第一组元素
//为同第二组再presentative元
现在你应该如何运行Kruskall？
首先把所有节点 N 相交集合由 MakeSet 方式。在找到所需的边缘后，每一步（未选中和最小的一个），通过查找方式（其再presentative元）查找相关的套其端点顶点，如果他们是一样的，删除此边缘，因为这种优势会导致一个周期，但如果是在不同的组，使用联盟方式合并这些集。他们，因为每一套是树工会树。
您可以通过为不相交集的选择更好的数据结构优化这一点，但现在我觉得就够了。如果您有兴趣了解更多高级数据结构，可以实现排名基础的方式，你会发现它在维基，这很容易，但我并没有提到它从困惑prevent。
I'm trying to write a program that would find the minimum spanning tree. But one problem I am having with this algorithm, is testing for a circuit. What would be the best way to do this in java.
Ok here is my code
import java.io.*;
import java.util.*;
public class JungleRoads
{
public static int FindMinimumCost(ArrayList graph,int size)
{
int total = 0;
int [] marked = new int[size]; //keeps track over integer in the mst
//convert an arraylist to an array
List<String> wrapper = graph;
String[] arrayGraph = wrapper.toArray(new String[wrapper.size()]);
String[] temp = new String[size];
HashMap visited = new HashMap();
for(int i = 0; i < size; i++)
{
// System.out.println(arrayGraph[i]);
temp = arrayGraph[i].split(" ");
//loop over connections of a current node
for(int j = 2; j < Integer.parseInt(temp[1])*2+2; j++)
{
if(temp[j].matches("[0-9]+"))
{
System.out.println(temp[j]);
}
}
}
graph.clear();
return total;
}
public static void main(String[] args) throws IOException
{
FileReader fin = new FileReader("jungle.in");
BufferedReader infile = new BufferedReader(fin);
FileWriter fout = new FileWriter("jungle.out");
BufferedWriter outfile = new BufferedWriter(fout);
String line;
line = infile.readLine();
ArrayList graph = new ArrayList();
do
{
int num = Integer.parseInt(line);
if(num!= 0)
{
int size = Integer.parseInt(line)-1;
for(int i=0; i < size; i++)
{
line = infile.readLine();
graph.add(line);
}
outfile.write(FindMinimumCost(graph, size));
}
line = infile.readLine();
}while(!line.equals("0"));
}
}
解决方案
Kruskall's algorithm won't searches for cycles, because It's not performance efficient; But tries to create a components which are tree, and then connect them to each other. As you know if you connect two different trees with one new edge you will create new tree and there is no need to check for cycles.
If you look at wiki page algorithm is as follow:
1. create a forest F (a set of trees), where each vertex in the graph is a separate tree
2. create a set S containing all the edges in the graph
3. while S is nonempty and F is not yet spanning
a. remove an edge with minimum weight from S
b. if that edge connects two different trees, then add it to the forest, combining
two trees into a single tree
c. otherwise discard that edge.
You should use Disjoint Set Data Structure for this. again from wiki:
first sort the edges by weight using a comparison sort in O(E log E) time; this allows the step "remove an edge with minimum weight from S" to operate in constant time. Next, we use a disjoint-set data structure (Union&Find) to keep track of which vertices are in which components. We need to perform O(E) operations, two 'find' operations and possibly one union for each edge. Even a simple disjoint-set data structure such as disjoint-set forests with union by rank can perform O(E) operations in O(E log V) time. Thus the total time is O(E log E) = O(E log V).
Creating Disjoint Forests
Now you can take a look at Boost Graph Library-Incremental Components part. You should implement some methods: MakeSet, Find, Union, After that you can implement kruskall's algorithm. All you doing is working with some sets, and simplest possible way to do so is using linked list.
Each set has one element named as representative element which is first element in the set.
1- First implement MakeSet by linked lists:
This prepares the disjoint-sets data structure for the incremental connected components algorithm by making each vertex in the graph a member of its own component (or set).
You should just initialize each vertex (element) as a representative element of new set, you can do this by setting them as themselves parent:
function MakeSet(x)
x.parent := x
2- Implement Find method:
Find representative element of set which contains vertex x:
function Find(x)
if x.parent == x
return x
else
return Find(x.parent)
The if part checks the element is representative element or not. we set all representative elements of sets as their first element by setting them as themselves parent.
3- And finally when you got all previous things simple part is implementing Union method:
function Union(x, y)
xRoot := Find(x) // find representative element of first element(set)
yRoot := Find(y) // find representative element of second element(set)
xRoot.parent := yRoot // set representative element of first set
// as same as representative element of second set
Now how you should run Kruskall?
First put all nodes in n disjoint sets by MakeSet method. In each step after finding desired edge (not checked and minimal one), find related sets of its endpoint vertices by Find method (their representative elements), if they are same, drop this edge out because this edge causes a cycle, but If they are in different sets, use Union method to merge these sets. Because each set is tree union of them is tree.
You can optimize this by choosing better data structure for disjoint sets, but for now I think is enough. If you are interested in more advanced data structures, you can implement rank base way, you will find it in wiki, It's easy but I didn't mention it to prevent from bewilderment.
