第一篇：北化航天工業學院~數據結構~實驗5圖
實驗五：圖的應用
班級學號姓名
一、實驗預備知識復習C++中的全局變量的概念。復習圖的鄰接矩陣和鄰接表兩種存儲方式。復習圖的兩種遍歷方法和求圖的最小生成樹的方法。
二、實驗目的掌握圖的鄰接矩陣和鄰接表兩種存儲方法。掌握有關圖的操作算法并用高級語言實現。熟悉圖的構造算法，了解實際問題的求解效率與采用何種存儲結構與算法有著密切聯系。掌握圖的兩種搜索路徑的遍歷算法。掌握求圖的最小生成樹的普里姆算法和克魯斯卡爾算法。
三、實驗內容創建給定的圖，從鄰接表和鄰接矩陣兩種存儲方式中選擇一種。對所創建的圖進行深度和廣度優先搜索遍歷，給出遍歷過程中的頂點序列。3 求圖的最小生成樹，按構造順序輸出邊的序列。編寫一個主函數，將上面函數連在一起，構成一個完整程序。將實驗源程序調試并運行。
四、實驗要求
所建立的圖為：
? 用鄰接表存儲結構時，所創建的單鏈表以結點的從小到大排列。? 注意標志數組visited[n+1] 的定義和賦值。
? 將頂點1作為起點。
五、實驗結果
給出源程序及輸入、輸出結果。
六、實驗總結
實驗過程中遇到的問題及解決方法，收獲。
第二篇：數據結構上機實驗--圖
數據結構上機實驗六
實驗內容:圖的基本操作
實驗要求:
1)圖的遍歷與基本操作要作為函數被調用.2)把自己使用的圖結構明確的表達出來.3)基本上實現每個實驗題目的要求.分組要求：可單獨完成，也可兩人一組。
實驗目的:
1)熟悉C/C++基本編程,培養動手能力.2)通過實驗,加深對圖的理解.評分標準：
1)只完成第一和第二題，根據情況得4，5分；
2）完成前3題，根據情況得5至7分；
3）在2）基礎上，選做四）中題目，根據情況得8至10分。
題目:
一)建立一個無向圖+遍歷+插入
(1)以數組表示法作為存儲結構，從鍵盤依次輸入頂點數、弧數與各弧信息建立一個無向圖；
(2)對（1）中生成的無向圖進行廣度優先遍歷并打印結果；
(3)向（1）中生成的無向圖插入一條新弧并打印結果；
二)建立一個有向圖+遍歷+插入+刪除
(1)以鄰接表作為圖的存儲結構，從鍵盤輸入圖的頂點與弧的信息建立一個有向圖；
(2)對（1）中生成的有向圖進行深度優先遍歷并打印結果；
(3)在（1）中生成的有向圖中，分別插入與刪除一條弧并打印其結果；
(4)在（1）中生成的有向圖中，分別插入與刪除一個頂點并打印結果；
(5)在（1）中生成的有向圖中,各頂點的入度與出度并打印結果；
三）基本應用題
（1）編寫算法，判斷圖中指定的兩個頂點是否連通。
（2）編寫算法，判斷圖的連通性。如果不連通，求連通分量的個數
（3）編寫算法，判斷圖中任意兩個頂點的連通性
（4）編寫算法，判斷圖中是否存在回路。
（5）實現圖的廣度優先搜索算法。
四）高級應用題
（1）實現Prim算法
（2）實現Kruskal算法
（3）實現迪杰斯特拉算法
（4）實現拓撲排序算法
（5）實現關鍵路徑算法
第三篇：數據結構 實驗一 圖[推薦]
北京郵電大學信息與通信工程學院
數據結構實驗報告
實驗名稱： 實驗二——圖 學生姓名： 佘晨陽 班
級： 2014211117 班內序號： 20 學
號： 2014210491 日
期： 2015年12月05日
1．實驗要求
根據圖的抽象數據類型的定義，使用鄰接矩陣或鄰接表實現一個圖。圖的基本功能：
1、圖的建立
2、圖的銷毀
3、深度優先遍歷圖
4、廣度優先遍歷圖
5、使用普里姆算法生成最小生成樹
6、使用克魯斯卡爾算法生成最小生成樹
7、求指定頂點到其他各頂點的最短路徑
8、其他：比如連通性判斷等自定義操作
編寫測試main()函數測試圖的正確性
2.程序分析
本實驗要求掌握圖基本操作的實現方法，了解最小生成樹的思想和相關概念，了解最短路徑的思想和相關概念，學習使用圖解決實際問題的能力。
2.1 存儲結構
存儲結構：1.不帶權值的無向圖鄰接矩陣
2.帶權值的無向圖鄰接矩陣
3.帶權值的有向圖鄰接矩陣
1．不帶權值的無向圖鄰接矩陣
第1頁 北京郵電大學信息與通信工程學院
2帶權值的無向圖鄰接矩陣.3.帶權值的有向圖鄰接矩陣
[備注]：
1.在使用打印元素、BFS、DFS 采用無權值的無向圖鄰接矩陣存儲方式 2.在使用PRIM、KRUSKAL、3.在使用最短路徑的算法時采用具有權值的有向圖鄰接矩陣存儲方式
2.2 關鍵算法分析
第2頁 北京郵電大學信息與通信工程學院
一．圖的鄰接矩陣構造函數：
1.關鍵算法： template
//帶權值的圖的構造函數 { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];}
//初始化頂點
for(k = 0;k for(i = 0;i < n;i++) { arc[k][i] =-1; if(i == k)arc[k][i] = 0; //初始化權值的大小 } visited[k] = 0;} cout << endl;for(k = 0;k //初始化邊 { cout << “請輸入線性鏈接節點:”; cin >> s1 >> s2 >> height; arc[convert(s1)][convert(s2)] = height; arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用無向圖帶權值的鄰接矩陣 } cout << endl;cout << “所得鄰接矩陣為：” << endl; for(k = 0;k for(i = 0;i < n;i++) { if(arc[k][i] ==-1) cout << “∞” << “ ”; else cout << arc[k][i] << “ ”; //打印鄰接矩陣的格式 } cout << endl; } cout << endl 2.算法的時間復雜度 第3頁 北京郵電大學信息與通信工程學院 有構造可知，初始化時其時間復雜度：O(n2) 二．深度優先便利DFS: 1.關鍵算法 ①從某頂點v出發并訪問 ②訪問v的第一個未訪問的鄰接點w，訪問w的第一個未訪問的鄰接點u，…… ③若當前頂點的所有鄰接點都被訪問過，則回溯，從上一級頂點的下一個未訪問過的頂點開始深度優先遍歷 ④直到所有和v路徑相通的頂點都被訪問到； 2.代碼圖解： 深度優先遍歷示意圖 3.代碼詳解： template for(int j = 0;j < vnum;j++) //連通圖 if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//當存在回路時，則連通深一層遍歷 } 4.時間復雜度 時間復雜度：O(n2) 空間復雜度：棧的深度O(n) 輔助空間O(n) 第4頁 北京郵電大學信息與通信工程學院 三．廣度遍歷BFS 1.關鍵算法 ①訪問頂點v ②依次訪問v的所有未被訪問的鄰接點v1,v2,v3… ③分別從v1,v2,v3…出發依次訪問它們未被訪問的鄰接點 ④反復①②③，直到所有和v路徑相通的頂點都被訪問到； 2.代碼圖解 3.代碼詳解 1.初始化隊列Q 2.訪問頂點v，visited[v]=1 3.while(隊列非空) 3.1 v=隊頭元素出隊 3.2 訪問隊頭元素的所有未訪問的鄰接點 4.時間復雜度 時間復雜度：O(n2) 空間復雜度：輔助空間O(n) 四.最小生成樹——普里姆算法 1,關鍵思路 一般情況下，假設n個頂點分成兩個集合：U(包含已落在生成樹上的結點)和V-U(尚未落在生成樹上的頂點)，則在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。主數據結構： 鄰接矩陣 輔助數據結構： int adjvex[MAXSIZE];// U集中的頂點序號 第5頁 北京郵電大學信息與通信工程學院 int lowcost[MAXSIZE]; // U?(V-U)的最小權值邊 2.代碼圖解 第6頁 北京郵電大學信息與通信工程學院 第7頁 北京郵電大學信息與通信工程學院 3;代碼詳解 template //輔助數組存儲所有到的V0邊 { adjvex[i] = 0;lowcost[i] = arc[0][i]; } lowcost[0] = 0;for(int j = 1;j < vnum;j++) //循環n-1次 { int k = Mininum(lowcost); //求下一個頂點 cout << vertex[adjvex[k]] << “->” << vertex[k] << endl; lowcost[k] = 0; //U=U+{Vk} for(int j = 0;j < vnum;j++) //設置輔助數組 { if((lowcost[j]!= 0 && arc[k][j] < lowcost[j])) { lowcost[j] = arc[k][j]; adjvex[j] = k; } } 第8頁 北京郵電大學信息與通信工程學院 } } 4,時間復雜度： 時間復雜度O(n2)，適合稠密圖 五.最小生成樹----克魯斯卡爾算法 1,關鍵思路 先構造一個只含n個頂點的子圖SG，然后從權值最小的邊開始，若它的添加不使SG中產生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止。2.代碼圖解： 3.代碼詳解 template //最小生成樹—kruskal算法 { cout<<“Krusal算法結果為：”< int k = 0, j = 0; while(k < vnum-1){ int m = vedgelist[j].fromv, n = vedgelist[j].endv; int sn1 = vset[m]; int sn2 = vset[n]; //兩個頂點分屬 第9頁 北京郵電大學信息與通信工程學院 不同的集合 if(sn1!= sn2) { cout << vertex[m] << “->” << vertex[n] << endl; k++; for(int i = 0;i < vnum;i++) { if(vset[i] == sn2) vset[i] = sn1; //集合sn2全部改成sn1 } } j++;} } 4.時間復雜度 時間復雜度O(nlogn)，適合稀疏圖 六．最短路徑——Dijkstra算法 1.關鍵代碼 ? 按路徑長度遞增的次序產生源點到其余各頂點的最短路徑。? 1)設置集合s存儲已求得的最短路徑的頂點，? 2)初始狀態：s=源點v ? 3)疊代算法： ? 直接與v相連的最近頂點vi,加入s ? 從v經過vi可以到達的頂點中最短的，加入s …… 2.代碼圖解 第10頁 北京郵電大學信息與通信工程學院 3.代碼詳解 emplate //關于最短路徑的初始化 { int v=convert(x); for(int i = 0;i < vnum;i++) //初始化路徑和點 { s[i]=0; disk[i] = arc[v][i]; if(disk[i]!= maxs)path[i] = v; else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++) //反復經過從該點到其他點的路徑 { if((v = FindMin())==-1)continue; s[v] = 1; for(int j = 0;j < vnum;j++) if(!s[j] &&(disk[j]>arc[v][j] + disk[v])) { 第11頁 北京郵電大學信息與通信工程學院 disk[j] = arc[v][j] + disk[v]; path[j] = v; } } Print(); //打印路徑長度和遍歷 } 4.時間復雜度 時間復雜度為：n^2 七．判斷連通圖算法 template { cout<<“該圖為連通圖！*******輸入成功！”< return false; } else { cout<<“該圖不為連通圖！*******請重新輸入”< return true; } } 時間復雜度：n^2 3.程序運行結果 1.測試主函數流程： 第12頁 北京郵電大學信息與通信工程學院 函數流程圖： 1.輸入圖的連接邊并打印 構造下面所示圖的鄰接矩陣： 第13頁 北京郵電大學信息與通信工程學院 2.判斷圖連通是否成功 3.BFS DFS PRIM算法的實現 第14頁 北京郵電大學信息與通信工程學院 4.克魯斯卡爾算法實現過程 4.有向圖鄰接矩陣的構建 第15頁 北京郵電大學信息與通信工程學院 插入V0位置后打印距離并開始回溯 總結 1.調試時出現的問題及解決的方法 問題一：prim算法中 解決方法：調整循環條件，修正函數體注意有無Next的區別 第16頁 北京郵電大學信息與通信工程學院 問題二：BFS和DFS同時在一個類里作用時會輸出錯誤 解決方案：每次BFS/DFS使用時都把visited數組初始化一遍 問題三：在最短路徑，經常出現了停止輸入的情況 解決方法：改return為continue，并修改打印算法 2.心得體會 通過本次實驗，基本熟練掌握了c++基本語句，尤其對圖的結構及應用有了較深了解；調試代碼時盡量做到完成一個代碼段調試一次，可以最快檢測出錯誤所在；類的封裝和調用，類的共有成員和私有成員的設置。 3.下一步的改進 第一，設置增加圖節點和邊的函數 第二，實現圖形化輸出圖的路徑的功能 第三，主函數設計簡單，不要過于累贅 4.程序中出現的亮點 1)利用dfs算法衍生生成判斷是否為連通圖的連通算法 2)采用graph類實現所有圖的所有算法，所需的數據類型均在私有成員內，封裝 3)利用convert函數采取象意輸入，采用ABCD的節點輸入方式而并非轉化成01234再輸入。 4)BFS中采用c++標準庫的。 5)打印鄰接矩陣時，打印出非鏈接的∞符號和與自身路徑的0距離 6)判斷圖為非連通圖后，提示輸入錯誤，重新輸入圖元素 第17頁 “數據結構和算法II”課程實驗報告 實驗名稱：圖及其應用 班級 姓名 學號 實驗日期： 實驗機時：2 學時 實驗成績： -----------------一.實驗目的： 1.熟練掌握圖的兩種存儲結構(鄰接矩陣和鄰接表)的表示方法 2.掌握圖的基本運算及應用 3.加深對圖的理解，逐步培養解決實際問題的編程能力 二.實驗內容：（1）基本實驗內容： 采用鄰接表或鄰接矩陣方式存儲圖，實現圖的深度遍歷和廣度遍歷； 用廣度優先搜索方法找出從一頂點到另一頂點邊數最少的路徑。三.程序及注釋： #include “stdio.h” #include “limits.h” //INT_MAX頭文件 #include “windows.h” //boolean頭文件 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 #define OVERFLOW-1 #define OK 1 #define ERROR 0 typedef int Status;typedef enum {DG,DN,UDG,UDN} GraphKind;typedef int VRType;typedef char VertexType;typedef char* InfoType;typedef int QElemType;//邊信息 typedef struct ArcCell{ VRType adj;//1或0表示是否鄰接,對帶權圖，則為權值類型 InfoType *info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//圖結構 typedef struct { VertexType vexs[MAX_VERTEX_NUM];//定點向量 AdjMatrix arcs; //鄰接矩陣，為一二維數組 //圖的當前頂點數和弧數 int vexnum,arcnum;GraphKind kind; //圖的種類標志 }MGraph;//輔助隊列 typedef struct QNode{ QElemType data;//數值域 struct QNode *next;//指針域 }QNode, *QueuePtr;typedef struct{ QueuePtr front;//隊頭 QueuePtr rear;//隊尾 }LinkQueue;//初始化隊列 Status InitQueue(LinkQueue &Q){ Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode));if(!Q.front){ printf(“內存分配失敗!”);exit(OVERFLOW);} Q.front->next = NULL;return OK;} //插入元素到隊尾 Status EnQueue(LinkQueue &Q,QElemType e){ QueuePtr p =(QueuePtr)malloc(sizeof(QNode));if(!p){printf(“n內存分配失敗!”);exit(OVERFLOW);} p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;} //隊列判空 Status QueueEmpty(LinkQueue Q){ return Q.front == Q.rear;} //銷毀隊列 Status DestroyQueue(LinkQueue &Q){ while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear;} return OK;} //刪除隊頭元素 Status DeQueue(LinkQueue &Q,QElemType &e){ if(QueueEmpty(Q)){printf(“n隊列為空！”);return ERROR;} QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear==p)Q.rear = Q.front;free(p);return OK;} //對頂點v定位，返回該頂點在數組的下標索引，若找不到則返回-1 int LocateVex(MGraph G,char v){ for(int i=0;i G.kind = UDN;printf(“輸入頂點個數和邊數(如：4,3):”);int vexnum,arcnum;scanf(“%d,%d”,&vexnum,&arcnum);G.vexnum=vexnum;G.arcnum=arcnum;//判斷是否超過頂點最大個數 while(G.vexnum>MAX_VERTEX_NUM){printf(“最大頂點為20，重新輸入(如：4,3):”);scanf(“%d,%d”,&G.vexnum,&G.arcnum);} printf(“n依次輸入頂點向量值n”);int i;for(i=0;i //清空緩沖區 fflush(stdin);printf(“第%d個:”,i+1);scanf(“%c”,&G.vexs[i]);} //初始化鄰接矩陣 for(i=0;i int values;printf(“n輸入依附兩個頂點的邊及其權值<如，a,b,1>n”);for(i=0;i printf(“第%d條：”,i+1);//清空緩沖區 fflush(stdin);scanf(“%c,%c,%d”,&rear,&front,&values);int m,n;//定位兩頂點在vexs數組中的索引 m = LocateVex(G,rear);n = LocateVex(G,front);if(m==-1||n==-1){ printf(“輸入頂點或不在此圖中，請重新輸入！n”);i--;continue;} //賦予對應矩陣位置的權值，以及對稱弧的權值 G.arcs[m][n].adj = values;G.arcs[n][m].adj = values;} return OK;} //CreateUDG //矩陣輸出 void printArcs(MGraph G){ int i;printf(“ ”);//輸出第一行的頂點向量 for(i=0;i for(int j=0;j else printf(“ %d”,G.arcs[i][j].adj);}} printf(“ ∞”); printf(“n”);} //訪問頂點v輸出 Status printAdjVex(MGraph G,int v){ printf(“%c ”,G.vexs[v]);return OK;} //查找v頂點的第一個鄰接點 Status FirstAdjVex(MGraph G,int v){ //查找與頂點v的第一個鄰接點，找到后立即返回其索引，若找不到，則返回-1 for(int i=1;i return i;} return-1;} //查找基于v頂點的w鄰接點的下一個鄰接點 Status NextAdjVex(MGraph G,int v,int w){ //查找基于頂點v的w鄰接點的下一個鄰接點，找到之后立即返回其索引，若找不到，則返回-1 for(int i=w+1;i boolean visited[MAX_VERTEX_NUM];//函數指針變量 Status(* VisitFunc)(MGraph G,int v);//DFS,從第v個頂點出發遞歸深度優先遍歷圖G void DFS(MGraph G,int v){ visited[v] = TRUE;//訪問第v個頂點 VisitFunc(G,v);for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){if(!visited[w]) DFS(G,w);}} //深度優先遍歷 void DFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //將函數復制給全局的函數指針變量，待調用DFS時使用 VisitFunc = Visit;int v;//將訪問標記初始化為false for(v=0;v void BFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //按廣度優先非遞歸遍歷圖G，使用輔助隊列Q和訪問標志數組Visited int v;int u;//將訪問標記數組初始化為false for(v = 0;v //判斷頂點V是否被訪問 if(!visited[v]){//將第一次訪問的頂點對應的訪問標記數組位置賦值為TRUE visited[v] = TRUE;//輸出頂點v Visit(G,v);EnQueue(Q,v);while(!QueueEmpty(Q)){//按入隊序列取出頂點，便于查找此頂點的鄰接點 DeQueue(Q,u);//查找當前頂點鄰接點 for(int w=FirstAdjVex(G,u);w>=0;w = NextAdjVex(G,u,w)) if(!visited[w]){visited[w] =TRUE;Visit(G,w);EnQueue(Q,w);}}} //銷毀隊列 DestroyQueue(Q);} int main(){ printf(“====圖的創建及其應用====n”);//創建一個圖 MGraph G;CreateUDN(G);//用鄰接矩陣輸出圖 printf(“n圖的鄰接矩陣輸出如下:n”);printArcs(G);//深度優先遍歷 printf(“n深度優先遍歷序列:n”);DFSTraverse(G,printAdjVex);printf(“n”);//廣度優先遍歷 } printf(“n廣度優先遍歷序列:n”);BFSTraverse(G,printAdjVex);printf(“n”);四.運行結果： 五.實驗心得： 通過本次課程設計，對圖的概念有了一個新的認識，在學習離散數學的時候，總覺得圖是很抽象的東西，但是在學習了《數據結構與算法》這門課程之后，我慢慢地體會到了其中的奧妙，圖能夠在計算機中存在，首先要捕捉他有哪些具體化、數字化的信息，比如說權值、頂點個數等，這也就說明了想要把生活中的信息轉化到計算機中必須用數字來完整的構成一個信息庫，而圖的存在，又涉及到了頂點之間的聯系。圖分為有向圖和無向圖，而無向圖又是有向圖在權值雙向相等下的一種特例，如何能在計算機中表示一個雙向權值不同的圖，這就是一件很巧妙的事情。有了這次課程設計的經驗和教訓，我能夠很清楚的對自己定一個合適的水平。第四篇：湘潭大學 數據結構實驗5 實驗報告 源代碼 圖的應用
點擊咨詢 