Java數(shù)據(jù)結(jié)構(gòu)之圖的路徑查找算法詳解

更新時間：2022年11月01日 09:55:28 作者：JAVA旭陽

這篇文章主要為大家詳細介紹了java數(shù)據(jù)結(jié)構(gòu)中圖的路徑查找算法，文中的示例代碼講解詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

前言

在實際生活中，地圖是我們經(jīng)常使用的一種工具，通常我們會用它進行導航，輸入一個出發(fā)城市，輸入一個目的地

城市，就可以把路線規(guī)劃好，而在規(guī)劃好的這個路線上，會路過很多中間的城市。這類問題翻譯成專業(yè)問題就是：

從s頂點到v頂點是否存在一條路徑？如果存在，請找出這條路徑。

例如在上圖上查找頂點0到頂點4的路徑用紅色標識出來,那么我們可以把該路徑表示為 0-2-3-4。

如果對圖的前置知識不了解，請查看系列文章：

【數(shù)據(jù)結(jié)構(gòu)與算法】圖的基礎(chǔ)概念和數(shù)據(jù)模型

【數(shù)據(jù)結(jié)構(gòu)與算法】圖的兩種搜索算法

算法詳解

我們實現(xiàn)路徑查找，最基本的操作還是得遍歷并搜索圖，所以，我們的實現(xiàn)暫且基于深度優(yōu)先搜索來完成。其搜索

的過程是比較簡單的。我們添加了edgeTo[]整型數(shù)組，這個整型數(shù)組會記錄從每個頂點回到起點s的路徑。

如果我們把頂點設(shè)定為0，那么它的搜索可以表示為下圖：

總結(jié)來說，就是edgeTo數(shù)組的下標表示當前頂點，內(nèi)容存放上一個節(jié)點的數(shù)據(jù)，根據(jù)最終edgeTo的結(jié)果，我們很容易能夠找到從起點0到任意頂點的路徑。

實現(xiàn)

API設(shè)計

類名	DepthFirstPaths
成員變量	1.private boolean[] marked: 索引代表頂點，值表示當前頂點是否已經(jīng)被搜索2.private int s:起點3.private int[] edgeTo:索引代表頂點，值代表從起點s到當前頂點路徑上的最后一個頂點
構(gòu)造方法	DepthFirstPaths(Graph G,int s)：構(gòu)造深度優(yōu)先搜索對象，使用深度優(yōu)先搜索找出G圖中起點為s的所有路徑
成員方法	1.private void dfs(Graph G, int v)：使用深度優(yōu)先搜索找出G圖中v頂點的所有相鄰頂點2.public boolean hasPathTo(int v):判斷v頂點與s頂點是否存在路徑3.public Stack pathTo(int v):找出從起點s到頂點v的路徑(就是該路徑經(jīng)過的頂點)

代碼實現(xiàn)

/**
 * 路徑查找
 *
 * @author alvin
 * @date 2022/10/31
 * @since 1.0
 **/
public class DepthFirstPaths {
    //索引代表頂點，值表示當前頂點是否已經(jīng)被搜索
    private boolean[] marked;
    //起點
    private int s;
    //索引代表頂點，值代表從起點s到當前頂點路徑上的最后一個頂點
    private int[] edgeTo;

    //構(gòu)造深度優(yōu)先搜索對象，使用深度優(yōu)先搜索找出G圖中起點為s的所有路徑
    public DepthFirstPaths(Graph G, int s){
        //初始化marked數(shù)組
        this.marked = new boolean[G.V()];
        //初始化起點
        this.s = s;
        //初始化edgeTo數(shù)組
        this.edgeTo = new int[G.V()];

        dfs(G,s);
    }

    //使用深度優(yōu)先搜索找出G圖中v頂點的所有相鄰頂點
    private void dfs(Graph G, int v){
        //把v表示為已搜索
        marked[v] = true;

        //遍歷頂點v的鄰接表，拿到每一個相鄰的頂點，繼續(xù)遞歸搜索
        for (Integer w : G.adj(v)) {
            //如果頂點w沒有被搜索，則繼續(xù)遞歸搜索

            if (!marked[w]){
                edgeTo[w] = v;//到達頂點w的路徑上的最后一個頂點是v
                dfs(G,w);
            }

        }
    }

    //判斷w頂點與s頂點是否存在路徑
    public boolean hasPathTo(int v){
        return marked[v];
    }

    //找出從起點s到頂點v的路徑(就是該路徑經(jīng)過的頂點)
    public Stack<Integer> pathTo(int v){
        if (!hasPathTo(v)){
            return null;
        }

        //創(chuàng)建棧對象，保存路徑中的所有頂點
        Stack<Integer> path = new Stack<>();

        //通過循環(huán)，從頂點v開始，一直往前找，到找到起點為止
        for (int x = v; x!=s;x = edgeTo[x]){
            path.push(x);
        }

        //把起點s放到棧中
        path.push(s);

        return path;
    }
}

測試：

public class DepthFirstPathsTest {

    @Test
    public void test() {
        //城市數(shù)量
        int totalNumber =  20;
        Graph G = new Graph(totalNumber);
        //添加城市的交通路線
        G.addEdge(0,1);
        G.addEdge(6,9);
        G.addEdge(1,8);
        G.addEdge(1,12);
        G.addEdge(8,12);
        G.addEdge(6,10);
        G.addEdge(4,8);

        DepthFirstPaths depthFirstPaths = new DepthFirstPaths(G, 0);
        Stack<Integer> path = depthFirstPaths.pathTo(12);
        StringBuilder sb = new StringBuilder();
        //遍歷棧對象
        for (Integer v : path) {
            sb.append(v+"->");
        }

        sb.deleteCharAt(sb.length()-1);
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb);
    }
}