Python數據結構之圖的存儲結構詳解
一、圖的定義
圖是一種比樹更復雜的一種數據結構,在圖結構中,結點之間的關系是任意的,任意兩個元素之間都可能相關,因此,它的應用極廣。圖中的數據元素通常被稱為頂點 ( V e r t e x ) (Vertex) (Vertex), V V V是頂點的有窮非空集合, V R VR VR是兩個頂點之間的關系的集合(可以為空),可以表示為圖 G = { V , { V R } } G=\{V,\{VR\}\} G={V,{VR}}。
二、相關術語
2.1 無向圖
給定圖 G = { V , { E } } G=\{V,\{E\}\} G={V,{E}},若該圖中每條邊都是沒有方向的,則稱其為無向圖
( U n d i g r a p h ) (Undigraph) (Undigraph)。對圖 G G G中頂點 v v v和頂點 w w w的關系,可用無序對 ( v , w ) (v,w) (v,w)表示,它是連接 v v v和 w w w的一條邊 ( E d g e ) (Edge) (Edge)。
2.2 有向圖
給定圖 G = { V , { A } } G=\{V,\{A\}\} G={V,{A}},若該圖中每條邊都是有方向的,則稱其為有向圖
( D i g r a p h ) (Digraph) (Digraph)。對圖 G G G中頂點 v v v和頂點 w w w的關系,可用有序對 < v , w > <v,w> <v,w>表示,它是從 v v v到 w w w的一條弧 ( A r c ) (Arc) (Arc),其中 v v v被稱為弧尾
( T a i l ) (Tail) (Tail), w w w被稱為弧頭
( H e a d ) (Head) (Head)。
弧尾也叫初始點 ( I n i t i a l (Initial (Initial N o d e ) Node) Node),弧頭也叫終端點 ( T e r m i n a l (Terminal (Terminal N o d e ) Node) Node)。
2.3 完全圖
對於任一無向圖,若其頂點的總數目為 n n n,邊的總數目為 e = n ( n − 1 ) 2 e=\frac {n(n-1)} {2} e=2n(n−1),則稱其為完全圖
( C o m p l e t e d (Completed (Completed G r a p h ) Graph) Graph)。
2.4 有向完全圖
對於任一有向圖,若其頂點的總數目為 n n n,邊的總數目為 e = n ( n − 1 ) e=n(n-1) e=n(n−1),則稱其為有向完全圖
。
2.5 稀疏圖和稠密圖
對於具有 n n n個頂點, e e e條邊或弧的圖來說,若 e e e很小,比如 e < n log n e<n\log n e<nlogn,則稱其為稀疏圖
( S p a r s e (Sparse (Sparse G r a p h ) Graph) Graph),反之稱其為稠密圖
( D e n s e (Dense (Dense G r a p h ) Graph) Graph)。
2.6 權和網
賦予圖中邊或弧的數值稱為權
( W e i g h t ) (Weight) (Weight),它可以表示從一個頂點到另一個頂點的距離;帶權的圖稱為網
( N e t w o r k ) (Network) (Network)。
2.7 稀疏網和稠密網
帶權的稀疏圖、稠密圖稱為稀疏網
、稠密網
。
2.8 子圖
對於圖 G = { V , { E } } G=\{V,\{E\}\} G={V,{E}}和圖 G ′ = { V ′ , { E ′ } } G’=\{V’,\{E’\}\} G′={V′,{E′}},若 V ′ ⊆ V V’\subseteq V V′⊆V且 E ′ ⊆ E E’\subseteq E E′⊆E,則稱 G ′ G’ G′為 G G G的子圖
( S u b g r a p h ) (Subgraph) (Subgraph)。
2.9 鄰接點
對於無向圖 G = { V , { E } } G=\{V,\{E\}\} G={V,{E}},若 v ∈ V v\in V v∈V、 w ∈ V w\in V w∈V且 ( v , w ) ∈ E (v,w)\in E (v,w)∈E,則稱頂點 v v v和頂點 w w w互為鄰接點
( A d j a c e n t ) (Adjacent) (Adjacent),並稱邊 ( v , w ) (v,w) (v,w)依附 ( I n c i d e n t ) (Incident) (Incident)於頂點 v v v和頂點 w w w,或稱邊 ( v , w ) (v,w) (v,w)與頂點 v v v和頂點 w w w相關聯。
對於有向圖 G = { V , { A } } G=\{V,\{A\}\} G={V,{A}},若 v ∈ V v\in V v∈V、 w ∈ V w\in V w∈V且 < v , w > ∈ A <v,w>\in A <v,w>∈A,則稱頂點 v v v鄰接到頂點 w w w,頂點 w w w鄰接自頂點 v v v,並稱弧 < v , w > <v,w> <v,w>與頂點 v v v和頂點 w w w相關聯。
2.10 度、入度與出度
在無向圖中,頂點 v v v的度
( D e g r e e ) (Degree) (Degree)等於與該頂點相關聯的邊的數目,記為 T D ( v ) TD(v) TD(v)。
在有向圖中,頂點 v v v的度
等於該頂點的入度與出度之和,記為 T D ( v ) = I D ( v ) + O D ( v ) TD(v)=ID(v)+OD(v) TD(v)=ID(v)+OD(v),其中頂點 v v v的入度
( I n D e g r e e ) (InDegree) (InDegree)為以該頂點為弧頭的弧的數目,記為 I D ( v ) ID(v) ID(v),頂點 v v v的出度
( O u t D e g r e e ) (OutDegree) (OutDegree)為以該頂點為弧尾的弧的數目,記為 O D ( v ) OD(v) OD(v)。
2.11 路徑、簡單路徑與路徑長度
路徑
( P a t h ) (Path) (Path)是任意兩個有關聯的頂點之間的邊或弧,在圖 G = { V , { V R } } G=\{V,\{VR\}\} G={V,{VR}}中,頂點 v 1 v_1 v1到頂點 v n v_n vn的路徑是一個頂點序列 ( v 1 , v 2 , … , v i , v j , … , v n ) (v_1,v_2,\dots,v_i,v_j,\dots,v_n) (v1,v2,…,vi,vj,…,vn),對於上述序列中的任意相鄰的頂點 v i v_i vi和 v j v_j vj,若圖 G G G是無向圖,則有 ( v , w ) ∈ E (v,w)\in E (v,w)∈E,若圖 G G G是有向圖,則有 < v , w > ∈ A <v,w>\in A <v,w>∈A。
對於給定的一條路徑,若該路徑對應的序列中的頂點不重復,則稱為該路徑為簡單路徑
。
路徑上邊或弧的數目稱為路徑長度
。
2.12 回路與簡單回路
若某一路徑中的第一個頂點和最後一個頂點相同,則稱該路徑為回路
,也稱為環
( C y c l e ) (Cycle) (Cycle)。
在某一回路中,若除去第一個頂點和最後一個頂點外,其餘頂點均不重復,則稱為該回路為簡單回路
,也稱為簡單環
。
2.13 連通圖與連通分量
在無向圖中,若從頂點 v v v到頂點 w w w有路徑,則稱為 v v v到 w w w是連通的,若該圖中的任意兩個頂點間都是連通的,則稱該圖為連通圖
( C o n n e c t e d (Connected (Connected G r a p h ) Graph) Graph)。無向圖中的極大連通子圖稱為連通分量
( C o n n e c t e d (Connected (Connected C o m p o n e n t ) Component) Component)。這裡的極大就是盡可能地包含更多的頂點。
2.14 強連通圖與強連通分量
在有向圖中,若從頂點 v v v到頂點 w w w有路徑,從頂點 w w w到頂點 v v v也有路徑,則稱為 v v v和 w w w是強連通的,若該圖中的任意兩個頂點間都是強連通的,則稱該圖為強連通圖
。有向圖中的極大連通子圖稱為強連通分量
。
2.15 生成樹、最小生成樹與生成森林
具有 n n n個頂點的連通圖的極小連通子圖稱為生成樹
,生成樹包含這一連通圖的 n n n個頂點和 n − 1 n-1 n−1條邊。這裡的極小是盡可能少地包含邊。
通常把各邊帶權的連通圖稱為連通網,在連通網的所有生成樹中,對每一棵生成樹的各邊權值求和,其中權值最小的生成樹稱為該連通網的最小生成樹
。
非連通圖的各連通分量的生成樹組成的森林稱為生成森林
。
3. 圖的性質
3.1 性質1
若圖中有 n n n個頂點 v 1 , v 2 , … , v n v_1,v_2,\dots,v_n v1,v2,…,vn, e e e條邊或弧,其中頂點的度分別為 T D ( v 1 ) , T D ( v 2 ) , … , T D ( v n ) TD(v_1),TD(v_2),\dots,TD(v_n) TD(v1),TD(v2),…,TD(vn),則有
e = 1 2 ∑ i = 1 n T D ( v i ) e=\frac {1} {2} \sum_{i=1} ^ {n} TD(v_i) e=21i=1∑nTD(vi)
3.2 性質2
一棵有 n n n個頂點的生成樹有且僅有 n − 1 n-1 n−1條邊。
4. 圖的存儲結構
4.1 鄰接矩陣
用於無向圖、有向圖
在存儲含有 n n n個結點的圖 G = { V , { V R } } G=\{V,\{VR\}\} G={V,{VR}}時,將圖中的所有頂點存儲在長度為 n n n的一維數組中,將圖中邊或弧的信息存儲在 n × n n\times n n×n的二維數組中,我們稱這個二維的數組為鄰接矩陣。假設圖 G G G中頂點 v v v和頂點 w w w在一維數組中的下標分別為 i i i、 j j j,則該圖對應各鄰接矩陣定義如下:
若該圖為無向圖或有向圖,則
A r c s [ j ] [ j ] = { 1 , ( v , w ) ∈ E 或 < v , w > ∈ A 0 , 其 他 Arcs[j][j]=\begin{cases} 1, & (v,w)\in E或<v,w>\in A\\ \\ 0, & 其他 \end{cases} Arcs[j][j]=⎩⎪⎨⎪⎧1,0,(v,w)∈E或<v,w>∈A其他 若該圖為無向網或有向網,則
A r c s [ j ] [ j ] = { w i j , ( v , w ) ∈ E 或 < v , w > ∈ A ∞ , 其 他 Arcs[j][j]=\begin{cases} w_{ij}, & (v,w)\in E或<v,w>\in A\\ \\ \infty, & 其他 \end{cases} Arcs[j][j]=⎩⎪⎨⎪⎧wij,∞,(v,w)∈E或<v,w>∈A其他 其中, w i j w_{ij} wij為邊或弧對應的權值。
定義圖中的頂點:
class VertexMatrix(object): """ 圖的一個頂點 """ def __init__(self, data): self.data = data self.info = None
定義圖:
class GraphMatrix(object): """ 圖的鄰接矩陣 """ def __init__(self, kind): # 圖的類型: 無向圖, 有向圖, 無向網, 有向網 # kind: Undigraph, Digraph, Undinetwork, Dinetwork, self.kind = kind # 頂點表 self.vertexs = [] # 邊表, 即鄰接矩陣, 是個二維的 self.arcs = [] # 當前頂點數 self.vexnum = 0 # 當前邊(弧)數 self.arcnum = 0
無向圖及其鄰接矩陣、有向網及其鄰接矩陣如下:
A r c s = [ 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 ] A r c s = [ ∞ 1 2 ∞ ∞ ∞ 3 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ ∞ ] Arcs=\begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix} Arcs=\begin{bmatrix} \infty & 1 & 2 & \infty \\ \infty & \infty & 3 & \infty \\ \infty & \infty & \infty & 4 \\ \infty & \infty & \infty & \infty \end{bmatrix} Arcs=⎣⎢⎢⎡0101100100011110⎦⎥⎥⎤Arcs=⎣⎢⎢⎡∞∞∞∞1∞∞∞23∞∞∞∞4∞⎦⎥⎥⎤
鄰接矩陣的特點如下:
(1) 由於在創建鄰接矩陣時,輸入頂點的順序不同,其相應的鄰接矩陣也是不同的;
(2) 對於含有 n n n個頂點的圖,其鄰接矩陣一定是 n × n n\times n n×n的二維數組;
(3) 無向圖的鄰接矩陣具有對稱性,可采用壓縮存儲的方式存儲;
(4) 對於無向圖,若某一頂點 v v v在一維數組中的下標為 i i i,則該頂點的度為鄰接矩陣的第 i + 1 i+1 i+1行中值為1的元素的總數目;
(5) 對於有向圖,若某一頂點 v v v在一維數組中的下標為 i i i,則該頂點的出度為鄰接矩陣的第 i + 1 i+1 i+1行中值為1的元素的總數目,入度為鄰接矩陣的第 i + 1 i+1 i+1列中值為1的元素的總數目。
構造一個具有 n n n個頂點 e e e條邊的無向網的時間復雜度為 O ( n 2 + n e ) O(n^2+ne) O(n2+ne),其中對鄰接矩陣的初始化使用瞭 O ( n 2 ) O(n^2) O(n2)的時間。
4.2 鄰接表
用於無向圖、有向圖
使用鄰接表存儲圖時,將圖分為兩個部分:
第一部分為圖中每一個頂點及與該頂點相關聯的第一條邊或弧,可以這樣定義:
class VertexAdjacencyList(object): """ 圖的一個頂點 """ def __init__(self, data): self.data = data # 與該頂點相連的第一條邊FirstArc self.FirstArc = None
使用data
域來存儲圖中的每一個頂點,FirstArc
域來存儲與該頂點相關聯的第一條弧或邊,通常情況下指向第二部分單鏈表的第一個結點。
第二部分為用一個結點來存儲圖中的每一條邊或弧,該結點由adjacent
域、info
域和NextArc
域組成,這些結點形成瞭單鏈表。這部分結點可以這樣定義:
class ArcAdjacencyList(object): """ 圖的一個邊(弧) """ def __init__(self, adjacent): # 鄰接點或弧頭, 與該頂點相連的另一頂點的index self.adjacent = adjacent self.info = None # 與該邊(弧)依附於相同頂點的下一條邊(弧)NextArc self.NextArc = None
根據上面圖的鄰接表可以這樣定義:
class GraphAdjacencyList(object): """ 圖的鄰接表 """ def __init__(self, kind): # 圖的類型: 無向圖, 有向圖, 無向網, 有向網 # kind: Undigraph, Digraph, Undinetwork, Dinetwork, self.kind = kind # 鄰接表 self.vertices = [] # 當前頂點數 self.vexnum = 0 # 當前邊(弧)數 self.arcnum = 0
無向圖及其鄰接表:
有向網及其鄰接表、逆鄰接表:
鄰接表的特點如下:
(1) 由於存儲邊或弧通過不同的連接順序會形成不同的單鏈表,所以圖的鄰接表不是唯一的;
(2) 對於具有 e e e條邊的無向圖,使用鄰接表存儲時需要 2 e 2e 2e個結點來存儲圖的邊,而對於具有 e e e條弧的有向圖,使用鄰接表存儲時需要 e e e個結點來存儲圖的弧;
(3) 對於具有 n n n個頂點 e e e條邊或弧的稀疏圖而言,若采用鄰接矩陣存儲,則需要 n 2 n^2 n2個存儲空間來存儲圖的邊或弧,而采用鄰接表存儲時,則至多需要 2 e 2e 2e個結點存儲圖的邊或弧,所以稀疏圖的存儲使用鄰接表會更節省空間;
(4) 對於無向圖,頂點的度等於該頂點對應的單鏈表中結點的總數目;
(5) 對於有向圖,若某一頂點在數組中的下標為 i i i,則該頂點的出度為該頂點對應的單鏈表中結點的總數目,入度為鄰接表中adjacent
域內值為 i i i的結點的總數目。
在使用鄰接表存儲圖時,計算圖中的某一頂點的出度很容易,但是在計算其入度時,最壞的情況需要遍歷整個鄰接表。因此,有時為瞭方便計算頂點的入度,可以為該圖建立一個逆鄰接表。
在建立鄰接表或逆鄰接表時,如輸入的頂點信息為頂點的編號,則建立鄰接表或逆鄰接表的時間復雜度為 O ( n + e ) O(n+e) O(n+e),否則,需要通過查找才能確定頂點在圖中的位置,對應的時間復雜度為 O ( n e ) O(ne) O(ne)。
4.3 十字鏈表
用於有向圖
十字鏈表通常用於有向圖,可以將它看成鄰接表和逆鄰接表的結合。同樣分為兩個部分,即頂點結點部分和弧部分,通常將頂結點存儲在數組中,弧結點存儲在單鏈表中。
頂點結點包含data
域、FirstIn
域和FirstOut
域,其中data
域存儲頂點的值,FirstIn
域指向以當前頂點為弧頭的第
一條弧和FirstOut
域指向以當前頂點為弧尾的第一條弧。
弧結點包含TailVertex
域、HeadVertex
域、HeadLink
域、TailLink
域和info
域,其中TailVertex
域存儲當前弧的弧尾在數組中的下標,HeadVertex
域存儲當前弧的弧頭在數組中的下標,HeadLink
域指向與當前弧有相同弧頭的下一條弧,TailLink
域指向與當前弧有相同弧尾的下一條弧,info
域存儲當前弧的其他信息。
頂點結點定義如下:
class VertexOrthogonalList(object): """ 有向圖的一個頂點 """ def __init__(self, data): self.data = data # 以該頂點為弧頭的第一條弧FirstIn self.FirstIn= None # 以該頂點為弧尾的第一條弧FirstOut self.FirstOut= None
弧結點定義如下:
class ArcOrthogonalList(object): """ 有向圖的一條弧 """ def __init__(self): # 當前弧中弧頭在數組中的下標HeadVertex self.HeadVertex = None # 當前弧中弧尾在數組中的下標TailVertex self.TailVertex = None # 與當前弧有相同弧頭的下一條弧HeadLink self.HeadLink = None # 與當前弧有相同弧尾的下一條弧TailLink self.TailLink = None self.info = None
十字鏈表表示的有向圖定義如下:
class GraphOrthogonalList(object): """ 有向圖的十字鏈表 """ def __init__(self): # 十字鏈表 self.vertices = [] # 當前頂點數 self.vexnum = 0 # 當前邊(弧)數 self.arcnum = 0
有向圖及其十字鏈表:
4.4 鄰接多重表
用於無向圖
在使用鄰接表存儲無向圖時,圖的每一條邊都對應兩個結點,由於這兩個結點屬於兩個不同的鄰接表,所以在進行刪除操作時需要對鄰接表的兩條單鏈表進行操作,比較麻煩,所有引出瞭鄰接多重表。鄰接多重表同樣分為兩個部分,即頂點結點和邊結點,通常將頂點結點存儲在數組中,邊結點存儲在單鏈表中。
頂點結點包含data
域和FirstEdge
域,其中data
域存儲頂點的值,FirstEdge
域指向與當前頂點相關聯的第一條邊。
邊結點包含mark
域、VertexOne
域、NextEdgeOne
域、VertexTwo
域、NextEdgeTwo
域和info
域,其中mark
域用於標記當前是否被訪問,VertexOne
域和VertexTwo
域分別存儲當前邊的兩個頂點在數組中的下標,NextEdgeOne
域指向與VertexOne
域對應的頂點相關聯的下一條邊,NextEdgeTwo
域指向與VertexTwo
域對應的頂點相關聯的下一條邊,info
域存儲當前邊的其他信息。
頂點結點定義如下:
class VertexAdjacencyMultitable(object): """ 無向圖的一個頂點 """ def __init__(self, data): self.data = data # 與該頂點相連的第一條邊FirstEdge self.FirstEdge = None
邊結點定義如下:
class Edge(object): """ 無向圖的鄰接多重表 """ def __init__(self): # 用來標記當前邊是否已被訪問過 self.mark = None # 該邊的兩個頂點在數組中的下標 self.VertexOne = None self.VertexTwo = None # 與VertexOne對應的頂點相連的下一條邊NextEdgeOne self.NextEdgeOne = None # 與VertexTwo對應的頂點相連的下一條邊NextEdgeTwo self.NextEdgeTwo = None self.info = None
多重鄰接表表示的圖定義如下:
class GraphAdjacencyMultitable(object): """ 無向圖的鄰接多重表 """ def __init__(self): self.vertices = [] self.vertexnum = 0 self.edgenum = 0
無向圖及其鄰接多重鏈表:
到此這篇關於P-ython數據結構之圖的存儲結構詳解的文章就介紹到這瞭,更多相關P-ython圖的存儲結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Python實現最短路徑問題的方法
- Java數據結構之圖的領接矩陣詳解
- 利用Python將社交網絡進行可視化
- C++實現LeetCode(312.打氣球遊戲)
- python 基於DDT實現數據驅動測試