图的路径查找

小半 • 2023年2月3日上午10:55 • 技术随笔 • 阅读 190

一.概述

我们实现路径查找，最基本的操作还是得遍历并搜索图，此处基于深度优先搜索来完成。其搜索的过程是比较简单的。我们添加了edgeTo[]整型数组，这个整型数组会记录起点s到任意顶点的路径。
如果我们把顶点设定为0，那么它的搜索可以表示为下图：

edge[2]=0 即顶点0到顶点2路径上的上一个顶点为0

edge[1]=2 即顶点0到顶点1路径上的上一个顶点为2
以此类推。。。

要找整个完整路径时：
如要找从0到1的路径，找到edge[1]=2，继续往回找，edge[2]=0，到了起点，路径为0-2-1

二.实现

public class pathDFS {
    private boolean[] marked;
    private int s; //起点
    private int[] edgeTo; //  edgeTo 标记路径
    // 索引代表顶点w，值代表从顶点s到当前顶点w路径上的最后一个顶点(也就是当前顶点w往回找的前一个顶点)

    public pathDFS(graph g,int s) {
        this.marked=new boolean[g.V()];
        this.s = s;  //起点
        this.edgeTo=new int[g.V()];  //也是一个长度为g.V()数组
        dfs(g,s);
    }



    public void dfs(graph g,int v){  //使用深度优先搜索找出G图中v顶点的所有相邻顶
        //标记已搜素
        marked[v]=true;
            for (Integer k : g.adj(v)) {  //循环v的邻接表，拿到相邻顶点，继续递归搜索
            if(!marked[k]){ //没被搜索过就继续递归，直到该顶点的临界表中每个顶点都被搜索过，递归结束。
                edgeTo[k]=v;  //在递归前！ 记录从起点s到节点k路径上的前一个节点为v
                dfs(g,k);
            }
        }
    }

    public boolean hasPath(int v){ //起点和顶点v是否存在路径
        return marked[v];  //直接返回marked[v]，如果被搜索过，即是相通的！
    }

    public Stack pathTo(int v) {  //找出从起点s到顶点v的路径！ 无向图为任意一条
        if (!hasPath(v)) {  //此时已经搜索完成，如果顶点没有被标记，则不存在路径 ！
            return null;
        }
            Stack<Integer> stack = new Stack<>();
       /*  for(int i=v;i!=s;i=edgeTo[i]){  //i为指针，  从v往前倒着来！
            // degeTo[i]的值，正好是往前一个顶点，循环让 i等于找个顶点
            stack.push(i);  //依次压入顶点，
        }*/
        int i=v; 
        while( i!=s){  循环条件： 到顶点
            stack.push(i);  //将指针i压栈
            i=edgeTo[i];  //迭代！
        }    


         //补上起点s
            stack.push(s);
            return stack;
    }