---

一，實驗目的

1．掌握圖的鄰接矩陣、鄰接表的表示方法及建立算法；
2．掌握圖的深度優先遍歷、廣度優先遍歷等基本操作的算法；
3．掌握圖的最小生成樹、關鍵路徑等應用問題的求解算法；
4．進一步加深對圖的幾種基本應用算法的理解，逐步培養解決實際問題的編程能力。

二，實驗內容

已知無向連通圖G如下圖所示。完成圖的下列基本操作：
（1）建立圖的鄰接矩陣，輸出鄰接矩陣；
（2）建立圖的鄰接表，輸出鄰接表；
（3）求鄰接表表示的圖的深度優先遍歷序列；
（4）求鄰接矩陣表示的圖的深度優先遍歷序列；
（5）求鄰接表表示的圖的廣度優先遍歷序列；
（6）求鄰接矩陣表示的圖的廣度優先遍歷序列。

三，實驗要求

（1）建立頭文件graph.h，其中定義了圖的鄰接矩陣和鄰接表表示的存儲結構，本實驗的其它實驗題目也可共享使用，其代碼如下：

#define MAXV 30      			// 最大頂點數
typedef int InfoType;
//以下定義圖的鄰接矩陣數據結構
typedef struct {					//定義圖的頂點結構int no;						//頂點編號InfoType info;					//頂點其它信息，可用于
} VertexType;
typedef struct {					//定義圖鄰接矩陣VertexType vexs[MAXV];		//頂點向量int arcs[MAXV][MAXV];		//鄰接矩陣int vexnum, arcnum;			//圖的當前頂點數和邊數
} MGraph;
//以下定義圖的鄰接表數據結構
typedef struct ArcNode {			//定義表結點類型int  adjvex;					//頂點序號int  weight;					//邊或弧的權值struct ArcNode *nextarc;		//指向下一個表結點的指針
} ArcNode;
typedef struct VNode {				//定義頭結點類型VertexType data;ArcNode *firstarc;
} VNode
//typedef  VNode  AdjList[MAXV];	//定義頭結點數組
typedef struct {					//定義圖的鄰接表類型VNode  vertices[MAXV];int  vexnum, arcnum;
} LGraph;

（2）完善參考程序，在程序中的下劃線處填寫適當的語句。
（3）設計測試數據，調試、測試完善后的參考程序，保存和打印測試結果，對結果進行分析。

四，算法分析

（1）深度優先搜索遍歷算法
從圖中某頂點v出發：
① 訪問頂點v；
② 依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；
③ 若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。

（2）廣度優先搜索遍歷算法
從圖中某頂點vi出發：
① 訪問頂點vi ；
② 訪問vi 的所有未被訪問的鄰接點w1 ,w2 , …wk ；
③ 依次從這些鄰接點（在步驟②中訪問的頂點）出發，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；
④ 若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行廣度優先搜索遍歷，直到圖中所有頂點均被訪問過為止。
為實現③，需要保存在步驟②中訪問的頂點，而且訪問這些頂點的鄰接點的順序為：先保存的頂點，其鄰接點先被訪問。

五，示例代碼

