数据结构？图？路径？

楼上的人才

个人认为前后2个城市名称一样的话，应该输出yes。城市名称应该应该区分大小写，如果不想区分大小写，Load时都转成大写或者小写存储即可。
我换个思路写的，用的是图的思路。

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;

public class Connected {
	public Map cityMap = new Hashtable();
	public List cityList = new ArrayList();
	boolean[][] connectArr = null;

	public static void main(String[] args) {
		Connected c = new Connected();
		if (args.length != 3) {
			System.out.println("Need Three Arguments!");
		} else {
			if (c.Load(args[0])) {
				c.init();
				System.out.println(c.connected(args[1].trim(), args[2].trim()));

			} else {
				System.out.println("File Load Exception");
			}
		}
	}

	public boolean Load(String filename) {
		File f = new File(filename);

		try {
			BufferedReader in = new BufferedReader(new FileReader(f));
			String s = null;
			while ((s = in.readLine()) != null) {
				String[] arrayStr = s.split(",");
				if (arrayStr != null && arrayStr.length == 2) {
					for (String city : arrayStr) {
						if (!this.cityMap.containsKey(city.trim())) {
							this.cityMap.put(city.trim(), this.cityMap.size());
						}
					}
					this.cityList.add(arrayStr[0].trim() + "->"
							+ arrayStr[1].trim());
					this.cityList.add(arrayStr[1].trim() + "->"
							+ arrayStr[0].trim());
				}
			}
			in.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
			return false;
		} catch (IOException e) {
			e.printStackTrace();
			return false;
		}
		return true;
	}

	public void init() {
		this.connectArr = new boolean[this.cityMap.size()][this.cityMap.size()];
		for (Object obj : this.cityList) {
			String[] arrayStr = obj.toString().split("->");
			int from = Integer.parseInt(this.cityMap.get(arrayStr[0])
					.toString());
			int to = Integer.parseInt(this.cityMap.get(arrayStr[1]).toString());
			this.connectArr[from][to] = true;
		}

		for (int x = 0; x < this.connectArr.length; x++) {
			for (int y = 0; y < this.connectArr.length; y++) {
				if (this.connectArr[x][y]) {
					for (int z = 0; z < this.connectArr.length; z++)
						if (this.connectArr[z][x]) {
							this.connectArr[z][y] = true;
						}
				}
			}
		}
	}

	public String connected(String from, String to) {
		if (this.cityMap.containsKey(from) && this.cityMap.containsKey(to)) {
			int x = Integer.parseInt(this.cityMap.get(from).toString());
			int y = Integer.parseInt(this.cityMap.get(to).toString());
			if (this.connectArr[x][y]) {
				return "yes";
			} else {
				return "no";
			}
		}
		return "no";
	}
}

2天做一道j2se的题，国外公司招聘的着眼点值得深思啊。

