l7_4.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  dfs1(int i)
{ link *p;
   cout<<a[i].v<<"  " ;              //输出访问顶点
   visited[i]=1;                //全局数组访问标记置为1表示已访问
   p=a[i].next;
   while (p!=NULL)
  {  if  (!visited[p->data])  dfs1(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;
   dfs1(i);
   cout<<endl;
}