前言

記錄實驗，同時也是記錄常見數據結構算法的實現。

---

廣州大學學生實驗報告

開課實驗室：計算機科學與工程實驗（電子樓416A）
學院 計算機科學與網絡工程學院
實驗課程 數據結構實驗
實驗項目 實驗三 圖的操作與實現

• 一、實驗目的：
  1、圖的鄰接表和鄰接矩陣存儲
  2、圖的各種遍歷算法實現
  3、最小生成樹的算法實現
  4、最短路徑的算法實現
• 二、使用儀器、器材
  微機一臺
  操作系統：Win10
  編程軟件：C++
• 三、實驗內容及原理
  1、圖的鄰接表和鄰接矩陣存儲 （返回目錄🖱）
  建立下圖的鄰接表或鄰接矩陣，并輸出之；

#include <iostream> using namespace std;#define MaxInt 32767 //定義極大值，即∞ #define MVNum 100 //最大定點數typedef struct AMGraph //定義鄰接矩陣結構 {char vexs[MVNum];int arcs[MVNum][MVNum];int vexnum, arcnum; //分別為結點數和邊數 }AMGraph;//獲取某定點在無向圖中的位置 int LocateVex(AMGraph G, char v) {for (int i = 0; i < G.vexnum; i++){if (G.vexs[i] == v){return i;break;}} }void CreatUDN(AMGraph& G) {cout << "請輸入無向圖的總頂點數和邊數" << endl;cout << "頂點數:"; cin >> G.vexnum;//設置一個循環用于檢測輸入邊數是否超過確定頂點數的無向圖的最大邊數while (1){cout << "邊數:"; cin >> G.arcnum;if (G.arcnum > ((G.vexnum) * (G.vexnum - 1) / 2))cout << "邊數超出限制,請重新輸入邊數" << endl;else break;}//輸入各頂點的信息for (int i = 0; i < G.vexnum; i++){cout << "第" << i + 1 << "個頂點的名稱: ";cin >> G.vexs[i];}//初始化各邊的權重（設置為無窮大）for(int i=0;i<G.vexnum;i++)for (int j = 0; j < G.vexnum; j++){G.arcs[i][j] = MaxInt;}//構建鄰接矩陣cout << "請輸入每兩個頂點及其邊的權重" << endl;for (int i = 0; i < G.arcnum; i++){char v1, v2;//任意兩個頂點int weight; //邊權重cout << "請輸入第" << i + 1 << "條邊及其兩個頂點的名稱( 形如（1 0 28））: ";cin >> v1 >> v2 >> weight;int index1, index2;//v1,v2的在無向圖中的序號index1 = LocateVex(G, v1); index2 = LocateVex(G, v2);G.arcs[index1][index2] = weight;G.arcs[index2][index1] = G.arcs[index1][index2];}cout << "無向網構建完成......"<<endl;}//輸出鄰接矩陣無向網 void AMGraph_show(AMGraph G) {for (int i = 0; i < G.vexnum; i++){for (int j = 0; j < G.vexnum; j++){if (G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] << " ";else cout << "∞ ";}cout << endl;} }int main() {AMGraph G;CreatUDN(G);AMGraph_show(G);}

2、圖的各種遍歷算法實現 （返回目錄🖱）
以0結點為起點實現上述圖的深度優先和廣度優先遍歷算法；

