本章，我們學(xué)習(xí)了圖。

首先是圖(GRAPH)的定義

一種非線性數(shù)據(jù)結(jié)構(gòu)，由有窮、非空的點(diǎn)集V(G)和邊集E(G)組成。當(dāng)G中的每條邊有方向時(shí)，稱G為有向圖，有向邊（用一對(duì)尖括號(hào)<a,b>）又稱為弧，起始頂點(diǎn)被稱為弧尾，終止頂點(diǎn)被稱為弧頭，每條邊無方向時(shí)（用一對(duì)括號(hào)表示（a,b）和（b,a）一樣），被稱為無向圖。

圖的存儲(chǔ)方式

1.鄰接矩陣（二維數(shù)組存儲(chǔ)）

?

void creat(vexList GV, adjmatrix GA, int n,int e){int i,j,k,w;cout << "輸入"<<n<<"個(gè)頂點(diǎn)的值:"<<endl;//初始化頂點(diǎn)數(shù)組for(int i = 0; i < n; i++) { cin>>GV[i];}//初始化鄰接矩陣 for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){if(i==j) GA[i][j] = 0;else GA[i][j] = maxValue;}//建立鄰接數(shù)組 cout << "輸入"<<e<<"條邊:"<<endl;for(int k = 0; k < e; k++){cin >> i >> j >>w;GA[i][j] =GA[j][i] = w;}}

2.鄰接表存儲(chǔ)

3.編輯數(shù)組

然后是本章的重點(diǎn)

鄰接矩陣表示法的特點(diǎn)：

優(yōu)點(diǎn)是容易實(shí)現(xiàn)圖的操作。

缺點(diǎn)是空間效率為O(n2)。對(duì)稀疏圖浪費(fèi)空間。

?

圖的遍歷

DFS：從圖中某個(gè)頂點(diǎn)V0 出發(fā)，訪問此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到

BFS：在訪問了起始點(diǎn)v之后，依次訪問 v 的鄰接點(diǎn)； 然后再依次訪問這些頂點(diǎn)中未被訪問過的鄰接點(diǎn)； 直到所有頂點(diǎn)都被訪問過為止。

在這周我們還學(xué)習(xí)了求最短路徑的方法，我覺得很有意思。

分別是Dijkstra算法和Floyd算法。

?

對(duì)于上次的目標(biāo)，首先敲代碼的積極性有提高，但pta的作業(yè)還是卡著ddl完成的，然后就是上課有時(shí)候會(huì)有點(diǎn)走神，導(dǎo)致有些小細(xì)節(jié)要課后去問同學(xué)才行，就還是希望自己能夠把學(xué)習(xí)當(dāng)做樂趣而不是工作。

ps：圖片來自CSDN

?

轉(zhuǎn)載于:https://www.cnblogs.com/Lnnnn/p/10890873.html

總結(jié)

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

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