一钓猬、圖的初識(shí)
在一個(gè)社交網(wǎng)絡(luò)中普舆，每個(gè)帳號(hào)和他們之間的關(guān)系構(gòu)成了一張巨大的網(wǎng)絡(luò)，就像下面這張圖：
那么在電腦中表悬，我們要用什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)保存這個(gè)網(wǎng)絡(luò)呢弥锄？這個(gè)網(wǎng)絡(luò)需要用一個(gè)之前課程里未提到過(guò)的數(shù)據(jù)結(jié)構(gòu)，也就是接下來(lái)要講解的 圖 結(jié)構(gòu)來(lái)保存蟆沫。
到底什么是圖籽暇？圖是由一系列頂點(diǎn)和若干連結(jié)頂點(diǎn)集合內(nèi)兩個(gè)頂點(diǎn)的邊組成的數(shù)據(jù)結(jié)構(gòu)。數(shù)學(xué)意義上的圖饥追，指的是由一系列點(diǎn)與邊構(gòu)成的集合图仓，這里我們只考慮有限集。通常我們用 表示一個(gè)圖結(jié)構(gòu)但绕，其中
表示點(diǎn)集救崔，
表示邊集。
在頂點(diǎn)集合所包含的若干個(gè)頂點(diǎn)之間捏顺，可能存在著某種兩兩關(guān)系——如果某兩個(gè)點(diǎn)之間的確存在這樣的關(guān)系的話(huà)六孵，我們就在這兩個(gè)點(diǎn)之間連邊，這樣就得到了邊集的一個(gè)成員幅骄，也就是一條邊劫窒。對(duì)應(yīng)到社交網(wǎng)絡(luò)中，頂點(diǎn)就是網(wǎng)絡(luò)中的用戶(hù)拆座，邊就是用戶(hù)之間的好友關(guān)系主巍。
如果用邊來(lái)表示好友關(guān)系的話(huà)，對(duì)于微信這種雙向關(guān)注的社交網(wǎng)絡(luò)沒(méi)有問(wèn)題挪凑，但是對(duì)于微博這種單向關(guān)注的要如何表示呢孕索？
于是引出了兩個(gè)新的概念：有向邊 和 無(wú)向邊。
1.1 有向邊 與 無(wú)向邊躏碳。
簡(jiǎn)而言之搞旭，一條有向邊必然是從一個(gè)點(diǎn)指向另一個(gè)點(diǎn)，而相反方向的邊在有向圖中則不一定存在菇绵；而有的時(shí)候我們并不在意構(gòu)成一條邊的兩個(gè)頂點(diǎn)具體誰(shuí)先誰(shuí)后肄渗，這樣得到的一條邊就是無(wú)向邊。就像在微信中咬最， 是
的好友翎嫡，那
也一定是
的好友，而在微博中永乌，
關(guān)注
并不意味著
也一定關(guān)注
钝的。
對(duì)于圖而言翁垂，如果圖中所有邊都是無(wú)向邊，則稱(chēng)為無(wú)向圖硝桩，反之稱(chēng)為有向圖。
簡(jiǎn)而言之枚荣，無(wú)向圖中的邊是“好友”碗脊，而有向圖中的邊是“關(guān)注”。一般而言橄妆，我們?cè)跀?shù)據(jù)結(jié)構(gòu)中所討論的圖都是有向圖衙伶，因?yàn)橛邢驁D相比無(wú)向圖更具有代表性。實(shí)際上害碾，無(wú)向圖可以由有向圖來(lái)表示矢劲。如果 兩個(gè)點(diǎn)之間存在無(wú)向邊的話(huà)，那用有向圖也可以表示為
兩點(diǎn)之間同時(shí)存在
到
與
到
兩條有向邊慌随。仍然以社交網(wǎng)絡(luò)舉例：雖然微博中并不存在明確定義的好友關(guān)系芬沉，但是一般情況下，如果你和另一個(gè) ID 互相關(guān)注的話(huà)阁猜，那么我們也可以近似認(rèn)為丸逸，你和 TA 是好友。
1.2 圖的準(zhǔn)確定義
我們來(lái)形式化地定義一下圖：圖是由頂點(diǎn)集合（簡(jiǎn)稱(chēng) 點(diǎn)集）和頂點(diǎn)間的邊（簡(jiǎn)稱(chēng) 邊集）組成的數(shù)據(jù)結(jié)構(gòu)剃袍，通常用 來(lái)表示黄刚。其中點(diǎn)集用
來(lái)表示，邊集用
來(lái)表示民效。在 無(wú)向圖 中憔维，邊連接的兩個(gè)頂點(diǎn)是無(wú)序的，這些邊被稱(chēng)為 無(wú)向邊畏邢。例如下面這個(gè)無(wú)向圖
业扒，其點(diǎn)集
，邊集為
棵红。
而在有向圖中凶赁，邊連接的兩個(gè)頂點(diǎn)之間是有序的。箭頭的方向就表示有向邊的方向逆甜。例如下面這張有向圖 ：
其點(diǎn)集 虱肄，邊集為
。對(duì)于每條邊
交煞，我們稱(chēng)其為從
到
的一條有向邊咏窿，
是這條有向邊的 起點(diǎn)，
是這條有向邊的 終點(diǎn)素征。注意在有向圖中集嵌，
和
是不同的兩條有向邊萝挤。
二、圖的特征
2.1 圖的分類(lèi)
有很少邊或桓贰（如 怜珍，
指邊數(shù)，
指頂點(diǎn)數(shù)）的圖稱(chēng)為 稀疏圖凤粗，反之稱(chēng)為 稠密圖酥泛。對(duì)應(yīng)到微博里，如果在一個(gè)圈內(nèi)嫌拣，同學(xué)們都互相關(guān)注柔袁，則我們可以認(rèn)為該關(guān)系圖是一個(gè)稠密圖，如果只有幾個(gè)人關(guān)注了別人异逐，則我們可以認(rèn)為這是一個(gè)稀疏圖捶索。如果圖中邊集為空，則稱(chēng)該圖為 零圖灰瞻。
如果無(wú)向圖中任何一對(duì)頂點(diǎn)之間都有一條邊相連腥例，也就是有 條不重復(fù)的邊，則這個(gè)無(wú)向圖被稱(chēng)為 完全圖箩祥。類(lèi)似地院崇，如果有向圖中任何一對(duì)頂點(diǎn)
之間都有兩條有向邊
相連，則稱(chēng)這個(gè)有向圖為 有向完全圖袍祖。下圖就是由
個(gè)頂點(diǎn)組成的無(wú)向完全圖底瓣。
對(duì)于一個(gè)圖，如果以任意一個(gè)點(diǎn)為起點(diǎn)蕉陋，在圖上沿著邊走都可以到達(dá)其他所有點(diǎn)（有向圖必須沿有向邊的方向）捐凭，那么這個(gè)圖就是連通圖。顯然完全圖一定是連通圖凳鬓。
2.2 度的概念
在無(wú)向圖中茁肠，頂點(diǎn)的 度 是指某個(gè)頂點(diǎn)連出的邊數(shù)。例如在下圖中缩举，頂點(diǎn) 的度數(shù)為
垦梆，頂點(diǎn)
的度數(shù)為
。
在有向圖中仅孩，和度對(duì)應(yīng)的是 入度 和 出度 這兩個(gè)概念托猩。頂點(diǎn)的入度是指以該頂點(diǎn)為終點(diǎn)的有向邊數(shù)量；頂點(diǎn)的出度是指以頂點(diǎn)為起點(diǎn)的有向邊數(shù)量辽慕。需要注意的是京腥，在有向圖里，頂點(diǎn)是沒(méi)有 度 的概念的溅蛉。例如在下圖中公浪，頂點(diǎn) 的入度為
他宛，出度為
；頂點(diǎn)
的入度為
欠气，出度為
厅各。
2.3 度的性質(zhì)
在無(wú)向圖或有向圖中，頂點(diǎn)的度數(shù)總和為邊數(shù)的兩倍晃琳，即：
而在有向圖中讯检，有一個(gè)很明顯的性質(zhì)就是，所有頂點(diǎn)的入度和等于出度和卫旱。
三、鄰接矩陣
這一節(jié)我們來(lái)學(xué)習(xí)的圖的一種儲(chǔ)存方式——鄰接矩陣围段。
3.1 鄰接矩陣與圖
什么是鄰接矩陣呢顾翼？所謂鄰接矩陣存儲(chǔ)結(jié)構(gòu)就每個(gè)頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ)邊的信息，這樣所有點(diǎn)合起來(lái)就是用矩陣表示圖中各頂點(diǎn)之間的鄰接關(guān)系奈泪。所謂矩陣其實(shí)就是二維數(shù)組适贸。
對(duì)于有 個(gè)頂點(diǎn)的圖
來(lái)說(shuō)，我們可以用一個(gè)
的矩陣
來(lái)表示
中各頂點(diǎn)的相鄰關(guān)系涝桅，如果
和
之間存在邊（或话葑恕），則
冯遂，否則
蕊肥。下圖為有向圖
和無(wú)向圖
對(duì)應(yīng)的鄰接矩陣：
一個(gè)圖的鄰接矩陣是唯一的，矩陣的大小只與頂點(diǎn)個(gè)數(shù) 有關(guān)蛤肌，是一個(gè)
的矩陣壁却。前面我們已經(jīng)介紹過(guò)，在無(wú)向圖里裸准，如果頂點(diǎn)
和
之間有邊展东，則可認(rèn)為頂點(diǎn)
到
有邊，頂點(diǎn)
到
也有邊炒俱。對(duì)應(yīng)到鄰接矩陣?yán)镅嗡啵瑒t有
。因此我們可以發(fā)現(xiàn)权悟，無(wú)向圖的鄰接矩陣是一個(gè)對(duì)稱(chēng)矩陣砸王。
在鄰接矩陣上，我們可以直觀(guān)地看出兩個(gè)頂點(diǎn)之間是否有邊（或唤┣邸）处硬，并且很容易求出每個(gè)頂點(diǎn)的度，入度和出度拇派。
這里我們以 為例荷辕，演示下如何利用鄰接矩陣計(jì)算頂點(diǎn)的入度和出度凿跳。頂點(diǎn)的出度，即為鄰接矩陣上點(diǎn)對(duì)應(yīng)行上所有值的總和疮方，比如頂點(diǎn)
出度即為
控嗜；而每個(gè)點(diǎn)的入度即為點(diǎn)對(duì)應(yīng)列上所有值的總和，比如頂點(diǎn)
對(duì)應(yīng)的入度即為
骡显。
接下來(lái)我們就先一起學(xué)習(xí)構(gòu)造和使用鄰接矩陣的方法疆栏。鄰接矩陣是一個(gè)由 和
構(gòu)成的矩陣。處于第
行惫谤、第
列上的元素
和
分別代表頂點(diǎn)
到
之間存在或不存在一條有向邊壁顶。
顯然在構(gòu)造鄰接矩陣的時(shí)候，我們需要實(shí)現(xiàn)一個(gè)整型的二維數(shù)組溜歪。由于當(dāng)前的圖還是空的若专，因此我們還要把這個(gè)二維數(shù)組中的每個(gè)元素都初始化為 。
在構(gòu)造好了一個(gè)圖的結(jié)構(gòu)后蝴猪，我們需要把圖中各邊的情況對(duì)應(yīng)在鄰接矩陣上调衰。實(shí)際上，這一步的實(shí)現(xiàn)非常簡(jiǎn)單自阱，當(dāng)從頂點(diǎn) 到
上存在邊時(shí)嚎莉，我們只要把二維數(shù)組對(duì)應(yīng)的位置置為
就好了。
用鄰接矩陣來(lái)構(gòu)建圖需要如下幾步沛豌，我們可以用二維數(shù)組G來(lái)表示一個(gè)圖趋箩。
3.2 初始化
初始化的過(guò)程很簡(jiǎn)單，只需要把數(shù)組初始化為 即可琼懊「篝ぃ可以借助
memset來(lái)快速地將一個(gè)數(shù)組中的所有元素都初始化為 。
memset(G, 0, sizeof(G));
注意哼丈，memset只能用來(lái)初始化 和
启妹，并且需要加上頭文件
cstring。
上面的代碼等價(jià)于：
for (int i = 0; i < N1; i++) { // N1 為數(shù)組第一維大小
for (int j = 0; j < N2; j++) { // N2 為數(shù)組第二維大小
G[i][j] = 0;
}
}
當(dāng)然我們平常使用鄰接矩陣的時(shí)候下標(biāo)只用 到
或者
到
（這個(gè)看題目中點(diǎn)的編號(hào)）醉旦。
3.3 鄰接矩陣元素的修改
插入邊
如果插入一條無(wú)向邊 饶米，只需要
G[u][v] = 1;
G[v][u] = 1;
也可以寫(xiě)成G[u][v] = G[v][u] = 1;。
如果插入一條有向邊 车胡，只需要
G[u][v] = 1;檬输。
訪(fǎng)問(wèn)邊
如果G[u][v] = 1，說(shuō)明有一條從 到
的邊匈棘，否則沒(méi)有從
到
的邊丧慈。
3.4 帶權(quán)值的圖
在前面的課程中，圖中的邊都只是用來(lái)表示兩個(gè)點(diǎn)之間是否存在關(guān)系，而沒(méi)有體現(xiàn)出兩個(gè)點(diǎn)之間關(guān)系的強(qiáng)弱逃默。比如在社交網(wǎng)絡(luò)中鹃愤，不能單純地用 茎辐、
來(lái)表示兩個(gè)人否為朋友浅缸。當(dāng)兩個(gè)人是朋友時(shí)，有可能是很好的朋友怔接，也有可能是一般的朋友吟税，還有可能是不熟悉的朋友凹耙。
我們用一個(gè)數(shù)值來(lái)表示兩個(gè)人之間的朋友關(guān)系強(qiáng)弱，兩個(gè)人的朋友關(guān)系越強(qiáng)肠仪，對(duì)應(yīng)的值就越大肖抱。而這個(gè)值就是兩個(gè)人在圖中對(duì)應(yīng)的邊的權(quán)值，簡(jiǎn)稱(chēng) 邊權(quán)异旧。對(duì)應(yīng)的圖我們稱(chēng)之為 帶權(quán)圖虐沥。
如下就是一個(gè)帶權(quán)圖，我們把每條邊對(duì)應(yīng)的邊權(quán)標(biāo)記在邊上：
帶權(quán)圖也分成帶權(quán)有向圖和帶權(quán)無(wú)向圖泽艘。前面學(xué)到的關(guān)于圖的性質(zhì)在帶權(quán)圖上同樣成立。實(shí)際上镐依，我們前面學(xué)習(xí)的圖是一種特殊帶權(quán)圖匹涮，只不過(guò)圖中所有邊的權(quán)值只有 一種；而在帶權(quán)圖中槐壳，邊的權(quán)值可以是任意的然低。
用鄰接矩陣存儲(chǔ)帶權(quán)圖和之前的方法一樣，用G[a][b]來(lái)表示 和
之間的邊權(quán)（我們需要用一個(gè)數(shù)值來(lái)表示邊不存在务唐，如
0）雳攘。同樣，對(duì)于無(wú)向圖枫笛，這個(gè)矩陣依然是對(duì)稱(chēng)的吨灭。
如上所示，左邊的圖對(duì)應(yīng)的右邊的鄰接矩陣刑巧。
