广度优先搜索.c

广度优先搜索 c语言实现

 /* 广度优先搜索
    武汉科技大学 
   崔恒*/
#include <stdio.h>
#define m 20       /*预定义图的最大顶点数*/
typedef char datatype; /*顶点信息数据类型*/
typedef struct node{   /*边表结点*/
  int adjvex;       /*邻接点*/
  struct node *next; 
}edgenode;

typedef struct vnode{ /*头结点类型*/
  datatype vertex;   /*顶点信息*/
  edgenode *firstedge;/*邻接链表头指针*/
}vertexnode;

typedef struct{       /*邻接表类型*/
vertexnode adjlist [m]; /*存放头结点的顺序表*/
int n,e;           /*图的顶点数与边数*/
}adjgraph;
/*------建立无向图的邻接表算法-------*/
void createadjgraph(adjgraph *g)
  { int i,j,k;     
    edgenode *s;
    printf("Please input n and e:\n");
    scanf("%d%d",&g->n,&g->e);         /*输入顶点数与边数*/
    getchar();                     /*取消回车符*/
    printf("Please input %d vertex:",g->n);
    for(i=0;i<g->n;i++)
    {
     scanf("%c",&g->adjlist[i].vertex);   /*读入顶点信息*/
     g->adjlist[i].firstedge=NULL;       /*边表置为空表*/
    }
    printf("Please input %d edges:",g->e);
    for(k=0;k<g->e;k++)               /*循环e次建立边表*/
    {
      scanf("%d%d",&i,&j);           /*输入无序对（i,j）*/
      s=(edgenode *)malloc(sizeof(edgenode));
      s->adjvex=j;                 /*邻接点序号为j*/
      s->next=g->adjlist[i].firstedge;
      g->adjlist[i].firstedge=s;       /*将新结点*s插入顶点vi的边表头部*/
      s=(edgenode *)malloc(sizeof(edgenode));
      s->adjvex=i;                 /*邻接点序号为i*/
      s->next=g->adjlist[j].firstedge;
      g->adjlist[j].firstedge=s;       /*将新结点*s插入顶点vj的边表头部*/
    }
  }
/*---函数print():输入邻接表存储结构---*/
void print(adjgraph g){
     edgenode *p;
int i;
for (i=0;i<g.n;i++){
      printf("%c ",g.adjlist[i].vertex);
  p=g.adjlist[i].firstedge;
  while (p){
            printf("%d-->",p->adjvex);
    p=p->next;
    }
  printf("\n");
  }
}
main(){
     adjgraph g;
createadjgraph(&g);
print(g);
}