s15885823584 2016-02-05 01:44 采纳率: 0%
浏览 2703

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

楼主写了一个求起点到终点的所有路径的算法,数据用邻接表链式结构,当节点数达到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 2016-02-05 15:57
    关注
    评论

报告相同问题?

悬赏问题

  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误