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