問(wèn)題8 連通

?圖在數(shù)學(xué)上的表示

相鄰、鄰居、度數(shù)

道（walk）、徑（trail）、路（path）

?

連通問(wèn)題：一個(gè)圖是連通的，當(dāng)且僅當(dāng)其任意兩個(gè)節(jié)點(diǎn)之間都存在一條路。

?

這個(gè)問(wèn)題，還可以推論兩個(gè)問(wèn)題

1：一個(gè)圖是連通的，當(dāng)且僅當(dāng)其任一個(gè)節(jié)點(diǎn)與其他所有節(jié)點(diǎn)之間都存在路。（這也是判斷圖是否連通的算法中，常用的認(rèn)識(shí)）

2：一個(gè)不連通的圖，包含多個(gè)連通分量，每個(gè)連通分量即其中盡可能打的連通子圖。

?

那從計(jì)算機(jī)處理圖的角度的最大特點(diǎn)是什么呢？就是要知道，圖在計(jì)算機(jī)（程序）內(nèi)部是如何表示的。因?yàn)槟壳坝?jì)算機(jī)存儲(chǔ)的特點(diǎn)，所以計(jì)算機(jī)當(dāng)前能夠存儲(chǔ)的圖（數(shù)據(jù)）和人腦、數(shù)學(xué)中圖是不一樣的。那么要學(xué)習(xí)計(jì)算機(jī)的圖算法，首先要學(xué)習(xí)圖在計(jì)算機(jī)中的表示和存儲(chǔ)。要認(rèn)識(shí)到，所有計(jì)算機(jī)的圖算法（程序）都是基于某種圖的計(jì)算機(jī)表示的。

?

本章介紹了計(jì)算機(jī)表示圖的最常見(jiàn)的兩種表示形式：“鄰接矩陣”和“鄰接表”。

?

然后介紹了基于鄰接矩陣判斷一個(gè)圖是否連通兩個(gè)算法：矩陣乘冪法和行列合并法，這個(gè)需要一些數(shù)學(xué)知識(shí)。如果有這方面的數(shù)學(xué)基礎(chǔ)，實(shí)現(xiàn)這兩個(gè)算法的程序設(shè)計(jì)技巧要求并不高（程序就是實(shí)現(xiàn)數(shù)學(xué)方法而已，知道數(shù)學(xué)方法就能設(shè)計(jì)出算法）。

?

最后介紹了一個(gè)基于鄰接表求解圖是否連通的一個(gè)算法：這個(gè)算法是基于圖遍歷算法的思路來(lái)實(shí)現(xiàn)的，不僅需要圖的數(shù)學(xué)知識(shí)，還需要掌握?qǐng)D遍歷算法，這需要算法設(shè)計(jì)基礎(chǔ)，學(xué)習(xí)和實(shí)現(xiàn)起來(lái)難度更高一些。

?

?

【作者感受】

本書(shū)有多個(gè)問(wèn)題，都和 圖有關(guān)

這一章介紹的 連通，也是圖論中的一個(gè)重要性質(zhì)和研究對(duì)象。

圖（注意，圖不是圖像哈）從某種角度來(lái)說(shuō)是可見(jiàn)的，可以從形象思維的角度理解，但是更多的時(shí)候，圖數(shù)據(jù)是看不見(jiàn)的（注意，讓圖數(shù)據(jù)可視化是圖的一個(gè)重要研究方法），所以圖的學(xué)習(xí)需要抽象思維，這也是圖很難學(xué)的原因吧。

?

圖論是數(shù)學(xué)中的一個(gè)重要分支，圖算法是計(jì)算機(jī)算法領(lǐng)域中的一個(gè)重要組成部分，兩者有關(guān)聯(lián)，但是也不完全一致。這一點(diǎn)，也要有認(rèn)識(shí)。