#include<stdio.h>
#include<iostream.h>
#define MaxInt 32767
#define MVNum 100
#define OK 1
typedef char VerTexType;
typedef int Status;
typedef struct ArcNode//边表
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode//表头结点表
{
VerTexType data;
ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct//图的基本数据
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
int LocateVex(ALGraph &G,VerTexType u)//返回顶点下标
{
int i;
for(i=0;i<G.vexnum;++i)
if(u==G.vertices[i].data)
return i;
return -1;
}
Status CreateUDG(ALGraph &G)//采用邻接表创建无向图
{
int j;
VerTexType v1,v2;
ArcNode *p1,*p2;
cout<<"输入顶点数及边数"<<endl;
cin>>G.vexnum>>G.arcnum ;
cout<<"依次输入点的信息"<<endl;
for(int i=0;i<G.vexnum;++i)
{
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
cout<<"输入边依附的顶点"<<endl;
for(int k=0;k<G.arcnum;++k)
{
cin>>v1>>v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p1=new ArcNode;
p1->adjvex=j;
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1;
p2=new ArcNode;
p2->adjvex=i;
p2->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p2;
}
return OK;
}
bool visited[MVNum];
void DFS_AL(ALGraph G,int v)//深度优先遍历图
{
ArcNode *p;
int w;
cout<<G.vertices[v].data<<" ";
visited[v]=true;
p=G.vertices[v].firstarc ;
while(p!=NULL)
{
w=p->adjvex;
if(!visited[w]) DFS_AL(G,w);
p=p->nextarc;
}
}
void main()
{
int v;
ALGraph G;
cout<<"初始化图"<<endl;
CreateUDG(G);
cout<<"输入遍历开始的位置"<<endl;
cin>>v;
cout<<"输出遍历的结果"<<endl;
DFS_AL(G,v);
cout<<endl;
cout<<"输出邻接表"<<endl;
for(int i=0;i<G.vexnum;i++)
{
cout<<i<<"->";
while(G.vertices[i].firstarc!=NULL)
{
cout<<G.vertices[i].firstarc->adjvex<<"->";
G.vertices[i].firstarc =G.vertices[i].firstarc->nextarc;
}
cout<<endl;
}
}
