本文實例講述了C++實現圖的鄰接矩陣存儲和廣度、深度優先遍歷的方法。分享給大家供大家參考。具體如下：
示例：建立如圖所示的無向圖
由上圖知，該圖有5個頂點，分別為a,b,c,d,e,有6條邊.
示例輸入（按照這個格式輸入）：
5
6
abcde
0 1 1
0 2 1
0 3 1
2 3 1
2 4 1
1 4 1
輸入結束（此行不必輸入）
注：0 1 1表示該圖的第0個頂點和第1個定點有邊相連，如上圖中的a->b所示
0 2 1表示該圖的第0個頂點和第2個定點有邊相連，如上圖中的a->c所示
2 3 1表示該圖的第2個頂點和第3個定點有邊相連，如上圖中的c->d所示
實現代碼如下：
#include <stdio.h>#define MAX_GRAPH 100#define MAX_QUEUE 30typedef struct{ char vex[MAX_GRAPH]; /* 頂點 */ int edge[MAX_GRAPH][MAX_GRAPH]; /* 鄰接矩陣 */ int n; /* 當前的頂點數 */ int e; /* 當前的邊數 */}GRAPH;void Create(GRAPH *G); /* 圖的鄰接矩陣表示法 */void BFS(GRAPH *G,int k); /* 廣度優先遍歷 */ void DFS(GRAPH *G,int k); /* 深度優先遍歷 */int visited[MAX_GRAPH];int main(int argc, char *argv[]){ int i; for(i = 0 ; i < MAX_QUEUE ; ++i) visited[i] = 0; GRAPH G; Create(&G);/* BFS(&G,0);*/ DFS(&G,0); return 0;}void BFS(GRAPH *G,int k){ int queue[MAX_QUEUE]; /* 隊列 */ int front = -1,rear = -1,amount = 0; int visited[MAX_GRAPH]; /* 標記已經訪問過的元素 */ int i,j; for(i = 0 ; i < MAX_GRAPH ; ++i) visited[i] = 0; printf("訪問頂點%c/n",G->vex[k]); visited[k] = 1; rear = (rear + 1) % MAX_QUEUE; /* 入隊操作 */ queue[rear] = k; front = rear; ++amount; while(amount > 0) { i = queue[front]; /* 出隊操作 */ front = (front + 1) % MAX_QUEUE; --amount; for(j = 0 ; j < G->n ; ++j) { if(G->edge[i][j] != 0 && visited[j] == 0) { printf("訪問頂點%c/n",G->vex[j]); visited[j] = 1; rear = (rear + 1) % MAX_QUEUE; /* 入隊 */ queue[rear] = j; ++amount; } } } printf("遍歷結束/n"); }void DFS(GRAPH *G,int k){ int j; printf("訪問頂點：%c/n",G->vex[k]); visited[k] = 1; for(j = 0 ; j < G->n ; ++j) { if(G->edge[k][j] != 0 && visited[j] == 0) DFS(G,j); }}void Create(GRAPH *G){ printf("輸入頂點數：/n"); scanf("%d",&G->n); printf("輸入邊數：/n"); scanf("%d",&G->e); getchar(); int i,j,k,w; printf("請輸入端點(char型)：/n"); for(i = 0 ; i < G->n ; ++i) /* 建立表頭 */ scanf("%c",&G->vex[i]); for(i = 0 ; i < G->n ; ++i) /* 初始化鄰接矩陣 */ for(j = 0 ; j < G->n ; ++j) G->edge[i][j] = 0; printf("請輸入邊：/n"); for(k = 0 ; k < G->e ; ++k) { scanf("%d%d%d",&i,&j,&w); /* 輸入(vi,vj)上的權w */ G->edge[i][j] = w; G->edge[j][i] = w; }}希望本文所述對大家的C++程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
