資訊專欄INFORMATION COLUMN
摘要：什么是圖前面說完了樹這種數(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)的圖片演示吧：
像上圖這樣的數(shù)據(jù)結(jié)構(gòu)就叫做圖了，圖中的每個節(jié)點叫做 頂點 ，各個頂點之間的連接關(guān)系叫做 邊 ，每個頂點有多少條邊，叫做這個頂點的 度 。其實圖這種數(shù)據(jù)結(jié)構(gòu)比較適合用來存儲我們常用的微信、微博好友關(guān)系。例如存儲微信好友，例如兩個人互加了微信，就相當(dāng)于在兩個頂點之間加上一條邊，而頂點的度則表示一個人有多少微信好友。
而微博這樣的存儲關(guān)系，要稍微復(fù)雜一些，因為微博允許當(dāng)方面關(guān)注，例如 A 關(guān)注了 B ，而 B 可以不關(guān)注 A，這樣的關(guān)系，我們可以在圖中引入方向的概念，先看下圖：
例如 A 關(guān)注了 B，那么直接將 A 的邊指向 B 即可。這樣有方向關(guān)系的圖，叫做 有向圖 ，顯然，沒有方向關(guān)系的圖，就叫做 無向圖 。
無向圖中有度的概念，表示一個頂點有多少條邊，而有向圖中的度，則還有 入度 和 出度 的區(qū)分，例如 A 指向 B，叫做 A 頂點的出度，E 指向了 A，叫做 A 的入度。不難理解，對應(yīng)到微博的關(guān)系中，一個頂點的出度，就表示他關(guān)注了多少人，入度，則表示他有多少粉絲。
2. 圖是如何存儲的？
圖有兩種存儲的方式，第一種叫做鄰接矩陣，其底層是利用二維數(shù)組來存儲的。對于無向圖，如果頂點 i 和 j 之間有邊，則在二維數(shù)組中 A[i] [j] 和 A[j] [i] 位置處標記為 1 ，對于有向圖，如果 i 指向了 j，則將二維數(shù)組中 A[i] [j] 位置標記為 1，類似，如果 j 指向了 i，則將二維數(shù)組中 A[j] [i] 位置標記為 1?？聪聢D的說明就很容易明白了：
這種存儲方式雖然支持較為高效的查找操作，因為可以直接根據(jù)數(shù)組下標取出數(shù)據(jù)，但是存在的問題便是比較浪費存儲空間，特別是對于數(shù)據(jù)量較大的情況。
另一種更加常用的圖存儲方式是鄰接表，每個頂點對應(yīng)一個鏈表，就像下圖這樣：
上面是使用的有向圖，每個頂點對應(yīng)的鏈表存儲的是該頂點所指向的頂點，如果是無向圖的話，那就更簡單了，每個頂點鏈表存儲的是與該頂點有邊關(guān)系的頂點。
3. 簡單實現(xiàn)一個圖
接下來我是用代碼簡單使用了一個圖，你可以看看，順便理解一下：
public class Graph {
private int vertex;//圖中的頂點個數(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();
}
}
//兩個頂點之間建立邊關(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);
}
//刪除頂點之間的邊
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);
}
//列出與某頂點有邊關(guā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://www.ezyhdfw.cn/yun/74071.html
摘要：在等機構(gòu)新提出的論文中，其采用了大規(guī)模數(shù)據(jù)集與深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)圖像的自然結(jié)構(gòu)，從而進一步分離圖像的前景與背景。一張手動摳圖的前景圖擁有簡單背景作為輸入。對于每一張測試圖像，按照降序從第列到第列顯示了度量下的排名結(jié)果排名到。 摳圖，一直是一件體力活，它需要大量的操作與時間。而傳統(tǒng)摳圖算法主要是以色彩為特征分離前景與背景，并在小數(shù)據(jù)集上完成，而這就造成了傳統(tǒng)算法的局限性。在 Adobe 等機構(gòu)新...
摘要：圖關(guān)聯(lián)矩陣在關(guān)聯(lián)矩陣表示的圖中，矩陣的行表示頂點，列表示邊。如圖，頂點數(shù)是，邊的數(shù)量是，用鄰接矩陣表示圖需要的空間是，而使用關(guān)聯(lián)矩陣表示圖需要的空間是。廣度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是隊列。深度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是棧。 定義 圖和散列表、二叉樹一樣，是一種非線性數(shù)據(jù)結(jié)構(gòu)。如圖1所示，圖由一系列頂點以及連接頂點的邊構(gòu)成。由一條邊連接在一起的頂點成為相鄰頂點，比如A和B、A和D是相鄰的，而A和...
摘要：近幾年來，目標檢測算法取得了很大的突破。本文主要講述算法的原理，特別是算法的訓(xùn)練與預(yù)測中詳細細節(jié)，最后將給出如何使用實現(xiàn)算法。但是結(jié)合卷積運算的特點，我們可以使用實現(xiàn)更高效的滑動窗口方法。這其實是算法的思路。下面將詳細介紹算法的設(shè)計理念。 1、前言當(dāng)我們談起計算機視覺時，首先想到的就是圖像分類，沒錯，圖像分類是計算機視覺最基本的任務(wù)之一，但是在圖像分類的基礎(chǔ)上，還有更復(fù)雜和有意思的任務(wù)，如目...
摘要：在本次課程中，著重講解的是傳統(tǒng)的機器學(xué)習(xí)技術(shù)及各種算法。回歸對連續(xù)型數(shù)據(jù)進行預(yù)測趨勢預(yù)測等除了分類之外，數(shù)據(jù)挖掘技術(shù)和機器學(xué)習(xí)技術(shù)還有一個非常經(jīng)典的場景回歸。 摘要： 什么是數(shù)據(jù)挖掘？什么是機器學(xué)習(xí)？又如何進行Python數(shù)據(jù)預(yù)處理？本文將帶領(lǐng)大家一同了解數(shù)據(jù)挖掘和機器學(xué)習(xí)技術(shù)，通過淘寶商品案例進行數(shù)據(jù)預(yù)處理實戰(zhàn)，通過鳶尾花案例介紹各種分類算法。 課程主講簡介：韋瑋，企業(yè)家，資深I(lǐng)T領(lǐng)...
閱讀 2307·2019-08-30 15:53
閱讀 2526·2019-08-30 12:54
閱讀 1440·2019-08-29 16:09
閱讀 795·2019-08-29 12:14
閱讀 821·2019-08-26 10:33
閱讀 2600·2019-08-23 18:36
閱讀 3050·2019-08-23 18:30
閱讀 2202·2019-08-22 17:09
