第六章圖-創(chuàng)新互聯(lián)
免責(zé)聲明：
在塔什庫爾干塔吉克等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站制作、成都網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作定制制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),成都全網(wǎng)營銷,成都外貿(mào)網(wǎng)站建設(shè)公司,塔什庫爾干塔吉克網(wǎng)站建設(shè)費(fèi)用合理。
- 筆記來源：本系列所有筆記均整理自 B站·王道考研·數(shù)據(jù)結(jié)構(gòu) 視頻教程。
- 參考書籍：《2021年數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)指導(dǎo)》，王道論壇所著，電子工業(yè)出版社出版，ISBN ：9787121379819。
目錄
1 圖的概念圖G，由頂點(diǎn)集V和邊集E組成，記作G(V,E)
- 頂點(diǎn)集V 不能為空，一個(gè)圖至少得有一個(gè)頂點(diǎn)，圖不可以是空圖；圖中的頂點(diǎn)個(gè)數(shù)稱為圖的階。
- 邊集E可以為空
頂點(diǎn)就好比火車站，邊就好比火車站間的鐵路。
有向圖與無向圖
簡單圖與多重圖
圖的邏輯結(jié)構(gòu)應(yīng)用
頂點(diǎn)的度
頂點(diǎn)與釘釘之間的關(guān)系
連通圖與強(qiáng)連通圖
子圖
無向圖的連通分量
有向圖的強(qiáng)連通分量
連通圖的生成樹
邊的權(quán)值與帶權(quán)圖
完全圖
頂點(diǎn)為 n 的無向完全圖，邊數(shù)為 n * (n-1) / 2
頂點(diǎn)為 n 的有向完全圖，邊數(shù)為 n * (n-1)
樹與有向樹
領(lǐng)接矩陣：使用一個(gè)一維數(shù)組存儲(chǔ)頂點(diǎn)信息，使用一個(gè)二維數(shù)組存儲(chǔ)邊的信息（頂點(diǎn)間的鄰接關(guān)系），這個(gè)二維數(shù)組稱為鄰接矩陣。
#define MAX_V_NUM 100
typedef char V; // 頂點(diǎn)的數(shù)據(jù)類型
typedef int E; // 邊上權(quán)值的數(shù)據(jù)類型
// 鄰接矩陣結(jié)構(gòu)
struct MGraph{V vertex[MAX_V_NUM]; // 頂點(diǎn)
E edge[MAX_V_NUM][MAX_V_NUM]; // 鄰接矩陣，邊表
int v_num; // 圖的當(dāng)前定點(diǎn)數(shù)
int arc_num; // 圖的當(dāng)前邊數(shù)/弧數(shù)
};當(dāng)鄰接矩陣中的元素只表示對應(yīng)的邊是否存在時(shí)，可以將其定義為0表示邊不存在，1表示邊存在。
無向圖的鄰接矩陣是一個(gè)對稱矩陣，對于規(guī)模較大的對稱矩陣可以采用壓縮存儲(chǔ)。
頂點(diǎn)數(shù)為n的圖，鄰接矩陣表示法的空間復(fù)雜度為O(n^2)
2.2 鄰接表鄰接表：對每個(gè)頂點(diǎn)建立一個(gè)單鏈表，單鏈表中存儲(chǔ)依附于這個(gè)頂點(diǎn)的邊，結(jié)合順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。
#define MAX_V_NUM 100
typedef char V; // 頂點(diǎn)數(shù)據(jù)類型
// 邊表結(jié)點(diǎn)
struct ArcNode{int adjvex; // 這條弧所指向的頂點(diǎn)位置
ArcNode* next; // 指向下一條弧的指針
};
// 頂點(diǎn)表結(jié)點(diǎn)
struct VNode {V data; // 頂點(diǎn)信息
ArcNode* first; // 指向依附于該頂點(diǎn)的第一條弧的指針
};
// 鄰接表
typedef VNode AdjList[MAX_V_NUM] ;
struct ALGraph{AdjList vertices; // 鄰接表
int vexnum; // 頂點(diǎn)數(shù)
int arcnum; // 弧數(shù)
};
鄰接表中：
- 對于無向圖，所需的存儲(chǔ)空間為
|V| + 2*|E|,|V|為頂點(diǎn)數(shù)，|E|為邊數(shù)，因?yàn)橐粭l邊的信息會(huì)存儲(chǔ)兩次 - 對于有向圖，所需的存儲(chǔ)空間為
|V| + |E|,|V|為頂點(diǎn)數(shù)，|E|為邊數(shù) - 圖的鄰接表的表示方式并不唯一
圖的基本操作獨(dú)立于圖的存儲(chǔ)結(jié)構(gòu)，不同的存儲(chǔ)結(jié)構(gòu)，同一操作算法的不同實(shí)現(xiàn)會(huì)有不同的性能。下面針對鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)進(jìn)行分析：
判斷圖中是否存在邊(x,y)或者弧
求圖中與頂點(diǎn)x鄰接的邊
圖的遍歷是指，從圖的某一個(gè)頂點(diǎn)出發(fā)，按某種搜索方式，沿著圖中的邊對其他頂點(diǎn)訪問一次（僅僅訪問一次）。為避免同一頂點(diǎn)被訪問多次，在遍歷的過程中，需記下每個(gè)已經(jīng)訪問過的頂點(diǎn)，可以使用一個(gè)數(shù)組來存儲(chǔ)這些已經(jīng)訪問過的頂點(diǎn)。
圖的遍歷算法主要有兩種：廣度優(yōu)先和深度優(yōu)先。
4.1 廣度優(yōu)先遍歷 算法思想廣度優(yōu)先搜索（Breadth-First-Search，BFS）。類似于二叉樹的層序遍歷。
算法思想：找到與一個(gè)頂點(diǎn)相鄰的所有頂點(diǎn)，標(biāo)記哪些頂點(diǎn)被訪問過，借助一個(gè)輔助數(shù)組，為了實(shí)現(xiàn)逐層訪問，還需要借助一個(gè)輔助隊(duì)列，用來存儲(chǔ)正在訪問的頂點(diǎn)的下一層頂點(diǎn)。
算法實(shí)現(xiàn)
深度優(yōu)先（Depth-First-Search，DFS），類似于樹的先序遍歷。
基本思想：從一個(gè)頂點(diǎn)v1開始，訪問與其鄰接且未被訪問的任意頂點(diǎn)w1，再訪問與w1鄰接且未被訪問的任意頂點(diǎn)，重復(fù)直到不能繼續(xù)向下訪問時(shí)，依次退回到最近被訪問的頂點(diǎn)，若其還有未被訪問過的頂點(diǎn)，以同樣的搜索方式繼續(xù)，直到所有的頂點(diǎn)都被訪問過為止。
算法實(shí)現(xiàn)
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
文章題目：第六章圖-創(chuàng)新互聯(lián)
瀏覽地址：http://m.jiaotiyi.com/article/dphppo.html