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++程序设计有所帮助。