8-1.cpp源碼

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include "graph.h"// 訪問標志數組
int visited[MAXV];
// 廣度優先遍歷存儲隊列
int queue[MAXV];// 建立圖的鄰接矩陣
void CreatMG(MGraph& mg) {int i, j;int A[7][7];mg.vexnum = 7;mg.arcnum = 9;for (i = 0; i < mg.vexnum; i++) {for (j = 0; j < mg.vexnum; j++) {A[i][j] = 0;}}A[0][1] = A[0][2] = A[0][6] = 1;A[1][3] = 1;A[2][3] = A[2][5] = A[2][6] = 1;A[3][4] = 1;A[5][6] = 1;for (i = 1; i < mg.vexnum; i++) {for (j = 0; j < i; j++) {A[i][j] = A[j][i];}}for (i = 0; i < mg.vexnum; i++) {for (j = 0; j < mg.vexnum; j++) {mg.arcs[i][j] = A[i][j];}}
}// 由圖的鄰接矩陣創建圖的鄰接表
void CreatLG(LGraph*& lg, MGraph mg) {int i, j;ArcNode* p;lg = (LGraph*)malloc(sizeof(LGraph));for (i = 0; i < mg.vexnum; i++) {lg->vertices[i].firstarc = NULL;}for (i = 0; i < mg.vexnum; i++) {for (j = mg.vexnum - 1; j >= 0; j--) {if (mg.arcs[i][j] != 0) {p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->weight = mg.arcs[i][j];p->nextarc = lg->vertices[i].firstarc;lg->vertices[i].firstarc = p;}}}lg->vexnum = mg.vexnum;lg->arcnum = mg.arcnum;
}// 輸出圖的鄰接矩陣
void OutputMG(MGraph mg) {int i, j;for (i = 0; i < mg.vexnum; i++) {for (j = 0; j < mg.vexnum; j++) {printf("%3d", mg.arcs[i][j]);}printf("\n");}
}// 輸出圖的鄰接表
void OutputLG(LGraph* lg) {int i;ArcNode* p;for (i = 0; i < lg->vexnum; i++) {p = lg->vertices[i].firstarc;if (p) {printf("%3d：", i);}while (p) {printf("%3d", p->adjvex);p = p->nextarc;}printf("\n");}
}// 鄰接表表示的圖的遞歸深度優先遍歷
void LDFS(LGraph* lg, int i) {ArcNode* p;printf("%3d", i);visited[i] = 1;p = lg->vertices[i].firstarc;while (p) {if (visited[p->adjvex] == 0) {LDFS(lg, p->adjvex);}p = p->nextarc;}
}// 鄰接矩陣表示的圖的遞歸深度優先遍歷
void MDFS(MGraph mg, int i) {int j;printf("%3d", i);visited[i] = 1;for (j = 0; j < mg.vexnum; j++) {if (mg.arcs[i][j] != 0 && visited[j] == 0) {MDFS(mg, j);}}
}// 鄰接表表示的圖的廣度優先遍歷
void LBFS(LGraph* lg, int s) {int i, v, w, front, rear;ArcNode* p;for (i = 0; i < lg->vexnum; i++) {visited[i] = 0;}front = rear = 0;printf("%3d", s);visited[s] = 1;queue[rear++] = s;while (front < rear) {v = queue[front++];for (p = lg->vertices[v].firstarc; p != NULL; p = p->nextarc) {w = p->adjvex;if (visited[w] == 0) {printf("%3d", w);visited[w] = 1;queue[rear++] = w;}}}
}// 鄰接矩陣表示的圖的廣度優先遍歷
void MBFS(MGraph mg, int s) {int i, j, v, front, rear;for (i = 0; i < mg.vexnum; i++) {visited[i] = 0;}front = rear = 0;printf("%3d", s);visited[s] = 1;queue[rear++] = s;while (front < rear) {v = queue[front++];for (i = 0; i < mg.vexnum; i++) {for (j = 0; j < mg.vexnum; j++) {if (mg.arcs[v][j] != 0 && visited[j] == 0) {printf("%3d", j);visited[j] = 1;queue[rear++] = j;}}}}
}int main() {LGraph* lg;MGraph mg;int i;CreatMG(mg);CreatLG(lg, mg);printf("（1）當前圖的鄰接矩陣是：\n");OutputMG(mg);printf("（2）當前圖的鄰接表是：\n");OutputLG(lg);for (i = 0; i < mg.vexnum; i++) {visited[i] = 0;}getchar();printf("（3）鄰接表表示的圖的深度優先遍歷序列是：");LDFS(lg, 0);getchar();for (i = 0; i < mg.vexnum; i++) {visited[i] = 0;}printf("（4）鄰接矩陣表示的圖的深度優先遍歷序列是：");MDFS(mg, 0);getchar();printf("（5）鄰接表表示的圖的廣度優先遍歷序列是：");LBFS(lg, 0);getchar();printf("（6）鄰接矩陣表示的圖的廣度優先遍歷序列是：");MBFS(mg, 0);printf("\n");return 0;
}

graph.h源碼

#pragma once
#ifndef GRAPH_H
#define GRAPH_H// 定義圖的最大頂點數
const int MAXV = 100;// 定義弧節點結構體
typedef struct ArcNode {int adjvex;int weight;struct ArcNode* nextarc;
} ArcNode;// 定義頂點結構體
typedef struct VNode {ArcNode* firstarc;
} VNode;// 定義鄰接表結構體
typedef struct {VNode vertices[MAXV];int vexnum, arcnum;
} LGraph;// 定義鄰接矩陣結構體
typedef struct {int arcs[MAXV][MAXV];int vexnum, arcnum;
} MGraph;#endif    

六，操作步驟

1，雙擊Visual Studio程序快捷圖標，啟動程序。

2，之前創建過項目的話，直接打開即可，這里選擇【創建新項目】。

3，單擊選擇【空項目】——單擊【下一步】按鈕。

4，編輯好項目的名稱和存放路徑，然后單擊【創建】按鈕。

5，創建C++程序文件，右擊【源文件】——選擇【添加】——【新建項】。

6，輸入項目名稱8-1.cpp，單擊【添加】按鈕。

7，輸入項目名稱graph.h，單擊【添加】按鈕，此文件要定義 MGraph、LGraph、ArcNode 等類型，同時定義 MAXV 常量。

8，編寫代碼，單擊運行按鈕，運行程序。

七，運行結果

1，實驗要求的測試結構。

2，編寫代碼運行后的結果。