//DATE:2006-12-03 BY:snowhill
/* 1---2 以邻接表存放应为: 1->5->3->2
| \ / | 2->4->3->1
| 3 | 3->5->4->2->1
| / \ | 4->5->3->2
5---4 5->4->3->1
*/
/* 图的邻接表 以a[1]为起始地起址存放 */
#include "iostream.h"
const int n=5;
const int e=8;
int visited[n+1]; //访问标志数组
struct link
{
int data;
link *next;
};
struct node
{
int v; //顶点信息
link *next;
}a[n+1];
/* 无向图的建立 */
void createlink()
{
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;
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 dfs(int i)
{
link *p;
cout<<a[i].v<<" ";
visited[i]=1;
p=a[i].next;
while(p!=NULL)
{
if(!visited[p->data])
dfs(p->data);
p=p->next;
}
}
void main()
{
link *p;char yn='y';int k;
createlink();
while(yn=='y')
{
cout<<"你建立的图为:"<<endl;
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>>k;
cout<<endl;
dfs(k);
cout<<"要继续遍历吗(Y/N)?";
cin>>yn;
}
}