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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
求无向无权图起点到终点的所有路径
求无向无权图起点到终点的所有路径 基本思路: 基于图的深度优先遍历进行修改。 0:初始栈中只有起点元素。 1:如果栈为空,则返回,否则,访问栈顶节点,但先不删除栈顶元素。 2:如果该元素的邻接点 (1)是终点,则打印路径。 (2)在栈中已存在,则是环路,不处理。 (2)正常,则将该邻接点入栈,继续步骤1 示例图如下: 代码如下: package
记数据结构简单课设之无向图的简单路径
只有两点要求: 1)求出无向图中从起点到终点的所有简单路径。其中起点和终点可以由用户自行设定。 2)求出无向图中从起点到终点的指定长度(如K)的所有简单路径。其中起点和终点可以由用户自行设定。 #include #include #include #include #include #include #include #include using namespace std;
广度优先遍历求指定顶点之间的最短路径
  问题描述:设图中的各边的权值均为相等,以邻接表为存储结构,求顶点v到顶点u的最短路径长度,要求输出路径上的每一个顶点。算法思路:采用广度优先遍历算法,当访问到的当前顶点为所指定的终点时,结束遍历,利用队列中每中元素的pre值寻找起点到终点的最短路径(当前顶点的pre值即为链接以当前顶点为终点的弧的表头结点序号)。算法实现:#include #include #inclu
有向图起点s到目标点t的所有路径
利用前面建立的结构,在这里利用这写顶点结构,边的建立结构,边数,顶点数, 即种类,和用于存储顶点的一个vector容器, 我采取的方法类似于,深度优先搜索: 1)首先建立了一个vector 用于存储顶点,  2)将s起点放入vector 中, 3)对他所指向的邻接进行查找,卡纳可能是否有那个目标点tar,如果有的话,则按s->t的顺序进行输出 4)如果没有目标点的话,
Java 有向图的遍历,寻找所有从起点到终点的路径
最近遇到一个绘图的需求,是对地图的二次开发,在上面绘制覆盖物,所以这里涉及了对有向无环图的遍历问题。 如下图是一个有向无环图: 正常的深度优先遍历算法得到的结果会是:A、B、C、E、G、J、K、D、F、H、I 。 但是我们需要的结果是:A、B、C、E、G、J、K ,A、B、D、E、G、J、K ,A、B、D、F、H、I、J、K 一共三条路径。 所以需要对普遍的深度优先遍历算法做一定修
最短路径:HDU2006-一个人的旅行(多个起点,多个终点)
解题心得: 1、之前做的最短路径使用Dijkstra算法一直都是算的一个起点,所以在一开始有一点懵逼,其实在使用Dijkstra算法之接将所有的起点全部初始化为0就可以了,它会自动寻找多个起点到终点的最短路径,注意这时d[i],记录的是从多个起点到达I点的最短路径,如果需要记录是哪个起点到达的最短路径还需要记录。 2、之后使用了一下Floyd的算法,因为Floyd算法可以直接记录所有的maps
动态规划(4)详细讲解各最短路径算法及比较
1 最短路径问题(The shortest-path problem, SPP)     最短路径问题是图论研究中的一个经典算法问题,旨在寻找图中两结点之间的最短路径。 算法具体的形式包括: 1) 确定起点的最短路径问题 - 即已知起始结点,求最短路径的问题。 2) 确定终点的最短路径问题 - 与确定起点的问题相反,该问题是已知终结点,求最短路径的问题。在无向图中该问题与确定起点
HDU 2066 一个人的旅行【最短路,多起点多终点,Dijkstra算法+spfa算法】
一个人的旅行 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 31420    Accepted Submission(s): 10804 Problem Description 虽然草儿是个路痴(就是在杭电待了一
7.28⑤ 已知有向图和图中两个顶点u和v,试编写算法求有向图中从u到v的所有简单路径。
7.28⑤ 已知有向图和图中两个顶点u和v,试编写算法求有向图中从u到v的所有简单路径。 void AllPath(ALGraph g, VertexType sv, VertexType tv,StrARR &path, int &i);
设计一个算法,输出从u到v的所有最短路径(采用邻接表存储)
思想:用path数组存放路径(初始为空),d表示路径长度(初始为-1),查找从顶点u到v的最短路径过程如图所示: 对应算法如下: void FindPath(AGraph *G,int u,int v,int path[ ],int d) { in