#include <iostream> using namespace std;#define MaxInt 32767 //定義極大值，即∞ #define MVNum 100 //最大頂點數 bool visited[MVNum]; typedef struct AMGraph //定義鄰接矩陣結構 {char vexs[MVNum];int arcs[MVNum][MVNum];int vexnum, arcnum; //分別為結點數和邊數 }AMGraph;//獲取某定點在無向圖中的位置 int LocateVex(AMGraph G, char v) {for (int i = 0; i < G.vexnum; i++){if (G.vexs[i] == v){return i;break;}} }void CreatUDN(AMGraph& G) {cout << "請輸入無向圖的總頂點數和邊數" << endl;cout << "頂點數:"; cin >> G.vexnum;//設置一個循環用于檢測輸入邊數是否超過確定頂點數的無向圖的最大邊數while (1){cout << "邊數:"; cin >> G.arcnum;if (G.arcnum > ((G.vexnum) * (G.vexnum - 1) / 2))cout << "邊數超出限制,請重新輸入邊數" << endl;else break;}//輸入各頂點的信息for (int i = 0; i < G.vexnum; i++){cout << "第" << i + 1 << "個頂點的名稱: ";cin >> G.vexs[i];}//初始化各邊的權重（設置為無窮大）for (int i = 0; i < G.vexnum; i++){visited[i] = 0;for (int j = 0; j < G.vexnum; j++)G.arcs[i][j] = MaxInt;}//構建鄰接矩陣cout << "請輸入每兩個頂點及其邊的權重" << endl;for (int i = 0; i < G.arcnum; i++){char v1, v2;//任意兩個頂點int weight; //邊權重cout << "請輸入第" << i + 1 <<"條邊及其兩個頂點的名稱( 形如（1 0 28））: ";cin >> v1 >> v2 >> weight;int index1, index2;//v1,v2的在無向圖中的序號index1 = LocateVex(G, v1); index2 = LocateVex(G, v2);G.arcs[index1][index2] = weight;G.arcs[index2][index1] = G.arcs[index1][index2];}cout << "無向網構建完成......" << endl;}//輸出鄰接矩陣無向網 void AMGraph_show(AMGraph G) {for (int i = 0; i < G.vexnum; i++){for (int j = 0; j < G.vexnum; j++){if (G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] << " ";else cout << "∞ ";}cout << endl;} }//---------下面實現深度優先遍歷算法--------- void DFS_AM(AMGraph &G, int v) {//訪問名稱為v的結點,并標記為已訪問int i;cout <<G.vexs[v]; visited[v] = true; //標記為已訪問//遞歸調用深度優先遍歷算法for ( i = 0; i < G.vexnum; i++){if ((G.arcs[v][i] != MaxInt) && !visited[i])DFS_AM(G,i);} } void DFSTraverse(AMGraph &G) {int i;for (i = 0; i < G.vexnum; ++i)visited[i] = 0;for (i = 0; i < G.vexnum; ++i){if (!visited[i])DFS_AM(G, i);}}int main() {AMGraph G;CreatUDN(G);AMGraph_show(G);char x;cout << "請輸入遍歷開始的結點 ";cin >> x;DFSTraverse(G); }

3、最小生成樹的算法實現（返回目錄🖱）
利用普里姆（Prim）算法或克魯斯卡爾(Kruskal)算法求上圖的最小生成樹，算法實現代碼必須有注釋。

