成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

Lsnsh / 2073人閱讀

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

無向圖的數(shù)據(jù)結(jié)構(gòu) 
Class Graph
private final int V;  邊數(shù)
private int E; 邊的數(shù)目
private Bag[] adj; 鄰接表，存儲與該節(jié)點相鄰的節(jié)點，一個鏈表數(shù)組
無向圖的API 
public class Graph
    Graph(int V)   創(chuàng)建一個含有V個節(jié)點但不含邊的無向圖
    Graph(In)    從輸入流中讀取一幅圖
    int V()      返回圖中有多少個節(jié)點
    int E()      邊數(shù)
    addEdge(int v,int w)  添加一條邊
    Iterable adj(int v)   V節(jié)點相鄰的所有頂點
    String toString       對象的字符串表示

實現(xiàn)很簡單

package Graph;

import In.In;

public class Graph {
    private final int V;
    private int E;
    private Bag[] adj;   //鄰接表

    public Graph(int V){
        this.V = V;
        this.E = 0;
        adj = (Bag[]) new Bag[V];
        for(int v = 0;v < V;v++){
            adj[v] = new Bag();
        }
    }

    public Graph(In in){
        this(in.readInt());
        int E = in.readInt();
        for(int i = 0;i < E;i++){
            int v = in.readInt();
            int w = in.readInt();
            addEdge(v,w);
        }
    }

    public int V(){ return V;}
    public int E(){ return E;}

    public void addEdge(int v,int w){
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterableadj(int v){
        return adj[v];
    }

}

既然實現(xiàn)了圖這種數(shù)據(jù)結(jié)構(gòu)，那么接下來可以考慮圖的處理算法了。見下一篇

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64312.html

相關(guān)文章

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

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

    kamushin233 評論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

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

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

    scola666 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法——圖

    摘要：什么是圖前面說完了樹這種數(shù)據(jù)結(jié)構(gòu)，接下來在看看一種更加復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)圖。其實圖這種數(shù)據(jù)結(jié)構(gòu)比較適合用來存儲我們常用的微信微博好友關(guān)系。 1. 什么是圖？ 前面說完了樹這種數(shù)據(jù)結(jié)構(gòu)，接下來在看看一種更加復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)——圖。 先看看下面圖這種數(shù)據(jù)結(jié)構(gòu)的圖片演示吧： showImg(https://img-blog.csdnimg.cn/20190319204147662.p...

    Paul_King 評論0 收藏0

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

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

    JeOam 評論0 收藏0

發(fā)表評論

0條評論

Lsnsh

男|高級講師

TA的文章

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