C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例
一、 實(shí)驗(yàn)?zāi)康?/h2>
理解圖的基本概念,掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu),實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷算法與廣度優(yōu)先搜索遍歷算法。
二、 實(shí)驗(yàn)內(nèi)容
利用鄰接矩陣描述示例圖,編寫程序輸出示例圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的遍歷序列。
具體步驟如下:
- 將圖的鄰接矩陣描述為一個(gè)二維數(shù)組,并將該數(shù)組定義為全局變量,以便數(shù)據(jù)的傳遞;
- 定義一個(gè)隊(duì)列,在廣度優(yōu)先搜索時(shí),該隊(duì)列存儲(chǔ)已被訪問(wèn)的路徑長(zhǎng)度為1,2,…的頂點(diǎn);
- 定義訪問(wèn)函數(shù)visit()、深度優(yōu)先搜索函數(shù)DFS()和廣度優(yōu)先搜索函數(shù)BFS();
- 主函數(shù)實(shí)現(xiàn)各函數(shù)的調(diào)用。
三、 實(shí)驗(yàn)工具
Dev-C++
四、 實(shí)驗(yàn)代碼
//Authors:xiaobei #include<stdio.h> #include<stdlib.h> #define MaxInt 32767 #define MVNum 100 typedef char VerTexType; typedef int ArcType; //定義圖結(jié)構(gòu) typedef struct{ VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum; }AMGraph; //定義輔助鏈隊(duì) typedef struct QNode{ char data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; //定義全局輔助數(shù)組visited[MVNum] int visited[MVNum]; //函數(shù)返回定點(diǎn)下標(biāo) int LocateVex(AMGraph G,char v){ int i; for(i=0;i<G.vexnum;i++) if(G.vexs[i]==v) return i; return -1; } //函數(shù)訪問(wèn)并輸出頂點(diǎn),返回下標(biāo) int visit(AMGraph G,char v){ int i; for(i=0;i<G.vexnum;i++) if(v==G.vexs[i]) printf("%c",v); return LocateVex(G,v); } //函數(shù)創(chuàng)建無(wú)向圖,以鄰接矩陣形式 int CreateUDN(AMGraph &G){ int i,j,k,v1,v2,w; printf("[輸入總頂點(diǎn)數(shù)和邊數(shù):]\n>>>"); scanf("%d %d",&G.vexnum,&G.arcnum); for(i=0;i<G.vexnum;i++) { getchar(); printf("[依次輸入各頂點(diǎn)的信息:]\n>>>"); scanf("%c",&G.vexs[i]); } for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) G.arcs[i][j] = MaxInt; for(k=0;k<G.arcnum;k++){ getchar(); printf("[輸入一條邊依附的頂點(diǎn)及權(quán)值:]\n>>>"); scanf("%c %c %d",&v1,&v2,&w); i = LocateVex(G,v1); j = LocateVex(G,v2); G.arcs[i][j]=w; G.arcs[j][i]=G.arcs[i][j]; } return 1; } //函數(shù)深度遍歷連通圖 void DFS_AM(AMGraph G,char v){ int w,u; u = visit(G,v); visited[u] = 1; for(w=0;w<G.vexnum;w++){ if((G.arcs[u][w]<MaxInt) && (!visited[w])) DFS_AM(G,G.vexs[w]); } } //函數(shù)初始化鏈隊(duì) void InitQueue(LinkQueue &Q){ Q.front = Q.rear = (QNode*)malloc(sizeof(QNode)); Q.front->next=NULL; } //函數(shù)數(shù)據(jù)進(jìn)隊(duì) void EnQueue(LinkQueue &Q,char e){ QueuePtr p; p = (QNode*)malloc(sizeof(QNode)); p->data = e; p->next = NULL; Q.rear->next=p; Q.rear = p; } //函數(shù)數(shù)據(jù)出隊(duì) void DeQueue(LinkQueue &Q,char &e){ QueuePtr p; if(Q.front==Q.rear); else { p = Q.front->next; e = p->data; Q.front->next = p->next; if(Q.rear==p) Q.rear=Q.front; free(p); } } //函數(shù)判斷鏈隊(duì)是否為空 int QueueEmpty(LinkQueue Q){ if(Q.front==Q.rear) return 1; else return 0; } //函數(shù)返回頂點(diǎn)下一個(gè)鄰接點(diǎn)下標(biāo) int FirstAdjVex(AMGraph G,int c){ int j; for(j=0;j<G.vexnum;j++) if(G.arcs[c][j]<MaxInt && visited[j]==0) return j; return -1; } //函數(shù)返回頂點(diǎn)下一個(gè)相對(duì)鄰接點(diǎn)下標(biāo) int NextAdjVex(AMGraph G,int c,int w){ int j; for(j=0;j<G.vexnum;j++) if(G.arcs[c][j]<MaxInt && visited[j]==0) return j; return -1; } //函數(shù)廣度遍歷連通圖 void BFS_AM(AMGraph G,char v){ int c,w,i; char u; LinkQueue Q; c = visit(G,v); visited[c] = 1; InitQueue(Q); EnQueue(Q,v); while(!QueueEmpty(Q)){ DeQueue(Q,u); c = LocateVex(G,u); for(w=FirstAdjVex(G,c);w>=0;w=NextAdjVex(G,c,w)) { if(!visited[w]){ i = visit(G,G.vexs[w]); visited[i] = 1; EnQueue(Q,G.vexs[w]); } } } } //菜單打印 void Menu(){ printf("\n————————菜單————————\n"); printf("\n1.創(chuàng)建圖結(jié)構(gòu);\n"); printf("\n2.深度遍歷(DFS);\n"); printf("\n3.廣度遍歷(BFS);\n"); printf("\n0.退出;\n"); printf("\n——————————————————\n"); printf("[請(qǐng)輸入你的選擇:]\n>>>"); } //主函數(shù) int main(){ int i,user; char v; AMGraph G; while(1){ Menu(); scanf("%d",&user); switch(user){ case 1:{ CreateUDN(G); break; } case 2:{ //初始化輔助數(shù)組 for(i=0;i<G.vexnum;i++) visited[i] = 0; printf("[請(qǐng)輸入遍歷開始的頂點(diǎn):]\n>>>"); getchar(); scanf("%c",&v); DFS_AM(G,v); break; } case 3:{ //初始化輔助數(shù)組 for(i=0;i<G.vexnum;i++) visited[i] = 0; printf("[請(qǐng)輸入遍歷開始的頂點(diǎn):]\n>>>"); getchar(); scanf("%c",&v); BFS_AM(G,v); break; } case 0:{ exit(0); break; } } } return 0; }
五、 實(shí)驗(yàn)結(jié)果
六、總結(jié)與思考
- 無(wú)向圖的鄰接矩陣是對(duì)稱的,有向圖鄰接矩陣可能不對(duì)稱。
- 深度優(yōu)先搜索類似于棧結(jié)構(gòu)的出棧于入棧過(guò)程,模擬遞歸,其實(shí)遞歸也是通過(guò)堆棧的形式實(shí)現(xiàn)的。
- 廣度遍歷是非遞歸過(guò)程,借助隊(duì)列來(lái)實(shí)現(xiàn)。
- 輔助數(shù)組需要在全局使用,在主函數(shù)外定義。
- DFS與BFS空間復(fù)雜度都是O(n),鄰接矩陣時(shí)間復(fù)雜度都是O(n2),鄰接表時(shí)間復(fù)雜度為O(n+e)。
鄰接矩陣示意圖:
以上就是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例的詳細(xì)內(nèi)容,更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建遍歷的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
- C語(yǔ)言深入刨析數(shù)據(jù)結(jié)構(gòu)之棧與鏈棧的設(shè)計(jì)與應(yīng)用
- C語(yǔ)言超詳細(xì)講解數(shù)據(jù)結(jié)構(gòu)中的線性表
- C語(yǔ)言算法積累圖的遍歷鄰接表簡(jiǎn)單路徑
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之圖的遍歷(二)
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之圖的遍歷(一)
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之算法的時(shí)間復(fù)雜度
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)詳細(xì)解析二叉樹的操作
相關(guān)文章
C++數(shù)據(jù)結(jié)構(gòu)之list詳解
list是一種序列式容器。list容器完成的功能實(shí)際上和數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表是極其相似的,list中的數(shù)據(jù)元素是通過(guò)鏈表指針串連成邏輯意義上的線性表,也就是list也具有鏈表的主要優(yōu)點(diǎn),即:在鏈表的任一位置進(jìn)行元素的插入、刪除操作都是快速的2021-11-11C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單通訊錄管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單通訊錄管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-07-07C++實(shí)現(xiàn)LeetCode(76.最小窗口子串)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(76.最小窗口子串),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C++ vector模擬實(shí)現(xiàn)的代碼詳解
vector是表示可變大小數(shù)組的序列容器,就像數(shù)組一樣,vector也采用的連續(xù)存儲(chǔ)空間來(lái)存儲(chǔ)元素,本質(zhì)講,vector使用動(dòng)態(tài)分配數(shù)組來(lái)存儲(chǔ)它的元素,本文將給大家詳細(xì)介紹一下C++ vector模擬實(shí)現(xiàn),需要的朋友可以參考下2023-07-07C++構(gòu)造函數(shù)的類型,淺拷貝與深拷貝詳解
這篇文章主要為大家詳細(xì)介紹了C++構(gòu)造函數(shù)的類型,淺拷貝與深拷貝,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助2022-03-03C++中?‘=default?’及‘?=delete?’的使用
這篇文章主要介紹了C++中?=default?及?=delete?使用,使用=default和=delete可以控制編譯器默認(rèn)函數(shù)體的使用,下面我們就來(lái)看看具體的室友方法吧,需要的朋友也可以參考一下2021-12-12C語(yǔ)言實(shí)現(xiàn)通訊錄管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)通訊錄管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-01-01C語(yǔ)言詳細(xì)講解if語(yǔ)句與switch語(yǔ)句的用法
用 if 語(yǔ)句可以構(gòu)成分支結(jié)構(gòu),它根據(jù)給的條件進(jìn)行判定,以決定執(zhí)行哪個(gè)分支程序段,C 語(yǔ)言中還有另外一種分支語(yǔ)句,就是 switch 語(yǔ)句2022-05-05