1.1.1 圖的基本類型

1.有向圖和無向圖

如果圖中的邊存在方向性，則稱這樣的邊為有向邊eij=<vi，vj>，其中vi是這條有向邊的起點(diǎn)，vj是這條有向邊的終點(diǎn)，包含有向邊的圖稱為有向圖，如圖1-2所示。與有向圖相對應(yīng)的是無向圖，無向圖中的邊都是無向邊，我們可以認(rèn)為無向邊是對稱的，同時(shí)包含兩個(gè)方向：eij=<vi，vj>=<vj，vi>=eji。

2.非加權(quán)圖與加權(quán)圖

如果圖里的每條邊都有一個(gè)實(shí)數(shù)與之對應(yīng)，我們稱這樣的圖為加權(quán)圖，如圖1-3所示，該實(shí)數(shù)稱為對應(yīng)邊上的權(quán)重。在實(shí)際場景中，權(quán)重可以代表兩地之間的路程或運(yùn)輸成本。一般情況下，我們習(xí)慣把權(quán)重抽象成兩個(gè)頂點(diǎn)之間的連接強(qiáng)度。與之相反的是非加權(quán)圖，我們可以認(rèn)為非加權(quán)圖各邊上的權(quán)重是一樣的。

3.連通圖與非連通圖

如果圖中存在孤立的頂點(diǎn)，沒有任何邊與之相連，這樣的圖被稱為非連通圖，如圖1-4所示。相反，不存在孤立頂點(diǎn)的圖稱為連通圖。

4.二部圖

二部圖是一類特殊的圖。我們將G中的頂點(diǎn)集合V拆分成兩個(gè)子集A和B，如果對于圖中的任意一條邊eij均有vi∈A，vj∈B或者vi∈B，vj∈A，則稱圖G為二部圖，如圖1-5所示。二部圖是一種十分常見的圖數(shù)據(jù)對象，描述了兩類對象之間的交互關(guān)系，比如：用戶與商品、作者與論文。