#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
#define maxSize 100
//边表
typedef struct ArcNode
{
int adjvex; //该边所指向的结点的位置
struct ArcNode *nextarc; //指向下一条边的指针
int info; //该边的相关信息（如权值）
}ArcNode;
//顶点表
typedef struct
{
char data; //顶点信息
ArcNode *firstarc; //指向第一条边的指针
}VNode;
typedef struct
{
VNode adjlist[maxSize]; //邻接表
int n,e; //顶点数和边数
}AGraph;
void Create(AGraph *G)
{
cout<<"请输入顶点数和边数:"<<endl;
cin>>G->n>>G->e;
cout<<"输入顶点信息:"<<endl;
for(int i=0;i<G->n;i++)
{
getchar();
cin>>G->adjlist[i].data;
G->adjlist[i].firstarc=NULL; //指向边表的指针初始时置为空
}
ArcNode *p;
//建立边表
cout<<"输入边的下标:"<<endl;
for(int k=0;k<G->e;k++)
{
int i,j;
cin>>i>>j;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j; //存储弧头
p->nextarc=G->adjlist[i].firstarc; //头插法插入边结点
G->adjlist[i].firstarc=p;
//下面代码无向图才有
/*p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i; //存储弧头
p->nextarc=G->adjlist[j].firstarc;
G->adjlist[j].firstarc=p; */
}
cout<<endl<<"邻接表 :"<<endl;
for(int i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
cout<<G->adjlist[i].data<<":";
while(p)
{
cout<<G->adjlist[p->adjvex].data;
p=p->nextarc;
}
cout<<endl;
}
cout<<endl;
}
void Visit(int v)
{
cout<<v<<" ";
}
int visit[maxSize];
void DFS(AGraph *G,int v)
{
ArcNode *p;
visit[v]=1;
Visit(v);
p=G->adjlist[v].firstarc;
while(p!=NULL)
{
if(visit[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc;
}
}
void BFS(AGraph *G,int v,int visit[maxSize])
{
ArcNode *p;
int que[maxSize],front=0,rear=0;
int j;
Visit(v);
visit[v]=1;
rear=(rear+1)%maxSize;
que[rear]=v;
while(front!=rear)
{
front=(front+1)%maxSize;
j=que[front];
p=G->adjlist[j].firstarc;
while(p!=NULL)
{
if(visit[p->adjvex]==0)
{
Visit(p->adjvex);
visit[p->adjvex]=1;
rear=(rear+1)%maxSize;
que[rear]=p->adjvex;
}
p=p->nextarc;
}
}
}
/*测试数据
7 12
a b c d e f g
0 1 0 2 0 3
1 2 1 4 2 5 2 4
3 2 3 5 4 6 5 4 5 6
*/
int main()
{
AGraph G;
Create(&G);
memset(visit,0,sizeof(visit));
cout<<"DFS:"<<endl;
DFS(&G,0);
cout<<endl;
memset(visit,0,sizeof(visit));
cout<<"BFS:"<<endl;
BFS(&G,0,visit);
cout<<endl;
}
