C++圖 小結(jié)

重點(diǎn)回顧?

• 圖由頂點(diǎn)和邊組成，可以被表示為一組頂點(diǎn)和一組邊構(gòu)成的集合。
• 相較于線性關(guān)系（鏈表）和分治關(guān)系（樹），網(wǎng)絡(luò)關(guān)系（圖）具有更高的自由度，因而更為復(fù)雜。
• 有向圖的邊具有方向性，連通圖中的任意頂點(diǎn)均可達(dá)，有權(quán)圖的每條邊都包含權(quán)重變量。
• 鄰接矩陣?yán)镁仃噥肀硎緢D，每一行（列）代表一個(gè)頂點(diǎn)，矩陣元素代表邊，用 1 或 0 表示兩個(gè)頂點(diǎn)之間有邊或無邊。鄰接矩陣在增刪查操作上效率很高，但空間占用較多。
• 鄰接表使用多個(gè)鏈表來表示圖，第 i 條鏈表對(duì)應(yīng)頂點(diǎn) i ，其中存儲(chǔ)了該頂點(diǎn)的所有鄰接頂點(diǎn)。鄰接表相對(duì)于鄰接矩陣更加節(jié)省空間，但由于需要遍歷鏈表來查找邊，時(shí)間效率較低。
• 當(dāng)鄰接表中的鏈表過長時(shí)，可以將其轉(zhuǎn)換為紅黑樹或哈希表，從而提升查詢效率。
• 從算法思想角度分析，鄰接矩陣體現(xiàn)“以空間換時(shí)間”，鄰接表體現(xiàn)“以時(shí)間換空間”。
• 圖可用于建模各類現(xiàn)實(shí)系統(tǒng)，如社交網(wǎng)絡(luò)、地鐵線路等。
• 樹是圖的一種特例，樹的遍歷也是圖的遍歷的一種特例。
• 圖的廣度優(yōu)先遍歷是一種由近及遠(yuǎn)、層層擴(kuò)張的搜索方式，通常借助隊(duì)列實(shí)現(xiàn)。
• 圖的深度優(yōu)先遍歷是一種優(yōu)先走到底、無路可走時(shí)再回溯的搜索方式，常基于遞歸來實(shí)現(xiàn)。

Q & A

路徑的定義是頂點(diǎn)序列還是邊序列？

維基百科上不同語言版本的定義不一致：英文版是“路徑是一個(gè)邊序列”，而中文版是“路徑是一個(gè)頂點(diǎn)序列”。以下是英文版原文：In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. 在本文中，路徑被認(rèn)為是一個(gè)邊序列，而不是一個(gè)頂點(diǎn)序列。這是因?yàn)閮蓚€(gè)頂點(diǎn)之間可能存在多條邊連接，此時(shí)每條邊都對(duì)應(yīng)一條路徑。

非連通圖中，是否會(huì)有無法遍歷到的點(diǎn)？

在非連通圖中，從某個(gè)頂點(diǎn)出發(fā)，至少有一個(gè)頂點(diǎn)無法到達(dá)。遍歷非連通圖需要設(shè)置多個(gè)起點(diǎn)，以遍歷到圖的所有連通分量。

在鄰接表中，“與該頂點(diǎn)相連的所有頂點(diǎn)”的頂點(diǎn)順序是否有要求？

可以是任意順序。但在實(shí)際應(yīng)用中，可能會(huì)需要按照指定規(guī)則來排序，比如按照頂點(diǎn)添加的次序、或者按照頂點(diǎn)值大小的順序等等，這樣可以有助于快速查找“帶有某種極值”的頂點(diǎn)。