//广度优先搜索算法_基于邻接表
//procedure BFS（G：带顶点v1，...vn的连通图）
//T：=只包含顶点v1的树
//L:=空表
//把v1放入尚未处理顶点的表L中
//------------------------------------//
//while L非空
//begin
//  删除L中第一个顶点v
//  for v的每个邻居w
//    if w既不在L中也不在T中 then
//     begin
//    加入w到表L的末尾
//    加入w和边｛v，w｝到T
//     end
//end

#include <iostream.h>  
  
//012345分别表示v0 v1......  
  int v;//////点数目  
  int edge;///边数目  
  int j=0;
  int Lleft=0,Lright=0;//队列头和尾



typedef class ING* pING;
  class ING
  {
  private:
    int var;
    pING link;
    ING(){}
  public:
    ING(int a){var=a;link=NULL;}
    pING backlink(){return link;}
    int backvar(){return var;}
    friend void add(pING,pING);
    friend void show(pING);
  };
void add(pING head,pING temp)
{ 
  while(head->link)head=head->link;
  head->link=temp;
}
void show(pING out)
{
  while(out)
  {
    cout<<out->var<<"  ";
    out=out->link;
  }
}

  
pING* draw();//绘图  
void BFS(pING*a,int head,int *T,int *L);//深度优先搜索
int no_T(int num,int *T);//判断是否访问过了
int no_L(int num,int *L);//判断是否在队列中

int main(int argc, char const *argv[])  
{  

  pING*a=draw();//指针变量的引用  
  int *T=new int[v];//访问ok
  int *L=new int[v];//队列
//------------------------------------------------------------------------//  
for (int i = 0; i < v; ++i)//v个访问始点
{
  j=0;
  Lleft=0;////记得重新设置
  Lright=0;//队列头和尾  
  BFS(a,i,T,L);
  cout<<endl;
}

  delete []a;
  delete []T;
  delete []L;
  return 0;  
}  
pING* draw()//绘图  
{  
  int i;  
  cin>>v>>edge;///输入点数目和边数目 

  pING *a=new pING[v];
  for ( i = 0; i < v; ++i)  
    a[i]=NULL;  
  
  int spot1,spot2;  
  for ( i = 0; i < edge; ++i)  
  {  
    cin>>spot1>>spot2;  
    pING temp=new ING(spot2);
    if (a[spot1]==NULL)
        a[spot1]=temp;
    else add(a[spot1],temp);

   pING temp2=new ING(spot1);
    if (a[spot2]==NULL)
        a[spot2]=temp2;
    else add(a[spot2],temp2);
  }  
///-------------------------------------------------------------///  
    for ( i = 0; i < v; ++i) {  
      show(a[i]); cout<<"\n";  
    }  
  return a;  
}  

void BFS(pING*a,int head,int *T,int *L)
{
   cout<<head<<" ";//始点
   T[j++]=head;////////////这两句相当于:T：=只包含顶点v1的树

   L[Lright++]=head;//相当于:把v1放入尚未处理顶点的表L中

   while(Lleft != Lright)
   {
     int chu=L[Lleft++];
     pING go=a[chu];
        while(go)
        {
          int i=go->backvar();
          if(no_T(i,T) && no_L(i,L))// w既不在L中也不在T中
           {
            cout<<i<<" ";//加入树中
            L[Lright++]=i;//入队列
            T[j++]=i;//加入树表
           }
          go=go->backlink();
         }
   }
}

int no_T(int num,int *T)
{
   for (int i = 0; i < j; ++i)
   {
    if (num==T[i])  
      return 0; 
   }
   return 1;
}
int no_L(int num,int *L)
{
   for (int i = Lleft; i < Lright; ++i)
   {
    if (num==L[i])  
      return 0; 
   }
   return 1;
}
/*
5
7
0 1
0 2
0 3
1 4
1 3
2 3
3 4


图
1  2  3
0  4  3
0  3
0  1  2  4
1  3

路线
0 1 2 3 4
1 0 3 4 2
2 0 3 1 4
3 0 1 2 4
4 1 3 0 2
Press any key to continue
*/

广度优先搜索算法_基于邻接表