無(wú)向圖的處理算法（三）

JeOam 發(fā)布于2019-08-14 12:10 / 3064人閱讀

摘要：那還有一個(gè)重要的問題就是，從到是否存在一條路徑，如果有找出其中最短的那條。最短路徑問題當(dāng)然這路考慮的是每條邊的都是權(quán)值為的情況。解決這個(gè)問題的算法就是廣度優(yōu)先搜索算法下面給出其實(shí)現(xiàn)代碼，其中的使用了一個(gè)隊(duì)列用來保存需要遍歷的頂點(diǎn)。

上一篇講了從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)是否存在路徑，用的時(shí)深度優(yōu)先搜索。那還有一個(gè)重要的問題就是，“從s到v是否存在一條路徑，如果有找出其中最短的那條。”最短路徑問題
當(dāng)然這路考慮的是每條邊的都是權(quán)值為1的情況。
解決這個(gè)問題的算法就是廣度優(yōu)先搜索算法
下面給出其實(shí)現(xiàn)代碼，其中的使用了一個(gè)隊(duì)列用來保存需要遍歷的頂點(diǎn)。其實(shí)很上一篇中的代碼結(jié)構(gòu)差不多，只不過遍歷的頂點(diǎn)是依次從隊(duì)列中取出的

package Graph;

import java.util.Stack;

import Queue.Queue;

public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;

    public BreadthFirstPaths(Graph G,int s)
    {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        bfs(G,s);
    }
    private void bfs(Graph G,int s)
    {
        Queue queue = new Queue();
        marked[s] = true;
        queue.enqueue(s);
        while(!queue.isEmpty())
        {
            int v = queue.dequeue();//從隊(duì)列中刪除改頂點(diǎn)
            for(int w:G.adj(v))//對(duì)該頂點(diǎn)相鄰的所有頂點(diǎn)進(jìn)行遍歷，標(biāo)記為訪問過，同時(shí)加入隊(duì)列
            {
                edgeTo[w] = v;
                marked[w] = true;
                queue.enqueue(w);
            }
        }
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }
    public Iterable pathTo(int v)
    {
        Stack path = new Stack();
        while(edgeTo[v] != s)//同上一篇，通過該數(shù)組往上回溯
        {
            path.push(v);
            v = edgeTo[v];
        }
        path.push(s);
        return path;
    }
}