C++實現(xiàn)圖的鄰接矩陣存儲和廣度、深度優(yōu)先遍歷實例分析

更新時間：2015年04月20日 11:35:18 作者：司青

這篇文章主要介紹了C++實現(xiàn)圖的鄰接矩陣存儲和廣度、深度優(yōu)先遍歷,實例分析了C++實現(xiàn)圖的遍歷技巧,非常具有實用價值,需要的朋友可以參考下

本文實例講述了C++實現(xiàn)圖的鄰接矩陣存儲和廣度、深度優(yōu)先遍歷的方法。分享給大家供大家參考。具體如下：

示例：建立如圖所示的無向圖

由上圖知，該圖有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

輸入結(jié)束（此行不必輸入）

注：0 1 1表示該圖的第0個頂點和第1個定點有邊相連，如上圖中的a->b所示
0 2 1表示該圖的第0個頂點和第2個定點有邊相連，如上圖中的a->c所示
2 3 1表示該圖的第2個頂點和第3個定點有邊相連，如上圖中的c->d所示

實現(xiàn)代碼如下：

#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; /* 當前的頂點數(shù) */
 int e; /* 當前的邊數(shù) */
}GRAPH;
void Create(GRAPH *G); /* 圖的鄰接矩陣表示法 */
void BFS(GRAPH *G,int k); /* 廣度優(yōu)先遍歷 */ 
void DFS(GRAPH *G,int k); /* 深度優(yōu)先遍歷 */
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]; /* 標記已經(jīng)訪問過的元素 */
 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("遍歷結(jié)束\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("輸入頂點數(shù)：\n");
 scanf("%d",&G->n);
 printf("輸入邊數(shù)：\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)上的權(quán)w */
  G->edge[i][j] = w;
  G->edge[j][i] = w;
 }
}

希望本文所述對大家的C++程序設(shè)計有所幫助。

您可能感興趣的文章: