C++實(shí)現(xiàn)圖的鄰接表存儲(chǔ)和廣度優(yōu)先遍歷實(shí)例分析
本文實(shí)例講述了C++實(shí)現(xiàn)圖的鄰接表存儲(chǔ)和廣度優(yōu)先遍歷方法。分享給大家供大家參考。具體如下:
示例:建立如圖所示的無(wú)向圖
由上圖知,該圖有5個(gè)頂點(diǎn),分別為a,b,c,d,e,有6條邊.
示例輸入(按照這個(gè)格式輸入):
5
6
abcde
0 1
0 2
0 3
2 3
2 4
1 4
輸入結(jié)束(此行不必輸入)
注:0 1表示該圖的第0個(gè)頂點(diǎn)和第1個(gè)定點(diǎn)有邊相連,如上圖中的a->b所示
0 2表示該圖的第0個(gè)頂點(diǎn)和第2個(gè)定點(diǎn)有邊相連,如上圖中的a->c所示
2 3表示該圖的第2個(gè)頂點(diǎn)和第3個(gè)定點(diǎn)有邊相連,如上圖中的c->d所示
實(shí)現(xiàn)代碼如下:
#include <stdio.h> #include <malloc.h> #define MAX_VEX 50 typedef struct NODE { int ix; /* 頂點(diǎn)的索引 */ struct NODE *next; /* 下一個(gè)表結(jié)點(diǎn) */ }EdgeNode; /* 表結(jié)點(diǎn) */ typedef struct { char vex; EdgeNode *first; /* 第一個(gè)表結(jié)點(diǎn) */ }Vertex; /* 表頭結(jié)點(diǎn) */ typedef struct { Vertex vex[MAX_VEX]; int n,e; }GRAPH; void Create(GRAPH *G); void BFS(GRAPH *G,int k); /* 廣度優(yōu)先遍歷 */ int main(int argc, char *argv[]) { GRAPH G; Create(&G); BFS(&G,0); return 0; } void BFS(GRAPH *G,int k) { EdgeNode *p; int queue[MAX_VEX]; /* 循環(huán)隊(duì)列 */ int front = -1,rear = -1,amount = 0; int visited[MAX_VEX]; int i,j; for(i = 0 ; i < MAX_VEX ; ++i) visited[i] = 0; printf("訪問(wèn)頂點(diǎn):%c\n",G->vex[k].vex); visited[k] = 1; rear = (rear + 1) % MAX_VEX; /* 入隊(duì) */ front = 0; queue[rear] = k; ++amount; while(amount > 0) { i = queue[front]; /* 出隊(duì) */ front = (front + 1) % MAX_VEX; --amount; p = G->vex[i].first; while(p) { if(visited[p->ix] == 0) { printf("訪問(wèn)頂點(diǎn):%c\n",G->vex[p->ix].vex); visited[p->ix] = 1; rear = (rear + 1) % MAX_VEX; /* 入隊(duì) */ queue[rear] = p->ix; ++amount; } p = p->next; } } } void Create(GRAPH *G) { printf("輸入頂點(diǎn)數(shù):\n"); scanf("%d",&G->n); printf("輸入邊數(shù):\n"); scanf("%d",&G->e); getchar(); EdgeNode *p; int i,j,k; for(i = 0 ; i < G->n ; ++i) /* 建立頂點(diǎn)表 */ { scanf("%c",&G->vex[i].vex); G->vex[i].first = NULL; } for(k = 0 ; k < G->e ; ++k) /* 建立邊表 */ {/* 類似于頭插法創(chuàng)建鏈表 */ scanf("%d%d",&i,&j); p = (EdgeNode*)malloc(sizeof(EdgeNode)); p->next = G->vex[i].first; p->ix = j; G->vex[i].first = p; p = (EdgeNode*)malloc(sizeof(EdgeNode)); p->next = G->vex[j].first; p->ix = i; G->vex[j].first = p; } }
希望本文所述對(duì)大家的C++程序設(shè)計(jì)有所幫助。
相關(guān)文章
Qt數(shù)據(jù)庫(kù)應(yīng)用之實(shí)現(xiàn)數(shù)據(jù)分組導(dǎo)出
這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)數(shù)據(jù)庫(kù)數(shù)據(jù)分組導(dǎo)出,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)或工作有一定參考價(jià)值,需要的可以了解一下2022-06-06C語(yǔ)言實(shí)現(xiàn)3*3數(shù)組對(duì)角線之和示例
今天小編就為大家分享一篇C語(yǔ)言實(shí)現(xiàn)3*3數(shù)組對(duì)角線之和示例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-12-12DSP中浮點(diǎn)轉(zhuǎn)定點(diǎn)運(yùn)算--舉例及編程中的心得
本文主要講解DSP浮點(diǎn)轉(zhuǎn)定點(diǎn)運(yùn)算舉例及編程中的心得 ,具有參考價(jià)值,需要的朋友可以參考一下。2016-06-06Matlab實(shí)現(xiàn)灰色預(yù)測(cè)的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何利用Matlab實(shí)現(xiàn)灰色預(yù)測(cè),文中的示例代碼講解詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴可以了解一下2022-05-05C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之 折半查找實(shí)例詳解
這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之 折半查找實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06C語(yǔ)言字符串轉(zhuǎn)換為Python字符串的方法
這篇文章主要介紹了C語(yǔ)言字符串轉(zhuǎn)換為Python字符串的方法,文中講解非常細(xì)致,代碼幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下2020-07-07C語(yǔ)言實(shí)現(xiàn)將彩色bmp圖像轉(zhuǎn)化為灰圖、灰度圖像反色
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)將彩色bmp圖像轉(zhuǎn)化為灰圖、灰度圖像反色,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-10-10C++入門(命名空間,缺省參數(shù),函數(shù)重載,引用,內(nèi)聯(lián)函數(shù),auto,范圍for)
這篇文章主要介紹了C++入門(命名空間,缺省參數(shù),函數(shù)重載,引用,內(nèi)聯(lián)函數(shù),auto,范圍for),這些基礎(chǔ)知識(shí)是學(xué)習(xí)C++最最基礎(chǔ)需要掌握的知識(shí)點(diǎn),需要的朋友可以參考下2021-05-05