#include
#include
#define MVNum 100
#define OK 1
#define ERROR -1
using namespace std;
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;
Status LocateVex(ALGraph G,VerTexType v){
for(int i=0;i<G.vexnum;++i){
if(G.vertices[i].data==v)
return i;
return ERROR;
}
}
Status CreateUDG(ALGraph &G){
VerTexType v1,v2;
int i,j,k;
cout<<"请输入顶点和边数:";
cin>>G.vexnum>>G.arcnum; //顶点和边数
cout<<"请输入顶点:";
for(i=0;i<G.vexnum;++i){
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL; //初始化表头指针
}
cout<<"请输入边:"<<endl;
for(k=0;k<G.arcnum;++k){
ArcNode *p1,*p2;
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;
}
void Print(ALGraph G)//打印邻接表
{
cout<<"打印邻接表如下:";
cout<<endl;
for(int i=0; i<G.vexnum; i++)//遍历每个顶点的邻接表
{
cout<<G.vertices[i].data;
ArcNode *p=G.vertices[i].firstarc;
while(p)
{
cout<<"->"<<G.vertices[p->adjvex].data;
p=p->nextarc;
}
cout<<endl;
}
}
int FirstAdjVex(ALGraph G,int v){
ArcNode *p=G.vertices[v].firstarc;
if(p) return p->adjvex;
else
return ERROR;
}
int NextAdjVex(ALGraph G,int v,int w){
int i;
ArcNode *p=G.vertices[i].firstarc;
while(p){
if(p->adjvex==w) break;
p=p->nextarc;
}
if(p->adjvex!=w||!p->nextarc)
return ERROR;
return p->nextarc->adjvex;
}
bool visited[10];
void DFS(ALGraph G,int v){
int w;
visited[v]=true;
cout<<G.vertices[v].data<<" ";
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
if(!visited[w])
DFS(G,w);
}
void DFSTraverse(ALGraph G) //深搜
{ int i;
for(i=0;i<G.vexnum;++i)
visited[i]=false; //全部置为未访问
for(i=0;i<G.vexnum;i++)
if(!visited[i])
DFS(G, i);
}
void BFSTraverse(ALGraph G) //广搜
{
queue q;
int i;
for(i=0; i<G.vexnum; i++)
visited[i]=false;
for(i=0; i<G.vexnum; i++)
{
if(!visited[i])
{
q.push(i);
visited[i]=true;
while(!q.empty())
{
int v=q.front();
q.pop();
cout<<G.vertices[v].data<<" ";
for(int w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w))
{
if (!visited[w])
{
q.push(w);
visited[w]=true;
}
}
}
}
}
}
int main()
{
ALGraph G;
CreateUDG(G);
Print(G);
cout<<"深度遍历:";
DFSTraverse(G);
cout<<endl;
cout<<"广度遍历:";
BFSTraverse(G);
cout<<endl;
return 0;
}