C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之圖的遍歷實(shí)例詳解
成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括洛浦網(wǎng)站建設(shè)、洛浦網(wǎng)站制作、洛浦網(wǎng)頁(yè)制作以及洛浦網(wǎng)絡(luò)營(yíng)銷策劃等。多年來,我們專注于互聯(lián)網(wǎng)行業(yè),利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等,向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案,洛浦網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前,我們服務(wù)的客戶以成都為中心已經(jīng)輻射到洛浦省份的部分城市,未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任!
輸入一組頂點(diǎn),建立無(wú)向圖的鄰接矩陣。輸入一組頂點(diǎn),建立有向圖的鄰接表。分別對(duì)無(wú)向圖和有向圖進(jìn)行DFS(深度優(yōu)先遍歷)和BFS(廣度優(yōu)先遍歷)。寫出深度優(yōu)先遍歷的遞歸和非遞歸算法。根據(jù)建立的有向圖,判斷該圖是否是有向無(wú)環(huán)圖,若是,則輸出其一種拓?fù)溆行蛐蛄小?/p>
實(shí)現(xiàn)代碼:
#include <stdio.h> #include <stdlib.h> #define MAX 20 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct{ char data; ArcNode *firstarc; }AdjList[MAX]; typedef struct{ AdjList vertices; int vexnum; int arcnum; }ALGraph; typedef struct{ int *base; int front,rear; }CqQueue; void InitQueue(CqQueue &Q) {//初始化一個(gè)隊(duì)列 Q.base=(int*)malloc(MAX*sizeof(int)); Q.front=Q.rear=0; } int QueueEmpty(CqQueue Q) {//判斷隊(duì)列是否為空 if(Q.rear==Q.front) return 1; return 0; } void EnQueue(CqQueue &Q,int e) {//入隊(duì)操作 if((Q.rear+1)%MAX==Q.front) return; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAX; } void DeQueue(CqQueue &Q,int &e) {//出隊(duì)操作 if(Q.rear==Q.front) return; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAX; } int LocateVex(ALGraph G,char v) {//查找頂點(diǎn)v在圖G中的位置 for(int i=0;i<G.vexnum;i++) if(G.vertices[i].data==v) return i; return -1; for(int i=0;i<G.vexnum;i++) if(G.vexs[i]==v) return i; return -1; } void CreateAdjList(ALGraph &G) {//建立無(wú)向圖的鄰接表 int v,i,j,k; char v1,v2; ArcNode *p,*s; printf("輸入無(wú)向圖的頂點(diǎn)數(shù)和邊數(shù):\n"); scanf("%d%d",&G.vexnum,&G.arcnum); getchar(); printf("輸入圖的頂點(diǎn)信息:\n"); for(v=0;v<G.vexnum;v++){ scanf("%c",&G.vertices[v].data);getchar(); G.vertices[v].firstarc=NULL; } printf("輸入無(wú)向圖的邊:\n"); for(k=0;k<G.vexnum;k++){ scanf("%c%c",&v1,&v2); getchar(); i=LocateVex(G,v1); j=LocateVex(G,v2); s=(ArcNode*)malloc(sizeof(ArcNode)); s->adjvex=j; s->nextarc=NULL; if(!G.vertices[i].firstarc) G.vertices[i].firstarc=s; else{ p=G.vertices[i].firstarc; while(p->nextarc) p=p->nextarc; p->nextarc=s; } s=(ArcNode*)malloc(sizeof(ArcNode)); s->adjvex=i; s->nextarc=NULL; if(!G.vertices[j].firstarc) G.vertices[j].firstarc=s; else{ p=G.vertices[j].firstarc; while(p->nextarc) p=p->nextarc; p->nextarc=s; } } } int visited[MAX]; void DFS(ALGraph G,int v) {//從頂點(diǎn)v開始對(duì)圖G進(jìn)行深度優(yōu)先搜索 ArcNode *p; printf("%3c",G.vertices[v].data); visited[v]=1; for(p=G.vertices[v].firstarc;p;p=p->nextarc) if(!visited[p->adjvex]) DFS(G,p->adjvex); } void DFSTraverse(ALGraph G) {//對(duì)用鄰接表存儲(chǔ)的無(wú)向圖G進(jìn)行深度優(yōu)先遍歷 int v; for(v=0;v<G.vexnum;v++) visited[v]=0; for(v=0;v<G.vexnum;v++) if(!visited[v]) DFS(G,v); } void BFSTraverse(ALGraph G) {//對(duì)用鄰接表存儲(chǔ)的無(wú)向圖G進(jìn)行深度優(yōu)先遍歷 int u,v; CqQueue Q; ArcNode *p; for(v=0;v<G.vexnum;v++) visited[v]=0; InitQueue(Q); for(v=0;v<G.vexnum;v++) if(!visited[v]){ printf("%3c",G.vertices[v].data); visited[v]=1; EnQueue(Q,v); while(!QueueEmpty(Q)){ DeQueue(Q,u); for(p=G.vertices[u].firstarc;p;p=p->nextarc) if(!visited[p->adjvex]){ printf("%3c",G.vertices[p->adjvex].data); visited[p->adjvex]=1; EnQueue(Q,p->adjvex); } } } } int main(){ ALGraph G; printf("建立無(wú)向圖的鄰接表:\n"); CreateAdjList(G); printf("無(wú)向圖的深度優(yōu)先遍歷序列如下:\n"); DFSTraverse(G); printf("\n\n無(wú)向圖的廣度優(yōu)先遍歷序列如下:\n"); BFSTraverse(G); printf("\n"); return 0; }
感謝閱讀,希望能幫助到大家,謝謝大家對(duì)本站的支持!
分享題目:C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之圖的遍歷實(shí)例詳解
標(biāo)題網(wǎng)址:http://muchs.cn/article6/ihdjig.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供手機(jī)網(wǎng)站建設(shè)、面包屑導(dǎo)航、網(wǎng)站維護(hù)、網(wǎng)站營(yíng)銷、企業(yè)建站、電子商務(wù)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)