C++实现图的邻接表存储和广度优先遍历实例分析

#include <stdio.h>#include <malloc.h>#define MAX_VEX 50typedef 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; }}