五、圖
圖的概念
圖是一種較線性表和樹(shù)形結(jié)構(gòu)更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在線性表中每個(gè)數(shù)據(jù)元素只有一個(gè)（直接）前驅(qū)和后繼，即各數(shù)據(jù)元素之間僅有線性關(guān)系。在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間有明顯的層次關(guān)系，每一層中的數(shù)據(jù)元素只和上一層中的一個(gè)元素（即雙親結(jié)點(diǎn)）相關(guān)。而在圖中，任意兩個(gè)數(shù)據(jù)元素之間均有可能相關(guān)。
圖（graph）是圖型結(jié)構(gòu)的簡(jiǎn)稱。它是一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。圖在各個(gè)領(lǐng)域都有著廣泛的應(yīng)用。圖的二元組定義為:
G=（V，E）
其中，V是非空的頂點(diǎn)集合，即
V=｛v i |1≤i≤n，n≥1，v i ∈elemtype，n為頂點(diǎn)數(shù)｝
E是V上二元關(guān)系的集合，一般只討論僅含一個(gè)二元關(guān)系的情況，且直接用E表示這個(gè)關(guān)系。這樣，E就是V上頂點(diǎn)的序偶或無(wú)序?qū)Γ總€(gè)無(wú)序?qū)Γ▁，y）是兩個(gè)對(duì)稱序偶和的簡(jiǎn)寫(xiě)形式）的集合。對(duì)于V上的每個(gè)頂點(diǎn)，在E中都允許有任意多個(gè)前驅(qū)和任意多個(gè)后繼，即對(duì)每個(gè)頂點(diǎn)的前驅(qū)和后繼個(gè)數(shù)均不加限制。回顧一下線性表和樹(shù)的二元組定義，都是在其二元關(guān)系上規(guī)定了限制條件，線性表的限制條件是只允許每個(gè)結(jié)點(diǎn)有一個(gè)前驅(qū)和一個(gè)后繼，樹(shù)的限制條件是只允許每個(gè)結(jié)點(diǎn)有一個(gè)前驅(qū)。因此，圖比線性表和樹(shù)更具有廣泛性，它包含線性表和樹(shù)在內(nèi)，線性表和樹(shù)可以認(rèn)為是圖的簡(jiǎn)單情況。來(lái)源：www.examda.com
對(duì)于一個(gè)圖G，若E是序偶的集合，則每個(gè)序偶對(duì)應(yīng)圖形中的一條有向邊，若E是無(wú)序?qū)Φ募希瑒t每個(gè)無(wú)序?qū)?duì)應(yīng)圖形中的一條無(wú)向邊，所以可把E看作為邊的集合。這樣，圖的二元組定義可敘述為:圖的非空頂點(diǎn)集（vertexset）和邊集（edgeset）所組成。針對(duì)圖G，頂點(diǎn)集和邊集可分別記為V（G）和E（G）。邊集E（G）允許是空集，若是空集，圖G中的頂點(diǎn)均為孤立頂點(diǎn)。對(duì)于一個(gè)圖G，若邊集E（G）為有向邊的集合，則稱此圖為有向圖（digraph），若邊集E（G）為無(wú)向邊的集合，則稱此圖為無(wú)向圖（undigraph）。