#include <iostream> using namespace std;#define MaxInt 32767 //定義極大值，即∞ #define MVNum 100 //最大頂點數 bool visited[MVNum]; typedef struct AMGraph //定義鄰接矩陣結構 {char vexs[MVNum];int arcs[MVNum][MVNum];int vexnum, arcnum; //分別為結點數和邊數 }AMGraph;//獲取某定點在無向圖中的位置 int LocateVex(AMGraph G, char v) {for (int i = 0; i < G.vexnum; i++){if (G.vexs[i] == v){return i;break;}} }//--------------構建無向網------------------- void CreatUDN(AMGraph& G) {cout << "請輸入無向圖的總頂點數和邊數" << endl;cout << "頂點數:"; cin >> G.vexnum;//設置一個循環用于檢測輸入邊數是否超過確定頂點數的無向圖的最大邊數while (1){cout << "邊數:"; cin >> G.arcnum;if (G.arcnum > ((G.vexnum) * (G.vexnum - 1) / 2))cout << "邊數超出限制,請重新輸入邊數" << endl;else break;}//輸入各頂點的信息for (int i = 0; i < G.vexnum; i++){cout << "第" << i + 1 << "個頂點的名稱: ";cin >> G.vexs[i];}//初始化各邊的權重（設置為無窮大）for (int i = 0; i < G.vexnum; i++){visited[i] = 0;for (int j = 0; j < G.vexnum; j++)G.arcs[i][j] = MaxInt;}//構建鄰接矩陣cout << "請輸入每兩個頂點及其邊的權重" << endl;for (int i = 0; i < G.arcnum; i++){char v1, v2;//任意兩個頂點int weight; //邊權重cout << "請輸入第" << i + 1 << "條邊及其兩個頂點的名稱( 形如（1 0 28））: ";cin >> v1 >> v2 >> weight;int index1, index2;//v1,v2的在無向圖中的序號index1 = LocateVex(G, v1); index2 = LocateVex(G, v2);G.arcs[index1][index2] = weight;G.arcs[index2][index1] = G.arcs[index1][index2];}cout << "無向網構建完成......" << endl; }//輸出鄰接矩陣無向網 void AMGraph_show(AMGraph G) {for (int i = 0; i < G.vexnum; i++){for (int j = 0; j < G.vexnum; j++){if (G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] << " ";else cout << "∞ ";}cout << endl;} }//輔助數組，用于篩選權值最小的鄰接結點 typedef struct {int adjvex;int lowcost; }closedge[MVNum];closedge theclose; //全局變量，輔助數組//從輔助數組中找出權值最小的邊的數組下標 int minimun(AMGraph G, closedge c) {int min = MaxInt; //min初始化為MaxIntint min_index = -1; //max_index表示輔助數組中最小權值邊的數組下標for (int i = 0; i < G.vexnum; i++){if (c[i].lowcost > 0 && c[i].lowcost < min){min = c[i].lowcost;min_index = i;}}return min_index; }//-------Prim算法-------- void MSTreePrim(AMGraph G,char v) {int k = LocateVex(G,v); //結點v在頂點數組中的下標//初始化，將結點v的鄰接邊的權重和鄰接頂點存入輔助數組theclosefor (int i = 0; i < G.vexnum; i++){if (i != k){theclose[i].adjvex = k;theclose[i].lowcost = G.arcs[k][i];}}theclose[k].lowcost = 0; //將結點v放入輔助數組//繼續往輔助數組里添加結點for (int i = 1; i < G.vexnum; i++){//找出權值最小的邊的下標k = minimun(G, theclose);//輸出權值最小邊的頂點cout << G.vexs[theclose[k].adjvex] << G.vexs[k] << endl;//將結點k歸入theclosetheclose[k].lowcost = 0;/*往theclose中加入新結點之后，需要重新計算最小邊是哪條,由此頂點出發，到達其它各頂點的權值是否比之前記錄的權值還要小，如果還小，則更新*/for (int i = 0; i < G.vexnum; i++){if (G.arcs[k][i] < theclose[i].lowcost){theclose[i].lowcost = G.arcs[k][i];theclose[i].adjvex = k;}}}cout << "Prinm算法最小生成樹構建完成......"; }int main() {AMGraph G;CreatUDN(G);AMGraph_show(G); //輸出鄰接矩陣cout << "請輸入開始遍歷的頂點: ";char x;cin >> x;MSTreePrim(G, x);//輸出最小生成樹 }

4、最短路徑的算法實現（返回目錄🖱）
利用狄克斯特拉（Dijkstra）算法求上圖中0結點到其它結點的最短路徑，算法實現代碼必須有注釋

