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