tgdbl.c

对于一个给定的任意边数和顶点值的有向图或无向图

#define NULL 0
#define MAXQSIZE 100
#define MAX_VERTEX_NUM 50
#include "stdio.h"
typedef struct{int *base;
               int front;
               int rear;}sqqueue;
typedef struct arcnode{int adjvex;
                       struct arcnode *nextarc;}arcnode;
typedef struct vexnode{int vexdata;
                       arcnode *firstarc;
 int tag;}vexnode;
vexnode adjlist[MAX_VERTEX_NUM];
int vexnum,arcnum;
sqqueue q;
sqqueue  initqueue()/*初始化队列函数*/
     { q.base=(int *)malloc(MAXQSIZE*sizeof(int));
       if(!q.base)
	printf("OVERFLOW\n");
       q.front=q.rear=0;
       return q;}
void enqueue(int x)/*入队列函数*/
        { if ((q.rear+1)%MAXQSIZE==q.front)
            printf("ERROR\n");
	  q.base[q.rear]=x;
	  q.rear=(q.rear+1)%MAXQSIZE;}
int dequeue()/*出队列函数*/
      {  int x;
	 if (q.front==q.rear)
	    printf("ERROR\n");
	 x=q.base[q.front];
	  q.front=(q.front+1)%MAXQSIZE;
	return x;}
void creatadjlist()/*利用邻接表生成图函数*/
{arcnode *ptr,*p;
 int vexnum,arcnum,k,v1,v2,i;
 printf("\nplease input dingdianshu and bianshu:\n");/*请求输入图中顶点数和边数*/
 scanf("%d,%d",&vexnum,&arcnum);
 for(k=1;k<=vexnum;k++)
  {adjlist[k].vexdata=k;
   adjlist[k].firstarc=NULL;}
for(k=1;k<=arcnum;k++)
 {printf("\nplease input dingdiandui:\n");/*请求输入图中各顶点对*/
  scanf("%d,%d",&v1,&v2);
  ptr=(arcnode *)malloc(sizeof(arcnode));
  ptr->nextarc=adjlist[v1].firstarc;
  ptr->adjvex=v2;
  adjlist[v1].firstarc=ptr;}
 for(i=1;i<=vexnum;i++)/*输出邻接表中各顶点*/
  {p=adjlist[i].firstarc;
   printf("\n%5d:",adjlist[i].vexdata);
   for(;p!=NULL;p=p->nextarc)
     printf("%5d",p->adjvex);
   printf("\n");}}
void bfs(int v)/*图的广度优先遍历函数*/
{int v1,w;arcnode *ptr;
 printf("%5d",v);
 adjlist[v].tag=1;
 enqueue(v);
 while(q.front!=q.rear)
  {    v1=dequeue();
  ptr=adjlist[v1].firstarc;
   while(ptr!=NULL)
   {w=ptr->adjvex;
    ptr=ptr->nextarc;
    if(adjlist[w].tag==0)
    {printf("%5d",w);
     adjlist[w].tag=1;
      enqueue(w);  }}}}
main()/*主函数*/
{int v;
  q=initqueue();/*调用初始化队列函数*/
  creatadjlist();/*调用利用邻接表生成图函数*/
 printf("\nplease input the first data:\n");/*请求输入广度优先遍历的起始出发点*/
scanf("%d",&v);
 bfs(v);/*调用图的广度优先遍历函数*/
 }