第六章知識點總結

?

圖是由一個頂點集V和一個邊集E構成的數(shù)據(jù)結構。???

?

圖的基于鄰接矩陣的結構定義

1 //用兩個數(shù)組分別存儲頂點表和鄰接矩陣 2 const int MVNum = 100; //最大頂點數(shù) 3 typedef char VerTexType; /假設頂點的數(shù)據(jù)類型為字符型 4 typedef int ArcType; //假設邊的權值類型為整型 5 typedef struct{ 6 VerTexType vexs[MVNum]; //頂點表 7 ArcType arcs[MVNum][MVNum]; //鄰接矩陣 8 int vexnum,arcnum; //圖的當前點數(shù)和邊數(shù) 9 }AMGraph; 圖的基于鄰接矩陣的結構定義

?

?

鄰接矩陣與鄰接表表示法的關系

?

?

?

鄰接表中頂點的結構：

?

1 typedef struct { 2 VerTexType data; // 頂點信息 3 ArcNode *firstarc; 4 // 指向第一條依附該頂點的弧 5 } VNode, AdjList[MVNUM]; 鄰接表中頂點的結構

?

鄰接表中鄰接點的結構

?

1 typedef struct ArcNode { 2 int adjvex; //該邊所指向的頂點的位置 3 struct ArcNode *nextarc; //指向下一條邊的指針 4 OtherInfo info; //和邊相關的信息，例如權值 5 } ArcNode 鄰接表中鄰接點的結構

?

?

圖的基于鄰接表的結構定義

?

1 typedef struct { 2 AdjList vertices; 3 int vexnum, arcnum; 4 //頂點數(shù)和邊數(shù) 5 } ALGraph 圖的基于鄰接表的結構定義

?

圖的遍歷：

（也是一種遞歸調用）

1：深度優(yōu)先搜索：（DFS）

即先縱向訪問，訪問到底了再回來

2：廣度優(yōu)先搜索：（BFS）

即橫先搜索，搜索完一層再到下一層，不會往回走。

?

頂點a出發(fā)的深度優(yōu)先遍歷順序(不唯一)：

??? a b c f e d

頂點a出發(fā)的廣度優(yōu)先遍歷順序(不唯一)：

a b e d c f

?

?

圖的應用：

最小生成樹：

1：普里姆算法：（選頂點）（適合稠密網(wǎng)）

我的理解：選一個頂點，然后在它的鄰接頂點中選擇權值最小的，做下一個頂點，直到下一個頂點是被選過的，然后沿原路返回，繼續(xù)尋找沒訪問過的權值最小的頂點，直到全部頂點被訪問完。

?

2：克魯斯卡爾算法：（選邊）（適合稀疏網(wǎng)）

（1）???? 先把權值從小到大排列

（2）???? 每個頂點自成一個聯(lián)通分量，成一個集合T

（3）???? 選擇兩個權值最小的聯(lián)通分量，若他們不形成回路，則結合成新的聯(lián)通分量，刪了結合前的，把結合后的加入集合T

（4）???? 直到所有頂點都在一條聯(lián)通分量上即結束。

?

本周反思：對于關于圖的應用，基本定義能理解，但是對于代碼如何實現(xiàn)算法思想還不是很理解，應用在具體問題還是有點難度，PTA的作業(yè)還沒寫完，希望下周能熟練應用圖的方法思想去解題。

?

轉載于:https://www.cnblogs.com/tann/p/10891529.html

總結

以上是生活随笔為你收集整理的第六章 图 学习小结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。