2 s15885823584 s15885823584 于 2016.02.05 09:44 提问

邻接表求起点与终点所有路径算法求优化

楼主写了一个求起点到终点的所有路径的算法,数据用邻接表链式结构,当节点数达到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);


    }

}

1个回答

devmiao
devmiao   Ds   Rxr 2016.02.05 23:57
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!