//DATE:2006-12-10 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 Max_vertex=5;
const int Max_Edge=8;
int visited[Max_vertex+1]; //访问标志数组
struct ArcNode
{
int adjvex;
ArcNode *nextarc;
//指向下一条弧
};
struct Vnode
{
int v; //顶点信息
ArcNode *next;
}a[Max_vertex+1];
/* 无向图的建立 */
void creategraph()
{
int i,j,k;
ArcNode *s;
//初始化
for(i=1;i<=Max_vertex;i++)
{
a[i].v=i;
a[i].next=NULL;
}
/*以头插法建立 */
for(k=1;k<=Max_Edge;k++)
{
cout<<"请输入第"<<k<<"条边:";
cin>>i>>j;
if(i>9||i<0||j<0||j>9)
{
cout<<"输入错误!!\n"<<endl;
break;
}
else{
cout<<endl;
s=new ArcNode;
s->adjvex=j;
s->nextarc=a[i].next;
a[i].next=s;
s=new ArcNode;
s->adjvex=i;
s->nextarc=a[j].next;
a[j].next=s;
}
}
}
/* 深度优先搜索 */
void dfs(int i)
{
ArcNode *p;
cout<<a[i].v<<" ";
visited[i]=1;
p=a[i].next;
while(p!=NULL)
{
if(!visited[p->adjvex])
dfs(p->adjvex);
p=p->nextarc;
}
}
void display()
{
ArcNode *p;
cout<<"你建立的图为:"<<endl;
for(int i=1;i<=Max_vertex;i++)
{
p=a[i].next;
cout<<a[i].v<<"->";
while(p->nextarc!=NULL)
{
cout<<p->adjvex<<"->";
p=p->nextarc;
}
cout<<p->adjvex<<endl;
}
}
void main()
{
cout<<"/******\t本算法以关插法建立无向图的邻接表为例!\t******/"<<endl;
char yn='y';int k;
creategraph();
display();
for(int i=1;i<=Max_vertex;i++)
visited[i]=0;
cout<<"请输入深度优先搜索的顶点:";
cin>>k;
cout<<endl;
while(yn=='y')
{
dfs(k);
cout<<"要继续遍历吗(Y/N)?";
cin>>yn;
}
}