Java：寻找两点之间所有路径

问题描述：

见下图，要求寻找A至Z的所有路径。

已知：两点之间的直接路径。例如：A-->B B-->C B-->E。。。。

 

 

 

 

解：

定义一个基本路径模型，属性：起始点和结束点。A-->B可抽象成new Road("A",'B');

package alogrim;
public class Road implements Cloneable {
	public Road(String begin,String end) {
		this.begin = begin;
		this.end = end;
	}
	private String begin;
	private String end;
	public String toString() {
		return begin + "->" + end;
	}
	public String getBegin() {
		return begin;
	}
	public void setBegin(String begin) {
		this.begin = begin;
	}
	public String getEnd() {
		return end;
	}
	public void setEnd(String end) {
		this.end = end;
	}
	
	public boolean equals(Object obj) {
		Road r = (Road)obj;
		if(this.getBegin().equals(r.getBegin()) && this.getEnd().equals(r.getEnd())) {
			return true;
		}
		return false;
	}
	
	public Object clone() {
		try {
			return super.clone();
		} catch (CloneNotSupportedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return null;
	}
}

 核心算法分两步：

1 过滤掉无用的路径。例如上图：G-->B G-->F D-->F都属于无效路径。

第一步：获取无效开始节点和无效结束点

	/**
	 * 过滤掉无用的节点
	 * 获取到无效开始节点和无效结束点
	 * @param all 所有节点
	 * @return
	 */
	public Set<String> filterInvalidNode(Set<String> all, List<Road> roads,
			Set<String> begins, Set<String> ends) {
		Set<String> result = new HashSet<String>();
		boolean isBegin = true;
		boolean isEnd = true;
		for (String str : all) {
			if (!existEnd(str, roads)) { // 没有以此节点结尾的路径，则证明此节点为无用节点
				isBegin = false;
				begins.add(str);
				// 删除以此节点为开始的路径
				// this.deleteBegin(str, roads);
			} else if (!existBegin(str, roads)) {// 没有以此节点开头的路径，则证明此节点为无用节点
				isEnd = false;
				ends.add(str);
				// this.deleteEnd(str, roads);
			} else {
				result.add(str); // 有用的节点
			}
		}
		if (isBegin == true && isEnd == true) {
			return result;
		} else {
			return filterInvalidNode(result, roads, begins, ends);
		}
	}

 第二步：删除无效路径

	/**
	 * 获取到需要删除的路径
	 * 
	 * @param begins
	 * ---无效起始节点
	 * @param ends
	 * ---无效终结点
	 * @param roads
	 */
	public Set<Road> deleteRoad(Set<String> begins, Set<String> ends,
			List<Road> roads) {
		Set<Road> set = new HashSet<Road>();
		for (String str : begins) {
			for (Road r : roads) {
				if (r.getBegin().equals(str)) {
					set.add(r);
				}
				if (r.getEnd().equals(str)) {
					set.add(r);
				}
			}
		}
		return set;
	}

 2 路径遍历，确保找到两点之间的所有可通过路径，需要确保每条基本路径都被访问过。本算法采用自上而下遍历方式。详细含义如下：

List<Road> roadList = null; //已知的路径
	List<String> backList = new ArrayList<String>(); //存放已经访问过的节点
	Set<String> resultSet = new HashSet<String>(); //目的路径--访问结果
	Set<Road> cirList = new HashSet<Road>(); 	//回路
	
	/**
	 * 路径遍历的核心算法
	 * @param start
	 * ---需要寻找的起始节点。本案例为A
	 * @param destination
	 * ---需要寻找的终结点。本案例为Z
	 */
	public void getAllRoad(String start, String destination) {
		backList.add(start);
		for (int z = 0; z < roadList.size(); z++) {
			if (roadList.get(z).getBegin().equals(start)) { //寻找找以start开始的路径
				if (roadList.get(z).getEnd().equals(destination)) { //如果以destination结尾，则为一条有效路径
					resultSet.add(backList.toString().substring(0, backList.toString().lastIndexOf("]")) + "," + destination + "]");
					continue;
				}
				if (!backList.contains(roadList.get(z).getEnd())) {//此节点仍未遍历，则继续迭代
					getAllRoad(roadList.get(z).getEnd(), destination);
				} else {//證明有回路
					cirList.add(roadList.get(z));
					//System.out.println("wwww");
				}
			}
		}
		backList.remove(start);
	}

 

至此已经完成‘两点之间所有路径’的核心算法。详细代码见附件，main方法在MapVisit里

评论

2 楼 aredapple 2012-04-07  

不错，工作中也正好要用到，向楼主表示深深的敬意。

1 楼 vincent-lee 2009-07-02  

你这部分代码正好是我需要的，前几天下载下来做了一些改造用着挺好。非常感谢！