無向圖的處理算法（三）

JeOam 發布于2019-08-14 12:10 / 3070人閱讀

摘要：那還有一個重要的問題就是，從到是否存在一條路徑，如果有找出其中最短的那條。最短路徑問題當然這路考慮的是每條邊的都是權值為的情況。解決這個問題的算法就是廣度優先搜索算法下面給出其實現代碼，其中的使用了一個隊列用來保存需要遍歷的頂點。

上一篇講了從一個頂點到另一個頂點是否存在路徑，用的時深度優先搜索。那還有一個重要的問題就是，“從s到v是否存在一條路徑，如果有找出其中最短的那條。”最短路徑問題
當然這路考慮的是每條邊的都是權值為1的情況。
解決這個問題的算法就是廣度優先搜索算法
下面給出其實現代碼，其中的使用了一個隊列用來保存需要遍歷的頂點。其實很上一篇中的代碼結構差不多，只不過遍歷的頂點是依次從隊列中取出的

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();//從隊列中刪除改頂點
            for(int w:G.adj(v))//對該頂點相鄰的所有頂點進行遍歷，標記為訪問過，同時加入隊列
            {
                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)//同上一篇，通過該數組往上回溯
        {
            path.push(v);
            v = edgeTo[v];
        }
        path.push(s);
        return path;
    }
}

GPU云服務器云服務器 webrtc agc算法三負載均衡支持三種調度算法字符串處理算法匹配算法 webrtc音頻處理算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64339.html

無向圖的實現和一些常用算法（一）

摘要：無向圖的數據結構邊數邊的數目鄰接表，存儲與該節點相鄰的節點，一個鏈表數組無向圖的創建一個含有個節點但不含邊的無向圖從輸入流中讀取一幅圖返回圖中有多少個節點邊數添加一條邊節點相鄰的所有頂點對象的字符串表示實現很簡單鄰接表既然實現了圖這種數據結無向圖的數據結構 Class Graph private final int V; 邊數 private int E; 邊的數目 privat...

Lsnsh 2019-08-14 12:08 評論0 收藏0
無向圖的處理算法（四）連通分量

這篇講的是連通分量，連通分量是深度優先搜索算法的一個應用。每進行了一次dfs，就會找到一條連通分量。定義如下的API public class CC CC(Graph g) 預處理構造函數 boolean connected(int v,in w) v和w連通嗎 int count() 改圖中的連通分量個數 int id(int v) ...

asce1885 2019-08-14 12:10 評論0 收藏0
無向圖的處理算法（二）

摘要：在圖中，我們很自然地會問這幾個問題從一個頂點能否到達頂點以為頂點能到達的所有頂點解決能否到達問題的算法就是深度優先算法，使用深度優先算法獲得的從到的路徑的時間與路徑的長度成正比。在圖中，我們很自然地會問這幾個問題從一個頂點s能否到達頂點v? 以s為頂點能到達的所有頂點? 解決能否到達問題的算法就是深度優先算法，使用深度優先算法獲得的從s到v的路徑的時間與路徑的長度成正比。 ...

bluesky 2019-08-14 12:11 評論0 收藏0
算法（第4版） Chapter 4.1 無向圖

摘要：邊僅由兩個頂點連接，并且沒有方向的圖稱為無向圖。用分隔符當前為空格，也可以是分號等分隔。深度優先算法最簡搜索起點構造函數找到與起點連通的其他頂點。路徑構造函數接收一個頂點，計算到與連通的每個頂點之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...

kamushin233 2019-08-14 17:14 評論0 收藏0
算法之不定期更新（三）（2018-04-24）

摘要：實現這個想法之后就發現，時間復雜度真的太高了。本期算法小分享就到這里咯剛做完探索里的初級，還有好多已經說爛了的題就不分享了。如果有什么意見或者想法歡迎在評論區和我交流題目 input: n // 代表無向圖的頂點數 // 從1開始 m // 無向圖的邊數 arr1 // 各邊的情況，形如[[1, 2], [3, 4],...]（代表頂點0和頂點2相連，頂點3和頂點4相連） ...

darryrzhong 2019-08-22 16:40 評論0 收藏0