這是一個美國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("大連", "倫敦");
}
}
控制臺輸出：
上海通向:北京,大連,南京,
烏魯木齊通向:呼和浩特,
亞特蘭大通向:西雅圖,
倫敦通向:巴黎,柏林,
北京通向:呼和浩特,大連,西安,上海,紐約,
南京通向:西安,上海,廣州,
呼和浩特通向:烏魯木齊,北京,
大連通向:北京,上海,
巴黎通向:倫敦,柏林,
廣州通向:南京,
成都通向:西安,
舊金山通向:西雅圖,
柏林通向:巴黎,倫敦,
紐約通向:西雅圖,北京,
西安通向:北京,成都,南京,
西雅圖通向:舊金山,紐約,亞特蘭大,
大連 可連通到 北京
大連 可連通到 紐約
大連 不可連通到 倫敦