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

資訊專欄INFORMATION COLUMN

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

Paul_King / 2854人閱讀

摘要：什么是圖前面說完了樹這種數(shù)據(jù)結(jié)構(gòu)，接下來在看看一種更加復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)圖。其實(shí)圖這種數(shù)據(jù)結(jié)構(gòu)比較適合用來存儲我們常用的微信微博好友關(guān)系。

1.  什么是圖？

前面說完了樹這種數(shù)據(jù)結(jié)構(gòu)，接下來在看看一種更加復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)——圖。

先看看下面圖這種數(shù)據(jù)結(jié)構(gòu)的圖片演示吧：

像上圖這樣的數(shù)據(jù)結(jié)構(gòu)就叫做圖了，圖中的每個(gè)節(jié)點(diǎn)叫做 頂點(diǎn) ，各個(gè)頂點(diǎn)之間的連接關(guān)系叫做 邊 ，每個(gè)頂點(diǎn)有多少條邊，叫做這個(gè)頂點(diǎn)的 度 。其實(shí)圖這種數(shù)據(jù)結(jié)構(gòu)比較適合用來存儲我們常用的微信、微博好友關(guān)系。例如存儲微信好友，例如兩個(gè)人互加了微信，就相當(dāng)于在兩個(gè)頂點(diǎn)之間加上一條邊，而頂點(diǎn)的度則表示一個(gè)人有多少微信好友。

而微博這樣的存儲關(guān)系，要稍微復(fù)雜一些，因?yàn)槲⒉┰试S當(dāng)方面關(guān)注，例如 A 關(guān)注了 B ，而 B 可以不關(guān)注 A，這樣的關(guān)系，我們可以在圖中引入方向的概念，先看下圖：

例如 A 關(guān)注了 B，那么直接將 A 的邊指向 B 即可。這樣有方向關(guān)系的圖，叫做 有向圖 ，顯然，沒有方向關(guān)系的圖，就叫做 無向圖 。

無向圖中有度的概念，表示一個(gè)頂點(diǎn)有多少條邊，而有向圖中的度，則還有 入度 和 出度 的區(qū)分，例如 A 指向 B，叫做 A 頂點(diǎn)的出度，E 指向了 A，叫做 A 的入度。不難理解，對應(yīng)到微博的關(guān)系中，一個(gè)頂點(diǎn)的出度，就表示他關(guān)注了多少人，入度，則表示他有多少粉絲。

2. 圖是如何存儲的？

圖有兩種存儲的方式，第一種叫做鄰接矩陣，其底層是利用二維數(shù)組來存儲的。對于無向圖，如果頂點(diǎn) i 和 j 之間有邊，則在二維數(shù)組中 A[i] [j] 和 A[j] [i] 位置處標(biāo)記為 1 ，對于有向圖，如果 i 指向了 j，則將二維數(shù)組中 A[i] [j] 位置標(biāo)記為 1，類似，如果 j 指向了 i，則將二維數(shù)組中 A[j] [i] 位置標(biāo)記為 1?？聪聢D的說明就很容易明白了：

這種存儲方式雖然支持較為高效的查找操作，因?yàn)榭梢灾苯痈鶕?jù)數(shù)組下標(biāo)取出數(shù)據(jù)，但是存在的問題便是比較浪費(fèi)存儲空間，特別是對于數(shù)據(jù)量較大的情況。

另一種更加常用的圖存儲方式是鄰接表，每個(gè)頂點(diǎn)對應(yīng)一個(gè)鏈表，就像下圖這樣：

上面是使用的有向圖，每個(gè)頂點(diǎn)對應(yīng)的鏈表存儲的是該頂點(diǎn)所指向的頂點(diǎn)，如果是無向圖的話，那就更簡單了，每個(gè)頂點(diǎn)鏈表存儲的是與該頂點(diǎn)有邊關(guān)系的頂點(diǎn)。

3. 簡單實(shí)現(xiàn)一個(gè)圖

接下來我是用代碼簡單使用了一個(gè)圖，你可以看看，順便理解一下：

public class Graph {
    private int vertex;//圖中的頂點(diǎn)個(gè)數(shù)
    private LinkedList[] list;

    public Graph(int vertex) {
        this.vertex = vertex;
        list = new LinkedList[vertex];
        for (int i = 0; i < vertex; i++) {
            list[i] = new LinkedList();
        }
    }

    //兩個(gè)頂點(diǎn)之間建立邊關(guān)系
    public void addSide(int v1, int v2){
        if (v1 >= vertex || v2 >= vertex || v1 == v2) return;
        if (!list[v1].contains(v2))
            list[v1].add(v2);
        if (!list[v2].contains(v1))
            list[v2].add(v1);
    }

