第六章圖-創(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è)計制作定制制作,公司網(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 不能為空，一個圖至少得有一個頂點(diǎn)，圖不可以是空圖；圖中的頂點(diǎn)個數(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)

樹與有向樹

2 圖的存儲結(jié)構(gòu) 2.1 領(lǐng)接矩陣

領(lǐng)接矩陣：使用一個一維數(shù)組存儲頂點(diǎn)信息，使用一個二維數(shù)組存儲邊的信息（頂點(diǎn)間的鄰接關(guān)系），這個二維數(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)的邊是否存在時，可以將其定義為0表示邊不存在，1表示邊存在。

無向圖的鄰接矩陣是一個對稱矩陣，對于規(guī)模較大的對稱矩陣可以采用壓縮存儲。

頂點(diǎn)數(shù)為n的圖，鄰接矩陣表示法的空間復(fù)雜度為O(n^2)

2.2 鄰接表

鄰接表：對每個頂點(diǎn)建立一個單鏈表，單鏈表中存儲依附于這個頂點(diǎn)的邊，結(jié)合順序存儲和鏈?zhǔn)酱鎯Α?/p>

#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ù)
};

鄰接表中：

• 對于無向圖，所需的存儲空間為|V| + 2*|E|,|V|為頂點(diǎn)數(shù)，|E|為邊數(shù)，因?yàn)橐粭l邊的信息會存儲兩次
• 對于有向圖，所需的存儲空間為|V| + |E|,|V|為頂點(diǎn)數(shù)，|E|為邊數(shù)
• 圖的鄰接表的表示方式并不唯一

2.3 十字鏈表（有向圖）

2.4 鄰接多重表（無向圖）

3 圖的基本操作

圖的基本操作獨(dú)立于圖的存儲結(jié)構(gòu)，不同的存儲結(jié)構(gòu)，同一操作算法的不同實(shí)現(xiàn)會有不同的性能。下面針對鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)進(jìn)行分析：

判斷圖中是否存在邊(x,y)或者弧

求圖中與頂點(diǎn)x鄰接的邊

4 圖的遍歷

圖的遍歷是指，從圖的某一個頂點(diǎn)出發(fā)，按某種搜索方式，沿著圖中的邊對其他頂點(diǎn)訪問一次（僅僅訪問一次）。為避免同一頂點(diǎn)被訪問多次，在遍歷的過程中，需記下每個已經(jīng)訪問過的頂點(diǎn)，可以使用一個數(shù)組來存儲這些已經(jīng)訪問過的頂點(diǎn)。

圖的遍歷算法主要有兩種：廣度優(yōu)先和深度優(yōu)先。

4.1 廣度優(yōu)先遍歷 算法思想

廣度優(yōu)先搜索（Breadth-First-Search，BFS）。類似于二叉樹的層序遍歷。

算法思想：找到與一個頂點(diǎn)相鄰的所有頂點(diǎn)，標(biāo)記哪些頂點(diǎn)被訪問過，借助一個輔助數(shù)組，為了實(shí)現(xiàn)逐層訪問，還需要借助一個輔助隊(duì)列，用來存儲正在訪問的頂點(diǎn)的下一層頂點(diǎn)。

算法實(shí)現(xiàn)

算法性能分析

廣度優(yōu)先生成樹

廣度優(yōu)先生成森林

4.2 深度優(yōu)先遍歷 算法思想

深度優(yōu)先（Depth-First-Search，DFS），類似于樹的先序遍歷。

基本思想：從一個頂點(diǎn)v1開始，訪問與其鄰接且未被訪問的任意頂點(diǎn)w1，再訪問與w1鄰接且未被訪問的任意頂點(diǎn)，重復(fù)直到不能繼續(xù)向下訪問時，依次退回到最近被訪問的頂點(diǎn)，若其還有未被訪問過的頂點(diǎn)，以同樣的搜索方式繼續(xù)，直到所有的頂點(diǎn)都被訪問過為止。

算法實(shí)現(xiàn)

算法性能分析

5 圖的應(yīng)用 5.1 最小生成樹 5.2 最短路徑問題 BFS算法 Dijkstra算法 Floyd算法 5.3 有向無環(huán)圖描述表達(dá)式 5.4 拓?fù)渑判? 5.5 關(guān)鍵路徑

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：第六章圖-創(chuàng)新互聯(lián)
鏈接URL：http://muchs.cn/article30/dphppo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、營銷型網(wǎng)站建設(shè)、云服務(wù)器、網(wǎng)站建設(shè)、網(wǎng)站設(shè)計公司、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)