[[398324]]

本文轉(zhuǎn)載自微信公眾號(hào)「貝塔學(xué)JAVA」，作者Silently9527。轉(zhuǎn)載本文請(qǐng)聯(lián)系貝塔學(xué)JAVA公眾號(hào)。

前言

在前面兩篇中我們通過深度優(yōu)先搜索可以從圖中找出一條通過頂點(diǎn)v到頂點(diǎn)w的路徑，但是深度優(yōu)先搜索與頂點(diǎn)的輸入有很大的關(guān)系，找出來的路徑也不一定是最短的，通常情況下我們很多時(shí)候需要找出圖中的最短路徑，比如：地圖功能。這里我們就需要使用到廣度優(yōu)先搜索算法

廣度優(yōu)先搜索

依然使用之前定義的尋找路徑的API

public class Paths { 
    Paths(Graph graph, int s); 
     
    boolean hasPathTo(int v); //判斷出從s->v是否存在路徑 
     
    Iterable<Integer> pathTo(int v); //如果存在路徑，返回路徑 
} 

在廣度優(yōu)先搜索中，為了找出最短路徑，我們需要按照起點(diǎn)的順序來遍歷所有的頂點(diǎn)，而不在是使用遞歸來實(shí)現(xiàn);算法的思路：

• 使用隊(duì)列來保存已經(jīng)被標(biāo)記過但是鄰接表還未被遍歷過的頂點(diǎn)
• 取出隊(duì)列中的下一個(gè)頂點(diǎn)v并標(biāo)記它
• 將v相鄰的所有未被標(biāo)記的頂點(diǎn)加入到隊(duì)列

在該算法中，為了保存路徑，我們依然需要使用一個(gè)邊的數(shù)組edgeTo[]，用一顆父鏈樹來表示根節(jié)點(diǎn)到所有連通頂點(diǎn)的最短路徑。

public class BreadthFirstPaths { 
    private boolean marked[]; 
    private int[] edgeTo; 
    private int s; 
    private Queue<Integer> queue = new LinkedListQueue<>(); 
 
    public BreadthFirstPaths(Graph graph, int s) { 
        this.s = s; 
        this.marked = new boolean[graph.V()]; 
        this.edgeTo = new int[graph.V()]; 
 
        bfs(graph, s); 
    } 
 
    private void bfs(Graph graph, int s) { 
        this.marked[s] = true; 
        this.queue.enqueue(s); 
        while (!this.queue.isEmpty()) { 
            Integer v = this.queue.dequeue(); 
            for (int w : graph.adj(v)) { 
                if (!this.marked[w]) { 
                    this.marked[w] = true; 
                    this.edgeTo[w] = v; 
                    this.queue.enqueue(w); 
                } 
            } 
        } 
 
 
    } 
 
    public boolean hasPathTo(int v) { 
        return this.marked[v]; 
    } 
 
    public Iterable<Integer> pathTo(int v) { 
        if (!hasPathTo(v)) { 
            throw new IllegalStateException("s不能到達(dá)v"); 
        } 
        Stack<Integer> stack = new LinkedListStack<>(); 
        stack.push(v); 
        while (edgeTo[v] != s) { 
            stack.push(edgeTo[v]); 
            v = edgeTo[v]; 
        } 
        stack.push(s); 
        return stack; 
    } 
} 

以下圖為列，來看看廣度優(yōu)先搜索的運(yùn)行軌跡

單元測試的代碼：

@Test 
public void test() { 
    Graph graph = new Graph(8); 
    graph.addEdge(0, 1); 
    graph.addEdge(0, 2); 
    graph.addEdge(0, 5); 
    graph.addEdge(1, 3); 
    graph.addEdge(2, 4); 
    graph.addEdge(4, 3); 
    graph.addEdge(5, 3); 
    graph.addEdge(6, 7); 
 
    BreadthFirstPaths paths = new BreadthFirstPaths(graph, 0); 
    System.out.println(paths.hasPathTo(5)); 
    System.out.println(paths.hasPathTo(2)); 
    System.out.println(paths.hasPathTo(6)); 
 
    paths.pathTo(5).forEach(System.out::print); 
    System.out.println(); 
    paths.pathTo(4).forEach(System.out::print); 
    System.out.println(); 
    paths.pathTo(2).forEach(System.out::print); 
    System.out.println(); 
    paths.pathTo(3).forEach(System.out::print); 
 
} 

