廣度優先搜尋算法_基于鄰接表

//廣度優先搜尋算法_基于鄰接表
//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
*/