欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)圖的鄰接表存儲(chǔ)和廣度優(yōu)先遍歷實(shí)例分析

 更新時(shí)間:2015年04月20日 11:42:18   作者:司青  
這篇文章主要介紹了C++實(shí)現(xiàn)圖的鄰接表存儲(chǔ)和廣度優(yōu)先遍歷,實(shí)例分析了C++實(shí)現(xiàn)圖的存儲(chǔ)與遍歷技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下

本文實(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)文章

最新評(píng)論