#include<stdlib.h>
#include<iostream.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define MaxInt 0 //表示极大值，即∞
#define MVNum 100 //最大顶点数
typedef char VerTexType; //假设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
typedef int OtherInfo;
typedef struct{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;
//
//最大顶点数
typedef struct ArcNode{ //边结点
int adjvex; //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
OtherInfo info; //和边相关的信息
}ArcNode;
typedef struct VNode{
VerTexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct{
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;
/////
typedef int QElemType;
#define MAXQSIZE 100
typedef struct{
QElemType *base;
int front;
int rear;
}SqQueue;
Status InitQueue (SqQueue &Q){
Q.base =new QElemType[MAXQSIZE] ;
if(!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
//入队
Status EnQueue(SqQueue &Q,QElemType e){
if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}
//出队
Status DeQueue(SqQueue &Q,QElemType &e){
if(Q.front==Q.rear) return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
///////////////
Status CreateUDG(ALGraph &G){ //采用邻接表表示法，创建无向图G
int i,j,k;
ArcNode *p1,*p2;
cout<<"vexnum arcnum:";
cin>>G.vexnum>>G.arcnum;
cout<<"输入各点，构造表头结点表"<<endl; //输入总顶点数，总边数
for( i = 0; i<G.vexnum; ++i){ //输入各点，构造表头结点表
cin>> G.vertices[i].data; //输入顶点值
G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL
}//for
cout<<"输入一条边依附的两个顶点WEIZHI "<<endl;
for( k = 0; k<G.arcnum;++k){ //输入各边，构造邻接表
cin>>i>>j; //输入一条边依附的两个顶点
// i = LocateVex(G,v1); j = LocateVex(G, v2);
p1=new ArcNode; //生成一个新的边结点*p1
p1->adjvex=j; //邻接点序号为j
p1->nextarc= G.vertices[i].firstarc; G.vertices[i].firstarc=p1;
//将新结点*p1插入顶点vi的边表头部
p2=new ArcNode; //生成另一个对称的新的边结点*p2
p2->adjvex=i; //邻接点序号为i
p2->nextarc= G.vertices[j].firstarc; G.vertices[j].firstarc=p2;
//将新结点*p2插入顶点vj的边表头部
}//for
return OK;
}//CreateUDG
Status CreateUDN(AMGraph &G){
int i,j,k,w;
//采用邻接矩阵表示法，创建无向网G
cout<<"vexnum arcnum:";
cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数
cout<<"vexs:";
for(i=0; i<G.vexnum; ++i)
cin>>G.vexs[i];
cout<<" aa"<<endl; //依次输入点的信息
for(i=0; i<G.vexnum;++i) //初始化邻接矩阵，边的权值均置为极大值
for(j=0; j<G.vexnum;++j)
G.arcs[i][j] = MaxInt;
for(k=0; k<G.arcnum;++k){ //构造邻接矩阵
cin>>i>>j>>w; //输入一条边依附的顶点及权值
G.arcs[i][j] = w; //边<v1, v2>的权值置为w
//G.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称边<v2, v1>的权值为w
}//for
return OK;
}//CreateUDN
int LocateVex(AMGraph G,VerTexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(u==G.vexs[i]) return i;
return -1;
}
//DFS
bool visited[MVNum];
void DFS(AMGraph G, int v){
//图G为邻接矩阵类型
cout<<v<<","<<G.vexs[v]<<" ";
visited[v] = true; //访问第v个顶点
for(int w = 0; w< G.vexnum; w++) //依次检查邻接矩阵v所在的行
if((G.arcs[v][w]!=0)&& (!visited[w])) DFS(G, w);
//w是v的邻接点，如果w未访问，则递归调用DFS
}
int FirstAdjVex(ALGraph G,int v)
{
ArcNode * p;
int v1;
v1 =v;//v1为顶点v在图G中的序号
p = G.vertices[v1].firstarc;
if (p)
{
return p->adjvex;
//->data.adjvex;
}
else
{
return -1;
}
}
int NextAdjVex(ALGraph G, int v, int w)
{//在图G中寻找第v个顶点的相对于w的下一个邻接顶点
ArcNode *p;
if(v>=1 && v<=G.vexnum && w>=1 && w<=G.vexnum)
{
p=G.vertices[v].firstarc;
while(p->adjvex!=w)
p=p->nextarc; //在顶点v的弧链中找到顶点w
if(p->nextarc!=NULL)
return 0; //若已是最后一个顶点，返回0
else
return(p->nextarc->adjvex); //返回下一个邻接顶点的序号
}
return -1;
}
void BFS (ALGraph G, int v){
//按广度优先非递归遍历连通图G
int u,w;
cout<<v<<","<<G.vertices[v].data<<" ";
visited[v] = true;
SqQueue Q; //访问第v个顶点
InitQueue(Q); //辅助队列Q初始化，置空
EnQueue(Q, v); //v进队
while(Q.front!=Q.rear){ //队列非空
DeQueue(Q, u); //队头元素出队并置为u
for(w = FirstAdjVex(G, u); w>=0; w = NextAdjVex(G, u, w)) {
if(!visited[w]){ //w为u的尚未访问的邻接顶点
cout<<w<<","<<G.vertices[w].data<<" "; visited[w] = true;
EnQueue(Q, w); //w进队
}//if
}
}//while
}//BFS
void main(){
//AMGraph G;
//CreateUDN(G);
ALGraph D;
CreateUDG(D);
//DFS(G,0);
ArcNode *Q;
VNode *P;
P=D.vertices;
for(int i=0;i<5;i++){
Q=P->firstarc;
cout<<P->data;
while(Q){
cout<<Q->adjvex<<" ";
Q=Q->nextarc;
}
cout<<endl;
P++;
}
cout<<"BFS"<<endl;
BFS(D,0);
}