數據結構與算法——圖

Paul_King 發布于2019-08-16 16:22 / 2800人閱讀

摘要：什么是圖前面說完了樹這種數據結構，接下來在看看一種更加復雜的非線性數據結構圖。其實圖這種數據結構比較適合用來存儲我們常用的微信微博好友關系。

1.  什么是圖？

前面說完了樹這種數據結構，接下來在看看一種更加復雜的非線性數據結構——圖。

先看看下面圖這種數據結構的圖片演示吧：

像上圖這樣的數據結構就叫做圖了，圖中的每個節點叫做頂點，各個頂點之間的連接關系叫做邊，每個頂點有多少條邊，叫做這個頂點的度。其實圖這種數據結構比較適合用來存儲我們常用的微信、微博好友關系。例如存儲微信好友，例如兩個人互加了微信，就相當于在兩個頂點之間加上一條邊，而頂點的度則表示一個人有多少微信好友。

而微博這樣的存儲關系，要稍微復雜一些，因為微博允許當方面關注，例如 A 關注了 B ，而 B 可以不關注 A，這樣的關系，我們可以在圖中引入方向的概念，先看下圖：

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

無向圖中有度的概念，表示一個頂點有多少條邊，而有向圖中的度，則還有入度和出度的區分，例如 A 指向 B，叫做 A 頂點的出度，E 指向了 A，叫做 A 的入度。不難理解，對應到微博的關系中，一個頂點的出度，就表示他關注了多少人，入度，則表示他有多少粉絲。

2. 圖是如何存儲的？

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

這種存儲方式雖然支持較為高效的查找操作，因為可以直接根據數組下標取出數據，但是存在的問題便是比較浪費存儲空間，特別是對于數據量較大的情況。

另一種更加常用的圖存儲方式是鄰接表，每個頂點對應一個鏈表，就像下圖這樣：

上面是使用的有向圖，每個頂點對應的鏈表存儲的是該頂點所指向的頂點，如果是無向圖的話，那就更簡單了，每個頂點鏈表存儲的是與該頂點有邊關系的頂點。

3. 簡單實現一個圖

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

public class Graph {
    private int vertex;//圖中的頂點個數
    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();
        }
    }

    //兩個頂點之間建立邊關系
    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);
    }

    //刪除頂點之間的邊
    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);
    }

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

GPU云服務器云服務器數據與統計圖統計與大數據圖算法與數據結構數據結構與算法

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

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

Adobe提出深度摳圖：利用卷積網絡分離圖像前景與背景

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

soasme 2019-04-25 18:10 評論0 收藏0
學習JavaScript數據結構與算法 — 圖

摘要：圖關聯矩陣在關聯矩陣表示的圖中，矩陣的行表示頂點，列表示邊。如圖，頂點數是，邊的數量是，用鄰接矩陣表示圖需要的空間是，而使用關聯矩陣表示圖需要的空間是。廣度優先搜索算法數據結構是隊列。深度優先搜索算法數據結構是棧。定義圖和散列表、二叉樹一樣，是一種非線性數據結構。如圖1所示，圖由一系列頂點以及連接頂點的邊構成。由一條邊連接在一起的頂點成為相鄰頂點，比如A和B、A和D是相鄰的，而A和...

yiliang 2019-08-22 11:09 評論0 收藏0
YOLO算法的原理與實現

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

zhangfaliang 2019-04-25 18:23 評論0 收藏0
Python數據挖掘與機器學習技術入門實戰

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

孫吉亮 2019-07-30 16:14 評論0 收藏0