#include <iostream> using namespace std;#define MaxInt 32767 //定義極大值，即∞ #define MVNum 100 //最大頂點數 bool visited[MVNum]; typedef struct AMGraph //定義鄰接矩陣結構 {char vexs[MVNum];int arcs[MVNum][MVNum];int vexnum, arcnum; //分別為結點數和邊數 }AMGraph;//獲取某定點在無向圖中的位置 int LocateVex(AMGraph G, char v) {for (int i = 0; i < G.vexnum; i++){if (G.vexs[i] == v){return i;break;}} }//--------------構建無向網------------------- void CreatUDN(AMGraph& G) {cout << "請輸入無向圖的總頂點數和邊數" << endl;cout << "頂點數:"; cin >> G.vexnum;//設置一個循環用于檢測輸入邊數是否超過確定頂點數的無向圖的最大邊數while (1){cout << "邊數:"; cin >> G.arcnum;if (G.arcnum > ((G.vexnum) * (G.vexnum - 1) / 2))cout << "邊數超出限制,請重新輸入邊數" << endl;else break;}//輸入各頂點的信息for (int i = 0; i < G.vexnum; i++){cout << "第" << i + 1 << "個頂點的名稱: ";cin >> G.vexs[i];}//初始化各邊的權重（設置為無窮大）for (int i = 0; i < G.vexnum; i++){visited[i] = 0;for (int j = 0; j < G.vexnum; j++)G.arcs[i][j] = MaxInt;}//構建鄰接矩陣cout << "請輸入每兩個頂點及其邊的權重" << endl;for (int i = 0; i < G.arcnum; i++){char v1, v2; //任意兩個頂點int weight; //邊權重cout << "請輸入第" << i + 1 << "條邊及其兩個頂點的名稱( 形如（1 0 28））: ";cin >> v1 >> v2 >> weight;int index1, index2; //v1,v2的在無向圖中的序號index1 = LocateVex(G, v1); index2 = LocateVex(G, v2);G.arcs[index1][index2] = weight;G.arcs[index2][index1] = G.arcs[index1][index2];}cout << "無向網構建完成......" << endl; }//輸出鄰接矩陣無向網 void AMGraph_show(AMGraph G) {for (int i = 0; i < G.vexnum; i++){for (int j = 0; j < G.vexnum; j++){if (G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] << " ";else cout << "∞ ";}cout << endl;} }//-----------Dijkstra算法的實現----------- int dist[MVNum]; //存放v0到vi的最短路徑長度 int sign[MVNum]; //若vi已卻定最短路徑長度，則為1，否則為0 int pre[MVNum]; //記錄vi的前驅結點，若無前驅結點則為-1void Dijkstra(AMGraph G, int v) {//初始化dist、sign、prefor (int i = 0; i < G.vexnum; i++){dist[i] = G.arcs[v][i];sign[i] = 0; //初始化為0if (dist[i] < MaxInt) pre[i] = v; //若存在邊，則將前驅初始化為原點else pre[i] = -1; //若不存在邊，則將前驅初始化為-1}sign[v] = 1;for (int i = 0; i < G.vexnum-1; i++){int min_v; //待選點int min = MaxInt;//尋找dist中的最短路徑for (int i = 0; i < G.vexnum; i++){if (sign[i] == 0 && dist[i] < min){min = dist[i];min_v = i;}}sign[min_v] = 1; //將找到最短路徑的頂點的標志置為1//重置每個頂點的最短路徑值for (int i = 0; i < G.vexnum; i++){if (sign[i] == 0 && dist[i] > dist[min_v] + G.arcs[min_v][i]){dist[i] = dist[min_v] + G.arcs[min_v][i];pre[i] = min_v;}}}//打印結果cout << "輸出頂點" << v << "到各頂點的最短路徑" << endl << "result:" << endl;for (int i = 0; i < G.vexnum; i++){cout << "<" << v << "," << i << "> : ";int p = pre[i];if (p != -1){cout << " " << dist[i] << "\t";cout << i;while (p != v){cout << "<--" << p;p = pre[p]; //逆向輸出路徑}cout << "<--" << v;}else cout << "∞"; //若不可達則輸出無窮cout << endl;} }int main() {AMGraph G;CreatUDN(G);AMGraph_show(G); //輸出鄰接矩陣Dijkstra(G, 0); //輸出頂點0到各頂點的最短路徑 }

四、實驗過程原始數據記錄
1.、圖的鄰接表和鄰接矩陣存儲
建立下圖的鄰接表或鄰接矩陣，并輸出之；

思路：通過構建鄰接矩陣來實現無向圖。

2、圖的各種遍歷算法實現
以0結點為起點實現上述圖的深度優先和廣度優先遍歷算法；

3、最小生成樹的算法實現
利用普里姆（Prim）算法或克魯斯卡爾(Kruskal)算法求上圖的最小生成樹，算法實現代碼必須有注釋。

4、最短路徑的算法實現
利用狄克斯特拉（Dijkstra）算法求上圖中0結點到其它結點的最短路徑，算法實現代碼必須有注釋。

五、實驗結果及分析
通過構造鄰接矩陣實現了圖的存儲、圖的深度優先遍歷算法、圖的最小生成樹Prim算法、最短路徑的Dijkstra算法，通過對這些算法的實現，讓我對圖有了更深的理解。

總結

以上是生活随笔為你收集整理的实验三 图的操作与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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