1、前言由于后續(xù)更新「面試專場」的好幾篇文章都涉及到 圖 這種數(shù)據(jù)結(jié)構(gòu)，因此打算先普及一下 圖 的相關(guān)理論支持，如果后面的相關(guān)內(nèi)容有些點不太容易理解，可以查閱此篇文章。本文不建議一口氣閱讀完畢，可以先瀏覽一遍，在后續(xù)有需要的時候進行查閱即可。 2、圖圖是數(shù)據(jù)結(jié)構(gòu)中重要內(nèi)容。相比于線性表與樹，圖的結(jié)構(gòu)更為復(fù)雜。在線性表的存儲結(jié)構(gòu)中，數(shù)據(jù)直接按照前驅(qū)后繼的線性組織形式排列。在樹的結(jié)構(gòu)中，數(shù)據(jù)節(jié)點以層的方式排列，節(jié)點與節(jié)點之間是一種層次關(guān)系。但是，在圖的結(jié)構(gòu)中數(shù)據(jù)之間可以有任意關(guān)系，這就使得圖的數(shù)據(jù)結(jié)構(gòu)相對復(fù)雜。 2.1 定義定義：圖（Graph）是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V，E），其中，G表示一個圖，V 是圖 G 中頂點的集合，E 是圖 G 中邊的集合。 例如：圖 2.1 所示圖  在圖 2.1 中，共有 V0，V1，V2，V3 這 4 個頂點，4 個頂點之間共有 5 條邊。 注：
2.2 無向邊無向邊：若頂點 x 和 y 之間的邊沒有方向，則稱該邊為無向邊(x,y)，(x,y) 與 (y,x) 意義相同，表示 x 和 y 之間有連接。 圖 2.2 所示圖中的邊均為無向邊。  2.3 有向邊有向邊：若頂點 x 和 y 之間的邊有方向，則稱該邊為有向邊  2.4 無向圖無向圖：若圖中任意兩個頂點之間的邊均是無向邊，則稱該圖為無向圖。 2.5 有向圖有向圖：若圖中任意兩個頂點之間的邊均是有向邊，則稱該圖為有向圖。 2.6 頂點與頂點的度 頂點的度： 頂點 V 的度是和 V 相關(guān)聯(lián)的邊的數(shù)目，記為TD(V)。 圖 2.6 所示圖中，V0 頂點的度為 3 。 入度： 以頂點v為頭的邊的數(shù)目，記為ID(V)。 圖2.6所示圖中，V0的入度為1。 出度： 以頂點 v 為尾的邊的數(shù)目，記為 OD(V)。 圖2.6所示圖中，V0的出度為2。 頂點的度 = 入度 + 出度。 即 TD(V) = ID(V) + OD(V)。 2.7 鄰接鄰接是兩個頂點之間的一種關(guān)系。如果圖包含（u,v），則稱頂點 v 與頂點 u 鄰接。在無向圖中，這也暗示了頂點 u 也與頂點 v 鄰接。換句話說，在無向圖中鄰接關(guān)系是對稱的。 2.8 路徑路徑：在圖中，依次遍歷頂點序列之間的邊所形成的軌跡。 例如：在圖 2.8 中所示圖中依次訪問頂點 V0 、V3 和 V2 ，則構(gòu)成一條路徑。  3、完全圖完全圖：每個頂點都與其他頂點相鄰接的圖。 無向完全圖：在無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。（含有n個頂點的無向完全圖有(n×(n-1))/2條邊） 圖 3.1 所示的圖為無向完全圖。  有向完全圖：在有向圖中，如果任意兩個頂點之間都存在方向互為相反的兩條邊，則稱該圖為有向完全圖。（含有 n 個頂點的有向完全圖有 n×(n-1) 條邊） 圖3.2所示的圖為有向完全圖。  4、連通圖在無向圖 G 中，如果從頂點 v 到頂點 v' 有路徑，則稱 v 和 v' 是連通的。 如果對于圖中任意兩個頂點 vi 、vj ∈E， vi，和vj都是連通的，則稱 G 是連通圖，否則圖為非連通圖。 例如：圖4.1所示圖，圖中頂點A、B、C、D是連通的，但是其中任一頂點與頂點E或者頂點F之間沒有路徑，因此圖4.1中所示的圖為非連通圖。  若添加頂點B與頂點F之間的鄰接邊，則圖變?yōu)檫B通圖，如圖4.2所示：  5、數(shù)組存儲圖的數(shù)組存儲方式也稱為鄰接矩陣存儲。圖中的數(shù)據(jù)信息包括：頂點信息和描述頂點之間關(guān)系的邊的信息，將這兩種信息存儲在數(shù)組中即為圖的數(shù)組存儲。 首先，創(chuàng)建頂點數(shù)組，頂點數(shù)組中存儲的是圖的頂點信息，采用一維數(shù)組的方式即可存儲所有的頂點信息。存儲圖中邊的信息時，由于邊是描述頂點與頂點之間關(guān)系的信息，因此需要采用二維數(shù)組進行存儲。 定義：設(shè)圖 G 有 n 個頂點，則鄰接矩陣是一個n X n的方陣A，定義為：  |
|
|
來自： taotao_2016 > 《計算機》
