楼主写了一个求起点到终点的所有路径的算法,数据用邻接表链式结构,当节点数达到100多个时运行就很慢了,求一个更好的算法。
算法如下:
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Stack;
public class PathSearch {
private GraphEntry[] graph; //邻接表
private int beginVertex; //起点站编号
private int endVertex; //终点站编号
List<ArrayList<Integer>> allPath = new ArrayList<ArrayList<Integer>>();
public PathSearch(GraphEntry[] graph,int beginVertex,int endVertex){
this.beginVertex=beginVertex;
this.endVertex=endVertex;
this.graph=graph;
}
public void makePathPrompt()
{
Stack<GraphEntry> stack = new Stack<GraphEntry>();
stack.push(graph[beginVertex]);//将起点入栈
graph[beginVertex].setFlag(true);//将起点标记为已搜索
ArrayList<Integer> path = new ArrayList<Integer>();//暂时存储搜索中的路径
path.add(beginVertex);//加入起点
Hashtable<Integer, List<Integer>> hasSearchTable = new
Hashtable<Integer, List<Integer>>();//记录本节点已经遍历过的节点
hasSearchTable.put(beginVertex, new ArrayList<Integer>());
while(!stack.isEmpty())
{
for(int i=0;i<stack.peek().size();i++)
{
int id = stack.peek().getItem(i);//当前节点的相邻节点ID
GraphEntry ge = stack.peek();//当前节点
boolean isPop=false;
//如果当前节点的相邻节点未被搜索过,且未从当前节点搜索过该相邻节点,则入栈
if(!graph[id].isFlag() && !hasSearchTable.get(ge.getId()).contains(id))
{
stack.push(graph[id]);
graph[id].setFlag(true);
path.add(id);
hasSearchTable.get(ge.getId()).add(id);
if(!hasSearchTable.containsKey(id))
{
hasSearchTable.put(id, new ArrayList<Integer>());
}
//如果当前节点的相邻节点为终点,表示找到一条路径,并让当前节点出栈
if(id==endVertex)
{
allPath.add((ArrayList<Integer>) path.clone());
ge = stack.pop();
// hasSearchTable.get(ge.getId()).clear();
ge.setFlag(false);
path.remove((Integer)ge.getId());
}
break;
}
//如果当前节点没有未搜索过的相邻节点,则出栈
else if(i==stack.peek().size()-1 && graph[id].isFlag())
{
isPop=true;
ge = stack.pop();
ge.setFlag(false);
hasSearchTable.get(ge.getId()).clear();
path.remove((Integer)ge.getId());
if(stack.isEmpty())
break;
}
else if(i==stack.peek().size()-1 && !isPop)
{
ge = stack.pop();
ge.setFlag(false);
hasSearchTable.get(ge.getId()).clear();
path.remove((Integer)ge.getId());
if(stack.isEmpty())
break;
}
}
}
}
public List<ArrayList<Integer>> getAllPath() {
return allPath;
}
}
GraphEntry类如下:
import java.util.ArrayList;
//邻接表类, 用于表示地铁线路图的数据结构。
class GraphEntry {
private ArrayList<Integer> list; //相邻节点的ID
private boolean flag;//是否被搜索标记
private int id;//当前节点ID
public GraphEntry(){
list = new ArrayList<Integer>();
}
public void insertItem(int id){
list.add(id);
}
public int getItem(int index){
return list.get(index);
}
public int size(){
return list.size();
}
public boolean isFlag() {
return flag;
}
public void setFlag(boolean flag) {
this.flag = flag;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
}
测试类如下:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Hashtable;
import java.util.List;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成的方法存根
Hashtable<Integer, List<Integer>> hashTable = new Hashtable<Integer, List<Integer>>();
hashTable.put(0, Arrays.asList(new Integer[]{1,12,13}));
hashTable.put(1, Arrays.asList(new Integer[]{0,2,7,8}));
hashTable.put(2, Arrays.asList(new Integer[]{1,3,8,14}));
hashTable.put(3, Arrays.asList(new Integer[]{2,4,14,21}));
hashTable.put(4, Arrays.asList(new Integer[]{3,15,21}));
hashTable.put(5, Arrays.asList(new Integer[]{6,14,20}));
hashTable.put(6, Arrays.asList(new Integer[]{5,7,13,14}));
hashTable.put(7, Arrays.asList(new Integer[]{1,6,13,14}));
hashTable.put(8, Arrays.asList(new Integer[]{1,2,9,17}));
hashTable.put(9, Arrays.asList(new Integer[]{8,10,18,21}));
hashTable.put(10, Arrays.asList(new Integer[]{9,18,19}));
hashTable.put(11, Arrays.asList(new Integer[]{12,17}));
hashTable.put(12, Arrays.asList(new Integer[]{0,11,17}));
hashTable.put(13, Arrays.asList(new Integer[]{0,6,7,20}));
hashTable.put(14, Arrays.asList(new Integer[]{2,3,5,6,7,15}));
hashTable.put(15, Arrays.asList(new Integer[]{4,14,16}));
hashTable.put(16, Arrays.asList(new Integer[]{15}));
hashTable.put(17, Arrays.asList(new Integer[]{8,11,12,18}));
hashTable.put(18, Arrays.asList(new Integer[]{9,10,17}));
hashTable.put(19, Arrays.asList(new Integer[]{10,21}));
hashTable.put(20, Arrays.asList(new Integer[]{5,13}));
hashTable.put(21, Arrays.asList(new Integer[]{3,4,9,19}));
GraphEntry [] graph=new GraphEntry[hashTable.size()];
for(Integer key : hashTable.keySet())
{
GraphEntry ge = new GraphEntry();
ge.setId(key);
for(Integer id:hashTable.get(key))
{
ge.insertItem(id);
}
graph[key]=ge;
}
PathSearch ps = new PathSearch(graph, 10, 6);
ps.makePathPrompt();
List<ArrayList<Integer>> allPath = ps.getAllPath();
int a=allPath.get(0).get(0);
}
}