这是一个美国IT企业的面试题，原题大意是从一个文件中读取出可连通的城市对，给出两个城市，判断是否可连通，如果可连通就输出yes，不可连通就输出no，否则给出命令行帮助。
其实判断连接状态不用遍历图，用蔓延法即可，具体做法就是从起始城市开始，依次改变其周边连通城市的连通状态，再从周边开始向周边连通城市蔓延，如果能蔓延到结束城市的周边可连通城市，则说明两个城市是完全可连通的。这种做法和多米诺骨牌效应很像。我姑且称之为蔓延法。
代码如下：
package com.sitinspring;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
/** *//**
* 城市类
* @author HEYANG
* @since 2008-7-24 下午08:38:19
*/
class City
{
// 城市名
String name;
// 可否连通
boolean isConnected;
public City(String name){
this.name=name;
isConnected=false;
}
}
/** *//**
* 用蔓延法探测两个城市的可连通状态
* @author HEYANG
* @since 2008-7-24 下午09:09:30
*/
public class RoadTestor{
/** *//**
* 路线图
*/
private Map<String,List<City>> map;
/** *//**
* 构造函数
*
*/
public RoadTestor(){
map=new TreeMap<String,List<City>>();
}
/** *//**
* 添加两个城市间的连接
* @param startCity
* @param endCity
*/
private void addConnRoad(String startCity,String endCity){
if(map.containsKey(startCity)){
List<City> connCities=map.get(startCity);
connCities.add(new City(endCity));
map.put(startCity,connCities);
}
else{
List<City> connCities=new ArrayList<City>();
connCities.add(new City(endCity));
map.put(startCity,connCities);
}
}
/** *//**
* 添加双向道路
* @param startCity
* @param endCity
*/
public void addRoad(String startCity,String endCity){
addConnRoad(startCity,endCity);
addConnRoad(endCity,startCity);
}
/** *//**
* 打印一个城市及其可连通的周边城市
*
*/
public void display(){
for(String city:map.keySet()){
// 本城
System.out.print(city+"通向:");
// 可连通的周边城
for(City connCity:map.get(city)){
System.out.print(connCity.name+",");
}
System.out.println();
}
}
/** *//**
* 判断两城市是否能连通
* @param startCity
* @param endCity
* @return
*/
public boolean isConnected(String startCity,String endCity){
// 调用蔓延法前重置所有城市的连通状态
resetAllCities();
// 蔓延法递归调用
drop(startCity);
// 结束城市周边可通的城市有一个被蔓延到,则表示该城市可连通
for(City connCity:map.get(endCity)){
if(connCity.isConnected){
System.out.println(startCity+" 可连通到 "+endCity);
return true;
}
}
// 都不满足则表示两个城市无法连通
System.out.println(startCity+" 不可连通到 "+endCity);
return false;
}
/** *//**
* 蔓延法,从一个城市起依次改变周边城市的可连通状态
* @param cityName
*/
private void drop(String cityName){
for(City connCity:map.get(cityName)){
if(connCity.isConnected==false){
connCity.isConnected=true;
drop(connCity.name);
}
}
}
/** *//**
* 重置每个城市的连通状态为否,在探测两城市连通情况前调用
*/
private void resetAllCities(){
for(String city:map.keySet()){
for(City connCity:map.get(city)){
connCity.isConnected=false;
}
}
}
public static void main(String[] args){
RoadTestor roadMap=new RoadTestor();
// 我国诸城
roadMap.addRoad("乌鲁木齐", "呼和浩特");
roadMap.addRoad("呼和浩特", "北京");
roadMap.addRoad("北京", "大连");
roadMap.addRoad("北京", "西安");
roadMap.addRoad("北京", "上海");
roadMap.addRoad("大连", "上海");
roadMap.addRoad("西安", "成都");
roadMap.addRoad("西安", "南京");
roadMap.addRoad("上海", "南京");
roadMap.addRoad("南京", "广州");
// 美国诸城
roadMap.addRoad("旧金山", "西雅图");
roadMap.addRoad("西雅图", "纽约");
roadMap.addRoad("亚特兰大", "西雅图");
roadMap.addRoad("纽约", "北京");// 北京到纽约的航线
// 欧洲诸城
roadMap.addRoad("伦敦", "巴黎");
roadMap.addRoad("巴黎", "柏林");
roadMap.addRoad("柏林", "伦敦");
// roadMap.addRoad("伦敦", "上海");// 上海到伦敦的航线
// 展示每个城市和其周边城市的可连通情况
roadMap.display();
// 依次探测三对城市的连通情况
roadMap.isConnected("大连", "北京");
roadMap.isConnected("大连", "纽约");
roadMap.isConnected("大连", "伦敦");
}
}
控制台输出：
上海通向:北京,大连,南京,
乌鲁木齐通向:呼和浩特,
亚特兰大通向:西雅图,
伦敦通向:巴黎,柏林,
北京通向:呼和浩特,大连,西安,上海,纽约,
南京通向:西安,上海,广州,
呼和浩特通向:乌鲁木齐,北京,
大连通向:北京,上海,
巴黎通向:伦敦,柏林,
广州通向:南京,
成都通向:西安,
旧金山通向:西雅图,
柏林通向:巴黎,伦敦,
纽约通向:西雅图,北京,
西安通向:北京,成都,南京,
西雅图通向:旧金山,纽约,亚特兰大,
大连 可连通到 北京
大连 可连通到 纽约
大连 不可连通到 伦敦