執(zhí)行的結(jié)果與我們分析的運(yùn)行軌跡一致

符號(hào)圖

最近幾篇文章一起學(xué)習(xí)到的圖算法都是以數(shù)字作為了頂點(diǎn)，是因?yàn)閿?shù)字來實(shí)現(xiàn)這些算法會(huì)非常的簡潔方便，但是在實(shí)際的場景中，通常都是使用的字符作為頂點(diǎn)而非數(shù)字，比如：地圖上的位置、電影與演員的關(guān)系。

為了滿足實(shí)際的場景，我們只需要在數(shù)字與字符串的關(guān)系做一個(gè)映射，此時(shí)我們會(huì)想到之前文章實(shí)現(xiàn)的map(通過二叉樹實(shí)現(xiàn)map、紅黑樹實(shí)現(xiàn)map、哈希表實(shí)現(xiàn)map等等，有興趣的同學(xué)可以去翻翻)，使用Map來維護(hù)字符串和數(shù)字的映射關(guān)系。

public interface SymbolGraph { 
    boolean contains(String key); //判斷是否存在頂點(diǎn) 
 
    int index(String key); //通過名稱返回對(duì)應(yīng)的數(shù)字頂點(diǎn) 
 
    String name(int v); //通過數(shù)字頂點(diǎn)返回對(duì)應(yīng)的字符名稱 
 
    Graph graph(); 
} 

實(shí)現(xiàn)的思路：

• 使用Map來保存字符串-數(shù)字的映射，key為字符串，value為數(shù)字
• 使用一個(gè)數(shù)組來反向映射數(shù)字-字符串，數(shù)組的下標(biāo)對(duì)應(yīng)數(shù)字頂點(diǎn)，值對(duì)應(yīng)字符串名稱
• 假設(shè)構(gòu)造圖的頂點(diǎn)與邊是通過字符串來表示的，如：a,b,c,d\nb,a,h,l,p\ng,s,z 使用\n分隔的每段第一個(gè)字符串表示頂點(diǎn)v，后面的表示與頂點(diǎn)v相連的相鄰頂點(diǎn);

實(shí)際的過程可以根據(jù)具體情況來確定，不一定非得這種字符串，可以來源于數(shù)據(jù)庫，也可以來源于網(wǎng)路的請(qǐng)求。

代碼實(shí)現(xiàn)如下：

public class SymbolGraph { 
    private Map<String, Integer> map = new RedBlack23RedBlackTreeMap<>(); 
    private String[] keys; 
    private Graph graph; 
 
    public SymbolGraph(String text) { 
        Arrays.stream(text.split("\n")).forEach(line -> { 
            String[] split = line.split(","); 
            for (int i = 0; i < split.length; i++) { 
                map.put(split[i], i); 
            } 
        }); 
 
        this.keys = new String[map.size()]; 
        map.keys().forEach(key -> { 
            this.keys[this.map.get(key)] = key; 
        }); 
 
        this.graph = new Graph(this.keys.length); 
        Arrays.stream(text.split("\n")).forEach(line -> { 
            String[] split = line.split(","); 
            int v = this.map.get(split[0]); 
            for (int i = 1; i < split.length; i++) { 
                this.graph.addEdge(v, this.map.get(split[i])); 
            } 
        }); 
         
    } 
 
    public boolean contains(String key) { 
        return map.contains(key); 
    } 
 
    public int index(String key) { 
        return map.get(key); 
    } 
 
    public String name(int index) { 
        return this.keys[index]; 
    } 
 
    public Graph graph() { 
        return this.graph; 
    } 
 
    public static void main(String[] args) { 
        System.out.println(Arrays.toString("323\n2323".split("\n"))); 
    } 
} 

文中所有源碼已放入到了github倉庫:https://github.com/silently9527/JavaCore