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

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

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

前言

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

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

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

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

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

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

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

算法詳解

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

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

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

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

實(shí)現(xiàn)

API設(shè)計(jì)

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

代碼實(shí)現(xiàn)

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

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

        dfs(G,s);
    }

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

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

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

        }
    }

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

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

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

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

        //把起點(diǎn)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);
    }
}