C++完成圖的鄰接矩陣存儲和廣度、深度優先遍歷實例剖析。本站提示廣大學習愛好者:(C++完成圖的鄰接矩陣存儲和廣度、深度優先遍歷實例剖析)文章只能為提供參考,不一定能成為您想要的結果。以下是C++完成圖的鄰接矩陣存儲和廣度、深度優先遍歷實例剖析正文
本文實例講述了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 30 typedef 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++法式設計有所贊助。