bfs.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/*************************************************/
/*          图的广度优先遍历算法                 */
/*  程序名bfs.c    函数名bfs()、bfstraverse()    */
/*************************************************/
#include "c_ljb.c"
int visited[m];  /*全局标志向量*/
/*---函数loc():查找结点data在图中的序号---*/
int loc(adjgraph g,datatype data)
{ int i;
  i=0;
  while (i<g.n && g.adjlist[i].vertex!=data)
       i++;
  if  (i==g.n)   return -1;  else   return i;
}

/*----从顶点i出发广度优先变量图g----*/
void bfs(adjgraph g, int i)
{ int j;
  edgenode *p;
  int queue[20], head,tail;           /*FIFO队列*/
  head=-1; tail=-1;                   /*初始化空队列*/
  printf("%c ",g.adjlist[i].vertex);                    /*访问源点v*/
  visited[i]=1;
  queue[++tail]=i;                    /*被访问结点进队*/
  while (tail>head)                   /*当队列非空时，执行下列循环体*/
     {
      j=queue[++head];                /*出队*/
      p=g.adjlist[j].firstedge;
      while (p)                       /*广度优先搜索邻接表*/
         { if (visited[p->adjvex]==0)
	       { printf("%c ",g.adjlist[p->adjvex].vertex);
                 queue[++tail]=p->adjvex;
                 visited[p->adjvex]=1;
               }
            p=p->next;
          }
     }
}
/*-----从顶点v开始广度优先遍历图g----*/
int bfstraverse(adjgraph g,datatype v)
{  int i,count=0;
   for (i=0;i<g.n;i++)
       visited[i]=0;     /*初始化标志数组*/
   i=loc(g,v);           /*寻找顶点v在邻接表中的位序*/
   if (i!=-1)
     { count++;          /*连通分量个数加1*/
       bfs(g,i);
     }
   for (i=0;i<g.n;i++)
       if (!visited[i])  /*vi未访问过*/
	   {printf("\n");
	    count++;     /*连通分量个数加1*/
	    bfs(g,i);
	   }
   return count;
 }
void main()
{ adjgraph g;
  int count;
  datatype v;
  createadjgraph(&g);
  printf("\n The graph is:\n");
  print(g);
  getchar();
  printf("请输入源点：");
  scanf("%c",&v);
  count=bfstraverse(g,v);     /*从顶点v出发广度优先遍历图g*/
  printf("\n该图共有%d个连通分量",count);
}