[資料結構] 圖(Graph) - iT 邦幫忙
文章推薦指數： 80 %
圖(Graph)，在資料結構上指的是點和點之間的關聯的東西，並不是數學定義上的兩點成一線，三點成一面的那種圖 ... 無相圖 https://ithelp.ithome.com.tw/upload/images/
2019iT邦幫忙鐵人賽
DAY
21
0
SoftwareDevelopment
30天學演算法和資料結構系列第
21篇
[資料結構]圖(Graph)
2019鐵人賽
資料結構
ramonliao
2018-11-0523:57:247373瀏覽
圖(Graph)，在資料結構上指的是點和點之間的關聯的東西，並不是數學定義上的兩點成一線，三點成一面的那種圖。
一張圖由數條邊(Edge)和數個點(Vertex)所構成，點和點之間可用邊相連，表示這兩個點之間有所關聯。
當然，兩個點之間可以有很多個邊，代表很多關係，又或者是一個點可以與很多個點相連接。
1.同構(Isomorphism/Isomorphic)
指的是兩張圖的連接方式一模一樣的，而圖上的點可以任意移動，邊不論直的彎的皆可。
2.有向圖&無向圖
有向圖，邊有方向性，表示兩點之間為單向關係。
無向圖，邊無方向性，表示兩點之間為雙向關係。
3.權重
邊加上權重，代表兩點之間的關係
點加上權狀，代表狀態
4.名稱or代號
點可以有名稱或者代號
5.圖的資料結構
圖是由點和邊所組成，為了方便人了解，所以視覺化。
但實際上在電腦中的儲存方式卻有很多不同的方法。
可以有陣列或矩陣的方式儲存。
EagleList
將圖用陣列的方式，記錄點與點之間的邊
0
0
1
3
1
3
3
4
AdjacencyMatrix
把一張圖上的點依序標示編號，然後建立一個矩陣，來記錄連接資訊。
方陣中的每一個元素都代表著某兩點的連接資訊。
0
1
2
3
4
5
6
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
0
0
1
0
4
0
0
0
0
1
0
0
5
0
0
0
1
0
0
0
6
1
0
0
0
0
1
0
舉例來說，0分別有一條連向3和4的邊，所以第0列的3、4行為1。
AdjacencyLists
在每一個點後方，串連所有相鄰有連接的點
無相圖
0 [1,3]
1 [0,3]
2
3 [0,1,4]
4 [3]
有向圖
0 [3,4]
1
2
3 [5]
4 [4]
5 [3]
6 [0,5]
圖的遍歷(GraphTraversal)
深度優先搜尋Depth-firstSearch
廣度優先搜尋Breadth-firstSearch
(之後會另外討論~)
特殊圖
IntersectionGraph
若兩個物件有交集關係(非空集合)，就可以表示成圖。
又或者是：
0={a,b,c}
1={a,d}
2={e}
3={b,d,f}
4={f}
DependencyGraph
是將各個物件所仰賴或依賴的對象關係表示成圖。
A>C;E
標記
{{result.label}}
{{result.account}}
關閉
延伸文章資訊
- 1Graph: Depth-First Search(DFS，深度優先搜尋)
以圖二的迷宮為例，把迷宮矩陣中的每一格定義成一個vertex，若兩個vertex之間有路，則建立edge相連。若要在迷宮中尋找抵達終點的路線，通常會先選擇其中一條路線，只要有路 ...
- 2【資料結構】圖論（Graph）Part 1
圖（Graph）通常以G 來代表，裡面包含兩個集合… ... Trees）是一個很重要的課題，它指的是在一個包含權重的無相圖中，找到一個生成樹，它的路徑權重加起來是最小的。
- 3Graph - 演算法筆記
Graph 中文翻做「圖」。此處談及的「圖」並不是指圖片或者圖形。「圖」是一種用來記錄關聯、關係的東西。 一張圖由數個點（ vertex ）以及數條邊（ edge ）所構成。
- 4寳像無相圖
《寳像無相圖》. ······方丈之地······閉關三年······七易其稿······心血呈現······ 當代佛教繪畫巨作. 七十米油畫組圖長卷《寳像無相圖》 ...
- 5無相佛精雕圖-新人首單立減十元-2021年12月 - 淘寶
去哪兒購買無相佛精雕圖？當然來淘寶海外，淘寶當前有1170件無相佛精雕圖相關的商品在售。 ... 精雕圖作圖洋花接圖玉雕製圖石雕做圖佛像觀音畫圖花鳥灰度圖五金.
