#include<iostream>
using namespace std;
#define MAX_VERTEX_NUM 30 /* 图中顶点数的最大值*/
#define OK 1
#define TRUE 1
#define ERROR 0
#define FALSE 0
#define null 0
int Visited[MAX_VERTEX_NUM]; /*访问标志数组(全局量) */
char Edge[2*MAX_VERTEX_NUM];
int i=0;
int j=0;
struct Qnode{
int data;
Qnode *next;
};
struct Queue{
Qnode *front;
Qnode *rear;
};
void InitQueue(Queue &Q){
Q.front=Q.rear=new Qnode;
Q.front->next=null;
}
int DestroyQueue(Queue &Q){
while(Q.front!=null){
Q.rear=Q.front->next;
delete Q.front;
Q.front=Q.rear;
}
return OK;
}
int QueueEmpty(Queue &Q){
if(Q.front==Q.rear)
return OK;
else
return ERROR;
}
void EnQueue(Queue &Q,int e){
Qnode *pt;
pt=new Qnode;
pt->data=e;
pt->next=null;
Q.rear->next=pt;
Q.rear=pt;
}
void DeQueue(Queue &Q,int &e){
Qnode *ps;
ps=Q.front->next;
e=ps->data;
if(ps->next==null){
Q.front->next=null;Q.front=Q.rear;
}
else Q.front->next=ps->next;
}
enum VisitIf{unvisited,visited};
struct Ebox{
VisitIf mark;
int ivex;
int jvex;
struct Ebox *ilink;
struct Ebox *jlink;
string *info;
};
struct Vexbox{
char data;
Ebox *firstedge;
};
struct AMLGraph{
Vexbox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum;
};
int LocateVex(AMLGraph G,char u){
int i;
for(i=0;i<G.vexnum;i++)
if(u==G.adjmulist[i].data)
return i;
return -1;
}
/*返回v的顶点值*/
int FirstAdjvex(AMLGraph G,char v){
int i;
i=LocateVex(G,v);
if(i<0)
return -1;
else if(G.adjmulist[i].firstedge!=null){
if(G.adjmulist[i].firstedge->ivex==i){
return G.adjmulist[i].firstedge->jvex;
}
else
return G.adjmulist[i].firstedge->ivex;
}
else return -1;
}
int NextAdjvex(AMLGraph G,char v,char w){
int i,j;
Ebox *p;
i=LocateVex(G,v);
j=LocateVex(G,w);
if(i<0||j<0)
return -1;
p=G.adjmulist[i].firstedge;
while(p!=null)
if(p->ivex==i && p->jvex!=j)
p=p->ilink;
else if(p->jvex==i && p->ivex!=j)
p=p->jlink;
else break;
if(p && p->ivex==i && p->jvex==j)
{
p=p->ilink;
if(p && p->ivex==i)
return p->jvex;
else
if(p && p->jvex==i)
return p->ivex;
}
if(p && p->ivex==j && p->jvex==i)
{
p=p->jlink;
if(p && p->ivex==i)
return p->jvex;
else
if(p && p->jvex==i)
return p->ivex;
}
return -1;
}
/* 采用邻接多重表存储结构,构造无向图G */
void CreateGraph(AMLGraph &G)
{
int i,j,k,cur=0;
char va,vb;
Ebox *p;
cout<<endl<<"请输入图的顶点数: ";
cin>>G.vexnum;
cout<<"请输入图的边数: ";
cin>>G.edgenum;
cout<<"请输入 "<<G.vexnum<<" 个顶点的数值:"<<endl;
for(i=0;i<G.vexnum;++i){
cin>>G.adjmulist[i].data;
G.adjmulist[i].firstedge=null;
}
cout<<"输入一条边上两个顶点的信息:"<<endl;
for(k=0;k<G.edgenum;++k) /* 构造表结点链表 */
{
cin>>va>>vb; /* 读入两个顶点*/
Edge[cur++]=va;
Edge[cur++]=vb;
i=LocateVex(G,va); /* 一端 */
j=LocateVex(G,vb); /* 另一端 */
p=new Ebox;
p->mark=unvisited; /* 设初值 */
p->ivex=i;
p->jvex=j;
p->info=null;
p->ilink=null;
p->jlink=null;
p->ilink=G.adjmulist[i].firstedge; /* 插在表头 */
G.adjmulist[i].firstedge=p;
p->jlink=G.adjmulist[j].firstedge; /* 插在表头 */
G.adjmulist[j].firstedge=p; /*插入j链表尾部*/
}
}
void DFS(AMLGraph G,int v);
void DFSTraverse(AMLGraph G ,char start){
int v,z;
for(v=0;v<G.vexnum;v++)Visited[v]=0;
z=LocateVex(G,start);
for(v=0;v<G.vexnum;v++)
if(Visited[(v+z)%G.vexnum]==0)
DFS(G,(v+z)%G.vexnum);
}
void DFS(AMLGraph G,int v){
Visited[v]=1;
cout<<G.adjmulist[v].data<<endl;
char u;
u=G.adjmulist[v].data;
for(int w=FirstAdjvex(G,u);w>=0;w=NextAdjvex(G,u,G.adjmulist[w].data))
if(Visited[w]==0){cout<<G.adjmulist[v].data<<"--"<<G.adjmulist[w].data<<endl;
DFS(G,w);
}
}
void BFSTraverse(AMLGraph G,char start){
Queue Q;
int u,z,w;
for(int v=0;v<G.vexnum;v++)Visited[v]=0;
InitQueue(Q);
z=LocateVex(G,start);
for(v=0;v<G.vexnum;v++)
if(Visited[(v+z)%G.vexnum]==0){
Visited[(v+z)%G.vexnum]=1;
cout<<G.adjmulist[(v+z)%G.vexnum].data<<endl;
EnQueue(Q,(v+z)%G.vexnum);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
for(w=FirstAdjvex(G,G.adjmulist[u].data);w>=0;w=NextAdjvex(G,G.adjmulist[u].data,
G.adjmulist[w].data))
if(Visited[w]==0){
Visited[w]=1;
cout<<G.adjmulist[u].data<<"--"<<G.adjmulist[w].data<<endl;
cout<<G.adjmulist[w].data<<endl;
EnQueue(Q,w);
}
}
}
DestroyQueue(Q);
}
int main(){
AMLGraph G;
char start;;
CreateGraph(G);
cout<<"输入要开始搜索的点:"<<endl;
cin>>start;
cout<<"深度优先搜索:"<<endl;
DFSTraverse(G,start);
cout<<"广度优先搜索:"<<endl;
BFSTraverse(G,start);
return 0;
}