C++圖 小結(jié)

重點回顧?

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

Q & A

路徑的定義是頂點序列還是邊序列？

維基百科上不同語言版本的定義不一致：英文版是“路徑是一個邊序列”，而中文版是“路徑是一個頂點序列”。以下是英文版原文：In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. 在本文中，路徑被認為是一個邊序列，而不是一個頂點序列。這是因為兩個頂點之間可能存在多條邊連接，此時每條邊都對應一條路徑。

非連通圖中，是否會有無法遍歷到的點？

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

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

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