C++完成圖的鄰接表存儲和廣度優先遍歷實例剖析

C++完成圖的鄰接表存儲和廣度優先遍歷實例剖析。本站提示廣大學習愛好者：（C++完成圖的鄰接表存儲和廣度優先遍歷實例剖析）文章只能為提供參考，不一定能成為您想要的結果。以下是C++完成圖的鄰接表存儲和廣度優先遍歷實例剖析正文

本文實例講述了C++完成圖的鄰接表存儲和廣度優先遍歷辦法。分享給年夜家供年夜家參考。詳細以下：

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

由上圖知，該圖有5個極點，分離為a,b,c,d,e,有6條邊.

示例輸出（依照這個格局輸出）：

5
6
abcde
0 1
0 2
0 3
2 3
2 4
1 4

輸出停止（此行不用輸出）

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

完成代碼以下：

#include <stdio.h>
#include <malloc.h>
#define MAX_VEX 50
typedef struct NODE
{
 int ix; /* 極點的索引 */
 struct NODE *next; /* 下一個表結點 */
}EdgeNode; /* 表結點 */
typedef struct
{
 char vex;
 EdgeNode *first; /* 第一個表結點 */
}Vertex; /* 表頭結點 */
typedef struct
{
 Vertex vex[MAX_VEX];
 int n,e;
}GRAPH;
void Create(GRAPH *G);
void BFS(GRAPH *G,int k); /* 廣度優先遍歷 */
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]; /* 輪回隊列 */
 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("拜訪極點:%c\n",G->vex[k].vex);
 visited[k] = 1;
 rear = (rear + 1) % MAX_VEX; /* 入隊 */
 front = 0;
 queue[rear] = k;
 ++amount;
 
 while(amount > 0)
 {
  i = queue[front]; /* 出隊 */
  front = (front + 1) % MAX_VEX;
  --amount;
  p = G->vex[i].first;
  
  while(p)
  {
   if(visited[p->ix] == 0)
   {
    printf("拜訪極點:%c\n",G->vex[p->ix].vex);
    visited[p->ix] = 1;
    rear = (rear + 1) % MAX_VEX; /* 入隊 */
    queue[rear] = p->ix;
    ++amount;
   }
   p = p->next;
  }
  
 }
}
void Create(GRAPH *G)
{
 printf("輸出極點數：\n");
 scanf("%d",&G->n);
 printf("輸出邊數：\n");
 scanf("%d",&G->e);
 getchar();
 EdgeNode *p;
 
 int i,j,k;
 for(i = 0 ; i < G->n ; ++i) /* 樹立極點表 */
 {
  scanf("%c",&G->vex[i].vex);
  G->vex[i].first = NULL;
 }
 
 for(k = 0 ; k < G->e ; ++k) /* 樹立邊表 */
 {/* 相似於頭插法創立鏈表 */
  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;
 }
}

願望本文所述對年夜家的C++法式設計有所贊助。