习题1-连通图上实现广度优先遍历.c

数据结构各章实验源代码； 数据结构实验源代码

#include  "datastru.h"
#include  <stdio.h>
#include  <malloc.h>

ADJGRAPH creat_adjgraph(){
EDGENODE  *p;
int  i, s, d;
ADJGRAPH  adjg;

adjg.kind = 2;
printf("\n\n输入顶点数和边数(用逗号隔开) : ");
scanf("%d,%d", &s, &d);fflush(stdin);
adjg.vexnum = s;                              /*存放顶点数在adjg.vexnum中 */
adjg.arcnum = d;                              /*存放边点数在adjg.arcnum中*/
printf("\n\n");
for(i = 0; i < adjg.vexnum; i++)
  {printf("输入顶点 %d 的值 : ", i + 1);
   scanf("%d", &adjg.adjlist[i].vertex);      /*输入顶点的值*/
   fflush(stdin);
   adjg.adjlist[i].link = NULL;}
printf("\n\n");
for(i = 0; i < adjg.arcnum; i++)
  {printf("输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): ", i + 1);
   scanf("%d,%d", &s, &d);             /*输入边的起始顶点和终止顶点*/
   fflush(stdin);
   while(s < 1 || s > adjg.vexnum || d < 1 || d > adjg.vexnum)
      { printf("输入错，重新输入: ");
        scanf("%d,%d", &s, &d);	}
   s --;
   d --;
   p = malloc(sizeof(EDGENODE));       /*建立一个和边相关的结点*/
   p->adjvex = d;
   p->next = adjg.adjlist[s].link;     /*挂到对应的单链表上*/
   adjg.adjlist[s].link = p;
   p = malloc(sizeof(EDGENODE));       /*建立另一个和边相关的结点*/
   p->adjvex = s;
   p->next = adjg.adjlist[d].link;     /*挂到对应的单链表上*/
   adjg.adjlist[d].link = p;}
return adjg;
}

void initlinkqueue(LINKQUEUE *q)
{/*初始化广度遍历中用到的链队列*/
	q->front = malloc(sizeof(LINKQLIST));
	(q->front)->next = NULL;
	q->rear = q->front;
}

int emptylinkqueue(LINKQUEUE *q)
{/*判队列是否为空？*/
	int v;
	if(q->front == q->rear)
		v = 1;
	else
		v = 0;
	return v;
}


void enlinkqueue(LINKQUEUE *q, DATATYPE1 x)
{/*元素x入队列*/
	(q->rear)->next = malloc(sizeof(LINKQLIST));
	q->rear = (q->rear)->next;
	(q->rear)->data = x;
	(q->rear)->next = NULL;
}

DATATYPE1 dellinkqueue(LINKQUEUE *q)
{/*删除队头元素*/
	LINKQLIST *p;
	DATATYPE1 v;
	if(emptylinkqueue(q))   {printf("队列空.\n");	v = 0;}
	else
	   {p = (q->front)->next;
		(q->front)->next = p->next;
		if(p->next == NULL)  q->rear = q->front;
		v = p->data;
		free(p);}
	return v;
}

void bfs(ADJGRAPH adjg, int vi)
{/*连通图的广度遍历算法：从vi顶点出发*/
int visited[MAXLEN];
int i, v;
EDGENODE *p;
LINKQUEUE  que, *q;

q = &que;
initlinkqueue(q);
for(i = 0; i < adjg.vexnum; i++)
   visited[i] = 0;                          /*visited数组初始化，均置0*/
visited[vi-1] = 1;                          /*从编号为vi的顶点出发，visited数组对应置1*/
printf("  %d", adjg.adjlist[vi-1].vertex);  /*输出vi顶点*/
enlinkqueue(q,vi);                          /*vi顶点入队列*/
while(!emptylinkqueue(q))                   /*队列不空，继续进行遍历*/
  {v = dellinkqueue(q);                     /*取队头元素放入v变量中*/
   v --;
   p = adjg.adjlist[v].link;
   while(p != NULL)                         /*对应单链表不空，进行广度遍历*/
      {if(visited[p->adjvex] == 0)
          {visited[p->adjvex] = 1;
	       printf("  %d", adjg.adjlist[p->adjvex].vertex);
	       enlinkqueue(q, (p->adjvex)+1);}  /*遍历到的结点编号入队列*/
       p = p->next;}
  }
}

main()
{
	ADJGRAPH ag;
	int  j;

  printf("\n连通图的广度遍历\n");
  ag = creat_adjgraph();         /*建立连通图的邻接链表结构*/
  printf("\n\n输入深度遍历起始顶点(1 -- %d) : ",ag.vexnum);
  scanf("%d",&j);
  printf("\n\n广度遍历结果序列 :  ");
  bfs(ag,j);                     /*连通图的广度遍历算法*/
  printf("\n\n");
}