有点错误，修改了一下，改用了Set替代List。
感觉还可以考虑的东西：
根据题目列出的条件先写JUnit test
把所有可以联通的城市分组记录到一个文件里面。运行一次，以后做判断性能就可以提高了

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class Connected {
	public static List<String[]> getCityPair(String filePath) {
		List<String[]> list = new ArrayList<String[]>();
		try {
			BufferedReader br = new BufferedReader(new FileReader(new File(
					filePath)));
			String line = null;
			while ((line = br.readLine()) != null) {
				String[] temp = line.split(",");
				if (temp.length == 2) {
					String[] array = { temp[0].trim(), temp[1].trim() };
					list.add(array);
				}
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		return list;
	}

	public static Set<String> getKeyInvolvedCities(String keyCity,
			List<String[]> cityPair) {
		Set<String> result = new HashSet<String>();
		result.add(keyCity);
		Set<String> tempSet = new HashSet<String>();
		tempSet.add(keyCity);
		while (tempSet.size() != 0) {
			Set<String> newTempSet = new HashSet<String>();
			Iterator<String> tit = tempSet.iterator();
			while (tit.hasNext()) {
				String targetCity = tit.next();
				Iterator<String[]> cpit = cityPair.iterator();
				while (cpit.hasNext()) {
					String[] cityAry = cpit.next();
					if (targetCity.equalsIgnoreCase(cityAry[0])) {
						newTempSet.add(cityAry[1]);
						cpit.remove();
					} else if (targetCity.equalsIgnoreCase(cityAry[1])) {
						newTempSet.add(cityAry[0]);
						cpit.remove();
					} else {
					}
				}
			}
			tempSet = new HashSet<String>(newTempSet);
			result.addAll(tempSet);
		}
		return result;
	}

	public static void main(String[] args) {
		if (args.length != 3) {
			System.out.println("error: require 3 args");
		} else {
			List<String[]> cityPair = Connected.getCityPair(args[0]);
			Set<String> cityList = Connected.getKeyInvolvedCities(args[1],
					cityPair);
			String result = cityList.contains(args[2]) ? "yes" : "no";
			System.out.println(result);
		}
	}
}

最讨论JAVA里编程的一Get一Set的方法了，一个简单的问题搞得烦死了.

xgylog 的思路很精炼，而且对储存空间要求低，佩服一个先。
sbzk的好像有点太学术，运算时间和储存空间都要求大，不是太灵活了。
我的可能太臃肿了，对象定义不少，呵呵。

大家讨论一下思路的形成如何？
两天，如果只是考基本知识的话，太长了。

题目中路径没有权重，我们是否需要考虑最优路径的问题？

另：看来过程化和结构化编程还是主流思路。

我觉得neomac.lin的思路最有发展空间，特别是在腰考虑路径权重的时候。

有意思的题目

不是答案。打印路径。不知道迭代的对不对。

package home;

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public class City {
	private final String name;
	private final Set<City> nearCitys;

	public String getName() {
		return name;
	}

	public Set<City> getNearCitys() {
		return Collections.unmodifiableSet(nearCitys);
	}

	public void addNearCity(City city) {
		this.nearCitys.add(city);
		city.nearCitys.add(this);
	}

	public boolean isNearWith(City city) {
		return nearCitys.contains(city);
	}

	@Override
	public boolean equals(Object obj) {
		if (!(obj instanceof City))
			return false;
		else if (this.hashCode() != obj.hashCode())
			return false;
		else
			return name.equals(((City) obj).getName());
	}

	@Override
	public int hashCode() {
		return name.hashCode() + 43424237;
	}

	@Override
	public String toString() {
		return name;
	}

	public City(String name) {
		this.name = name;
		this.nearCitys = new HashSet<City>();
	}
}


package home;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;

public class Helper {

	public static Map<String, City> read(String fileName) {
		Map<String, City> allCitys = new HashMap<String, City>();
		BufferedReader in;
		try {
			in = new BufferedReader(new FileReader(fileName));
			String s;
			while ((s = in.readLine()) != null) {
				String[] cityNames = s.split(",");

				City city0 = allCitys.get(cityNames[0].trim().toLowerCase());
				if (city0 == null) {
					city0 = new City(cityNames[0].trim());
					allCitys.put(cityNames[0].trim().toLowerCase(), city0);
				}
				City city1 = allCitys.get(cityNames[1].trim().toLowerCase());
				if (city1 == null) {
					city1 = new City(cityNames[1].trim());
					allCitys.put(cityNames[1].trim().toLowerCase(), city1);
				}
				city0.addNearCity(city1);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		return allCitys;
	}

}


package home;

import java.util.Iterator;
import java.util.Map;
import java.util.Stack;

public class Connector {
	private static Map<String, City> allCitys;

	public static void main(String[] args) {
		allCitys = Helper.read("airline.txt");
		Connector connector = new Connector();
		connector.search("new york", "Tampa");
	}

	public void search(String fromCityName, String toCityName) {
		City fromCity = allCitys.get(fromCityName.trim().toLowerCase());
		City toCity = allCitys.get(toCityName.trim().toLowerCase());
		Stack<City> stack = new Stack<City>();
		this.searchRoute(fromCity, fromCity, toCity, stack);
	}

	public void searchRoute(City city, City fromCity, City toCity,
			Stack<City> stack) {
		stack.push(city);
		Iterator<City> nearCityIterator = city.getNearCitys().iterator();
		while (nearCityIterator.hasNext()) {
			City tempCity = nearCityIterator.next();
			if (!stack.contains(tempCity)) {
				if (tempCity.equals(toCity)) {
					stack.push(tempCity);
					System.out.print(stack.toString());
					stack.pop();
					continue;
				}
				searchRoute(tempCity, fromCity, toCity, stack);
			}
		}
		stack.pop();
	}
}

如果按该题的要求，用图确实在空间方面花费较大。所以我开始写的思路和你们的差不多。不过那时你们都贴出来了，我就想换个思路写。图的优势是，如果只加载一次，多次查找的话，效率就很快了。因为初始化的时候已经勾勒出一个可到达城市的数组，查找时只需根据下标【起点】【终点】打印出对应的值即可。