国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

無向圖的處理算法（二）

bluesky / 425人閱讀

摘要：在圖中，我們很自然地會問這幾個問題從一個頂點(diǎn)能否到達(dá)頂點(diǎn)以為頂點(diǎn)能到達(dá)的所有頂點(diǎn)解決能否到達(dá)問題的算法就是深度優(yōu)先算法，使用深度優(yōu)先算法獲得的從到的路徑的時(shí)間與路徑的長度成正比。

在圖中，我們很自然地會問這幾個問題

從一個頂點(diǎn)s能否到達(dá)頂點(diǎn)v?

以s為頂點(diǎn)能到達(dá)的所有頂點(diǎn)?

解決能否到達(dá)問題的算法就是深度優(yōu)先算法，使用深度優(yōu)先算法獲得的從s到v的路徑的時(shí)間與路徑的長度成正比。

package Graph;

import java.util.Stack;

//基于深度優(yōu)先算法，搜索查找圖中的路徑
//解決單點(diǎn)路徑問題，即，從一點(diǎn)開始是否存在到另一個點(diǎn)的路徑
public class DepthFirstPaths {
    private boolean[] marked;//這個頂點(diǎn)調(diào)用過dfs了嗎
    private int[] edgeTo;//從起點(diǎn)到該點(diǎn)路徑上的最后一個頂點(diǎn)
    private final int s;//起點(diǎn)

    public DepthFirstPaths(Graph g,int s)
    {
        marked = new boolean[g.V()];
        edgeTo = new int[g.V()];
        this.s = s;
        dfs(g,s);
    }

    private void dfs(Graph G,int V){
        marked[V] = true;
        for(int w: G.adj(V)){
            if(!marked[w]){
                edgeTo[w] = V;//表示這條路徑上，w之前是v
                dfs(G,w);
            }
        }
    }

    public boolean hasPathTo(int V){
        return marked[V];
    }

    public Iterable pathTo(int V){
        if(!hasPathTo(V)) return null;
        Stack path = new Stack();
        for(int x = V;x != s; x = edgeTo[x])//從終點(diǎn)開始往上回溯
            path.push(x);
        path.push(s);
        return path;

    }
}

這樣通過調(diào)用pathTo(v)就可以知道到任意頂點(diǎn)v的路徑。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/64340.html

相關(guān)文章

  • 無向圖的實(shí)現(xiàn)和一些常用算法（一）

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

    Lsnsh 評論0 收藏0

  • 無向圖的處理算法（四）連通分量

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

    asce1885 評論0 收藏0

  • 無向圖的處理算法（三）

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

    JeOam 評論0 收藏0

  • 算法（第4版） Chapter 4.1 無向圖

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

    kamushin233 評論0 收藏0

  • 算法第四版4.1-無向圖詳解

    摘要：樹是一副無環(huán)連通圖。互不相連的樹組成的集合稱為森林。表示無向圖的數(shù)據(jù)類型圖的基本操作的兩個構(gòu)造，得到頂點(diǎn)數(shù)和邊數(shù)，增加一條邊。該方法不符合第一個條件，上百萬個頂點(diǎn)的圖是很常見的空間不滿足。 四種重要的圖模型： 無向圖（簡單連接） 有向圖（連接有方向性） 加權(quán)圖（連接帶有權(quán)值） 加權(quán)有向圖（連接既有方向性又帶有權(quán)值） 無向圖 定義：由一組頂點(diǎn)和一組能夠?qū)蓚€頂點(diǎn)相連的邊組成。 特殊：...

    scola666 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<