圖形結構

原理

圖(graph)，是一種用來描述點與點關係的資料結構，也可以說是記錄關聯的結構，它和樹狀結構長的得像，而他們的關係在於
樹是一種圖
那什麼時後，它是圖而不是樹呢?
出現一個環時。
他沒有連通時。
一張圖會由數個節點以及數條邊所構成，節點與節點間使用邊來相接，在數學上通常定義成G = (V,E)來表示，其中V是所有節點所成的集合，而E代表所有的邊所成的集合。圖(graph)畫出來長的如下圖。



接下來我們來認識一些名詞。
頂點(vertex) : 上圖中的A、B、C就為三個項點。
邊(edge) : 上圖中那個每個項點的連線，就稱為邊。
相鄰(adjacent) : 例如上圖中的A與B就為相鄰的，其它的項點也都如此。
附著(incident) : 上圖中，我們可以說明，邊{A,C}與邊{A,B}『附著』在項點 A 。
路徑(path) : 代表某個項點到某個項點的過程。
簡單路徑(simple path) : 在上圖中 A 到 D 的路徑可能有ACBD和ABD，這時我們可以稱ABD為簡單路徑。
長度(length) : 一條路徑上的長度是指該路徑上所有邊的數量。
分支度(degree) : 例如上圖中，我們可以稱項點 B 的分支度為 3 ，但在有向圖中會分成外分支度與內分支度。
子圖(Subgraph) : 請看下圖。