l7_6.cpp

数据结构课程的源代码

//用邻接表实现无向图的广度优先搜索遍历
#include<iostream.h>
const   int      n =8;            // 表示图中最大顶点数
const   int      e= 10;           // 图中最大边数
typedef int elemtype;
struct  link                       //定义链表类型
{ 
   elemtype   data ;
   link  *next ;
};
struct  node                     //定义邻接表的表头类型
{  
elemtype   v;            //顶点信息
link   *next;
}a[n+1];
int visited[n];
void  creatlink( )
{  int i,j,k ;
 link   *s ;
for(i=1; i<=n;i++)                   //建立邻接表头结点
{ a[i].v=i ;
   a[i].next=NULL;
 }
for(k=1; k<=e;k++)
{ cout<<"请输入一条边";
 cin>>i>>j ;                      //输入一条边 (i,j)
 cout<<endl;
 s=new  link;                     //申请一个动态存储单元
s->data=j ;
s->next=a[i].next ;
a[i].next=s ;
s=new  link;               
s->data=i ;
s->next=a[j].next ;
a[j].next=s ;
}
}
void  bfs1(int i)
{ int  q[n+1] ;               //定义队列
  int  f,r ;
  link  *p ;                //P为搜索指针
  f=r=0 ;
  cout<<a[i].v<<"  " ;
 visited[i]=1 ;
 r++; q[r]=i ;                //进队
 while (f<r)
{ f++ ; i=q[f] ;           //出队
  p=a[i].next ;
  while  (p!=NULL)
   { if  (!visited[p->data])
{ cout<<a[p->data].v<<"  ";
  visited[p->data]=1 ;
   r++;q[r]=p->data ;
}
p=p->next;
}
}
  }


void main( )
{ link *p;
   creatlink( );
   for(int i=1;i<=n;i++)
   {  p=a[i].next;
      cout<<a[i].v<<"->";
      while(p->next!=NULL)
	  {  cout<<p->data<<"->";
	     p=p->next;
	  }
	  cout<<p->data<<endl;
   }
   for(i=1;i<=n;i++)
	   visited[i]=0;
   cout<<"请输入开始访问的顶点";
   cin>>i;
   cout<<endl;
   cout<<"从"<<i<<"出发的广度优先搜索遍历序列为"<<endl;
   bfs1(i);
   cout<<endl;
}