圖－基本概念
- 圖：頂點(diǎn)＋線
- 無(wú)向邊 (A,B)
- 有向邊 <A,B>则拷，不能寫成<B,A>，A是弧尾，B是弧頭
- 簡(jiǎn)單圖：沒(méi)有到自身的邊餐抢，沒(méi)有重復(fù)的邊
- 無(wú)向完全圖：如果任意兩個(gè)頂點(diǎn)之間都存在邊
- 有向完全圖：如果任意兩個(gè)定點(diǎn)之間都存在方向互為相反的兩條弧
- 有很少條邊或弧的圖稱為稀疏圖美浦，反之為稠密圖
- 網(wǎng)：邊或弧上帶權(quán)重的圖
- 頂點(diǎn)的度：是與頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)量（無(wú)向圖）
- 樹的總邊數(shù)：所有頂點(diǎn)度之和的一半（無(wú)向圖）
- 無(wú)向圖分為出度和入度
- 無(wú)向圖的弧的總數(shù)：等于所有節(jié)點(diǎn)的出度之和／入度之和
- 路徑的長(zhǎng)度是路徑上的邊或弧的數(shù)目
- 回路／環(huán)：第一個(gè)頂點(diǎn)到最后一個(gè)頂點(diǎn)相同的路徑
- 簡(jiǎn)單路徑：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑
- 簡(jiǎn)單回路：除了第一個(gè)和最后一個(gè)頂點(diǎn)，其余頂點(diǎn)不重復(fù)的回路
- 聯(lián)通圖：如果對(duì)于圖中任意兩個(gè)頂點(diǎn)都是聯(lián)通的（無(wú)向圖）
- 聯(lián)通分量：無(wú)向圖中的極大連通子圖（無(wú)向圖）
- 要是子圖
- 子圖要是連通的
- 連通子圖含有極大頂點(diǎn)數(shù)
- 具有極大頂點(diǎn)數(shù)的連通子圖包含以負(fù)于這些頂點(diǎn)的所有邊
- 強(qiáng)聯(lián)通圖：任意兩個(gè)頂點(diǎn)之間都存在相反方向的兩條弧（有向圖）
- 強(qiáng)連通分量：極大聯(lián)通子圖（有向圖）
連通分量的疑惑
連通分量（無(wú)向圖的極大連通子圖）到底什么意思曹动？？
- 無(wú)向非連通圖饰恕，
相連的所有節(jié)點(diǎn)組成的子圖就是一個(gè)連通分量挠羔。E/F和A/B/C/D都不相連，所以它們獨(dú)自形成一個(gè)連通分量埋嵌。而A/B/C組成的子圖缺少了可連通的節(jié)點(diǎn)D破加，因此就不能稱之為極大連通子圖（連通分量） - 無(wú)向連通圖，它的極大連通子圖就是自身
圖的存儲(chǔ)結(jié)構(gòu)（內(nèi)存存儲(chǔ)結(jié)構(gòu)）
鄰接矩陣
鄰接表
圖的遍歷
深度優(yōu)先
- 類似于樹的先序遍歷
- 如同人站在迷宮里雹嗦，從一個(gè)頂點(diǎn)進(jìn)去范舀，每次選擇未訪問(wèn)的最右邊的頂點(diǎn)
- 紅色線框標(biāo)記部分；這是代碼的核心了罪，
循環(huán)＋遞歸實(shí)現(xiàn)了從每個(gè)節(jié)點(diǎn)深度進(jìn)入锭环，再遞歸回來(lái)，最終遍歷所有節(jié)點(diǎn) -
時(shí)間復(fù)雜度：O(
)
廣度優(yōu)先
- 類似于樹的層級(jí)遍歷
- 算法用到一個(gè)輔助隊(duì)列泊藕，來(lái)記錄需要訪問(wèn)的頂點(diǎn)順序
- 從第一個(gè)頂點(diǎn)開始辅辩，與他連接的所有頂點(diǎn)就是第二層，依此類推
代碼：
