并集查找算法
开发有效算法解决已经问题的第一步是实现一个解决该问题的简单算法。如果我们需要解决几个容易的特殊问题实例，则这个简单实现可以完成任务。如果要求的算法较为复杂，则简单实现为我们提供了一种针对小型实例伯正确性检查以及评价性能牲的基准。我们总是要关心算法的效率，但在开发第一个解决问题的程序时，我们首先需要保证该程序是问题的正确解决方案。
第一个想到的构思也许是保存所有的输入对，然后编写一个函数来遍历它们，找出下一个对象对是否连通。我们将使用一种与之不同的方法。首先，对的数量可能十分大，在实际应用中不太可能保存所有对。其次，更要注意的是，没有简单方法能根据所有连通集合立即判断两个对象是否连通，即使我们能够将它们全部保存，也不能达到此目的。
摘自：C算法(第一卷)第二版相对于《从文件读取城市对信息，判断指定两个城市是否可连通》一文中使用的算法，这里的并集查找算法能够提升五倍的速度，的确极大提高了计算的效率。
package eli.math;
import java.io.FileReader;
import java.io.IOException;
import java.io.LineNumberReader;
import java.util.ArrayList;
import java.util.List;
/** *//**
* @author <a href="mailto:eli.wuhan@gmail.com">屹砾</a>
*/
public class Connected2 
{
// 存储城市的集合
private List<String> cities = new ArrayList<String>(0);
// 标识数组的容量
private static final int capacity = 256;
// 容量的倍数
private int multiple = 1;
// 城市的标识，用于区分城市的连通性
private int[] id = new int[capacity * multiple];
public Connected2() {
for (int i = id.length - 1; i >= 0; i--) {
id[i] = i;
}
}
protected void clear() {
cities.clear();
multiple = 1;
id = new int[capacity * multiple];
for (int i = id.length - 1; i >= 0; i--) {
id[i] = i;
}
}
public boolean isConnected(String file, String city0, String city1)
throws IOException {
clear();
read(file);
int idx0 = cities.indexOf(city0);
int idx1 = cities.indexOf(city1);
if (id[idx0] == id[idx1]) {
return true;
}
return false;
}
/** *//**
* 读取数据文件并填充数据
*
* @param file
* @throws IOException
*/
protected void read(String file) throws IOException {
LineNumberReader fileReader = new LineNumberReader(new FileReader(file));
String[] arr = null;
for (String line = fileReader.readLine(); line != null; line = fileReader
.readLine()) {
arr = line.split(",");
if (arr.length == 2) {
addCityPair(arr[0], arr[1]);
}
}
}
/** *//**
* 添加城市对到集合中
*
* @param city0
* @param city1
*/
protected void addCityPair(String city0, String city1) {
int idx0 = addCity(city0), idx1 = addCity(city1);
if (cities.size() > id.length) {
int[] tmp = new int[capacity * ++multiple];
System.arraycopy(id, 0, tmp, 0, id.length);
id = tmp;
for (int i = id.length - 1; i >= capacity * (multiple - 1); i--) {
id[i] = i;
}
}
// 并集查找算法
if (id[idx0] != id[idx1]) {
for (int tmp = id[idx0], i = cities.size() - 1; i >= 0; i--) {
if (id[i] == tmp) {
id[i] = id[idx1];
}
}
}
}
/** *//**
* 将城市加入到集合中
*
* @param cityName
* 城市名称
* @return 城市在集合中的索引号
*/
protected int addCity(String cityName) {
int idx = -1;
if ((idx = cities.indexOf(cityName)) != -1) {
return idx;
}
cities.add(cityName);
return cities.size() - 1;
}
/** *//**
* @param args
*/
public static void main(String[] args) {
Connected2 cities = new Connected2();
try {
if (args.length == 3) {
long s = System.currentTimeMillis();
boolean bool = cities.isConnected(args[0], args[1], args[2]);
long t = System.currentTimeMillis() - s;
System.out.println(bool ? "yes" : "no");
System.out.println("time(ms): " + t);
} else {
throw new IllegalArgumentException();
}
} catch (IOException e) {
System.out.println("File is not existing.");
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println("City(s) is not valid in this file.");
} catch (Exception e) {
System.out.println("Usage: java " + Connected2.class.getName()
+ " <filename> <cityname1> <cityname2>");
}
}
}