    //刪除頂點(diǎn)之間的邊
    public void removeSide(int v1, int v2){
        if (v1 >= vertex || v2 >= vertex || v1 == v2) return;
        if (list[v1].contains(v2))
            list[v1].remove(v2);
        if (list[v2].contains(v1))
            list[v2].remove(v1);
    }

    //列出與某頂點(diǎn)有邊關(guān)系的所有頂點(diǎn)
    public void listVertexes(int v){
        if (v >= vertex) return;
        System.out.println(list[v].toString());
    }
}

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

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

相關(guān)文章

  • Adobe提出深度摳圖：利用卷積網(wǎng)絡(luò)分離圖像前景與背景

    摘要：在等機(jī)構(gòu)新提出的論文中，其采用了大規(guī)模數(shù)據(jù)集與深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)圖像的自然結(jié)構(gòu)，從而進(jìn)一步分離圖像的前景與背景。一張手動摳圖的前景圖擁有簡單背景作為輸入。對于每一張測試圖像，按照降序從第列到第列顯示了度量下的排名結(jié)果排名到。 摳圖，一直是一件體力活，它需要大量的操作與時(shí)間。而傳統(tǒng)摳圖算法主要是以色彩為特征分離前景與背景，并在小數(shù)據(jù)集上完成，而這就造成了傳統(tǒng)算法的局限性。在 Adobe 等機(jī)構(gòu)新...

    soasme 評論0 收藏0

  • 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 圖

    摘要：圖關(guān)聯(lián)矩陣在關(guān)聯(lián)矩陣表示的圖中，矩陣的行表示頂點(diǎn)，列表示邊。如圖，頂點(diǎn)數(shù)是，邊的數(shù)量是，用鄰接矩陣表示圖需要的空間是，而使用關(guān)聯(lián)矩陣表示圖需要的空間是。廣度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。深度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是棧。 定義 圖和散列表、二叉樹一樣，是一種非線性數(shù)據(jù)結(jié)構(gòu)。如圖1所示，圖由一系列頂點(diǎn)以及連接頂點(diǎn)的邊構(gòu)成。由一條邊連接在一起的頂點(diǎn)成為相鄰頂點(diǎn)，比如A和B、A和D是相鄰的，而A和...

    yiliang 評論0 收藏0

  • YOLO算法的原理與實(shí)現(xiàn)

    摘要：近幾年來，目標(biāo)檢測算法取得了很大的突破。本文主要講述算法的原理，特別是算法的訓(xùn)練與預(yù)測中詳細(xì)細(xì)節(jié)，最后將給出如何使用實(shí)現(xiàn)算法。但是結(jié)合卷積運(yùn)算的特點(diǎn)，我們可以使用實(shí)現(xiàn)更高效的滑動窗口方法。這其實(shí)是算法的思路。下面將詳細(xì)介紹算法的設(shè)計(jì)理念。 1、前言當(dāng)我們談起計(jì)算機(jī)視覺時(shí)，首先想到的就是圖像分類，沒錯(cuò)，圖像分類是計(jì)算機(jī)視覺最基本的任務(wù)之一，但是在圖像分類的基礎(chǔ)上，還有更復(fù)雜和有意思的任務(wù)，如目...

    zhangfaliang 評論0 收藏0

  • Python數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)技術(shù)入門實(shí)戰(zhàn)

    摘要：在本次課程中，著重講解的是傳統(tǒng)的機(jī)器學(xué)習(xí)技術(shù)及各種算法。回歸對連續(xù)型數(shù)據(jù)進(jìn)行預(yù)測趨勢預(yù)測等除了分類之外，數(shù)據(jù)挖掘技術(shù)和機(jī)器學(xué)習(xí)技術(shù)還有一個(gè)非常經(jīng)典的場景回歸。 摘要： 什么是數(shù)據(jù)挖掘？什么是機(jī)器學(xué)習(xí)？又如何進(jìn)行Python數(shù)據(jù)預(yù)處理？本文將帶領(lǐng)大家一同了解數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)技術(shù)，通過淘寶商品案例進(jìn)行數(shù)據(jù)預(yù)處理實(shí)戰(zhàn)，通過鳶尾花案例介紹各種分類算法。 課程主講簡介：韋瑋，企業(yè)家，資深I(lǐng)T領(lǐng)...

    孫吉亮 評論0 收藏0

發(fā)表評論

0條評論

Paul_King

男|高級講師

TA的文章

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