这是一个广度优先搜索无向图的代码,自己写的但是无法完成请高手帮忙分析一下谢谢!
enum Status
{
OK,
ERROR,
}; //定义枚举类型typedef struct QNode
{
int data; //数据域
struct QNode *next; //指针域
}QNode, *QueuePtr; //定义链队列结点typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue; //定义链队列头尾指针Status InitQueue( LinkQueue &Q )
{
//将Q初始化为一个具有头结点的空的链队列
Q.front=Q.rear=( QueuePtr ) malloc ( sizeof( QNode ) ); //申请头结点空间
if( Q.front==NULL ) return ERROR; //内存空间申请不成功
Q.front->next=NULL;
return OK;
}Status DestroyQueue(LinkQueue &Q)
{
//销毁队列Q
QueuePtr p;
while(Q.front->next)
{
p=Q.front->next;
Q.front->next=p->next;
free(p);
}
free(Q.front); //释放头结点
return OK;
}Status QueueIsEmpty(LinkQueue Q)
{
//判断队列是否为空
if (Q.front->next==NULL) return OK;
return ERROR;
}Status EnQueue(LinkQueue &Q, int e)
{
//将数据元素e插入到队列Q的队尾
QueuePtr p;
p=( QueuePtr ) malloc ( sizeof( QNode ) );
if( p==NULL ) return ERROR;
p->data=e;
p->next=NULL; //创建新结点
Q.rear->next=p;
Q.rear=p; //插入
return OK;
}Status DeQueue(LinkQueue &Q, int &e)
{
//将队列Q的队头元素出队,并存放到e中
QueuePtr p;
if( Q.front==Q.rear ) return ERROR; //空队出错
p=Q.front->next; //记住要删除的结点
Q.front->next=p->next; //队头元素p出队
if( Q.rear==p ) Q.rear=Q.front; //如果队中只有一个元素p,则p出队后成为空队
e=p->data;
free(p); //释放存储空间
return OK;
}#define MAX_VERTEX_NUM 100
typedef struct ArcNode
{
int adjvertex; //关联的顶点序号
struct ArcNode *nextarc; //指向下一条边
} ArcNode, *ArcLink; //边结点的定义
typedef struct VertexNode
{
char data; //顶点信息
bool flag; //标志,是否被访问过
ArcNode *firstarc; //指向关联的第一条边
} VertexNode; //顶点结点的定义
typedef struct Graph
{
VertexNode vertex[MAX_VERTEX_NUM];
int vexnum,arcnum; //图的顶点数,边数
} Graph; //图的定义void CreateGraph(Graph &G)
{
int m,n,i;
ArcLink p;
//输入顶点数和边数
printf("请输入顶点数和边数: ");
scanf("%d %d",&G.vexnum,&G.arcnum);
while(G.arcnum>G.vexnum*(G.vexnum-1)/2 || G.arcnum<0)
{
printf("输入的数字不符合要求,请重新输入: ");
scanf("%d %d",&G.vexnum,&G.arcnum);
}
//构建顶点集
for(i=0;i<G.vexnum;i++)
{
printf("请输入第%d个顶点的信息: ",i);
getchar(); //躲避回车符
scanf("%c",&G.vertex[i].data);
G.vertex[i].flag=false;
G.vertex[i].firstarc=NULL;
}
//构建边集
for(i=0;i<G.arcnum;i++)
{
printf("请输入第%d条边的2个顶点的序号(序号只能从0——%d,且不能重复): ",i,G.vexnum-1);
scanf("%d %d",&m,&n);
while(m<0 || m>=G.vexnum || n<0 || n>=G.vexnum || m==n)
{
printf("输入的数字不符合要求,请重新输入: ");
scanf("%d %d",&m,&n);
}
p=(ArcLink) malloc (sizeof(ArcNode)); //新建边结点,插入在顶点结点后面
p->adjvertex=n;
p->nextarc=G.vertex[m].firstarc;
G.vertex[m].firstarc=p;
}
}int NextAdjVertex(Graph &G,int t)
{
ArcLink p;
p=G.vertex[t].firstarc->nextarc;
if(p!=NULL)
{p++;t=p->adjvertex;}
else
t=NULL;
return t;
}void BFSGraph(Graph &G,int v) //v0表示起始顶点的序号
{
LinkQueue Q;
InitQueue (Q);
int e,w;
for(v=0;v<G.vexnum;++v)
{if(G.vertex[v].flag==false)
{printf("%c\n",G.vertex[v].data);
EnQueue(Q,v);
while(QueueIsEmpty(Q)==ERROR)
{DeQueue(Q,e);
printf("%c\n",G.vertex[e].data);
for(w=G.vertex[w].firstarc->nextarc->adjvertex;w>=0;w=NextAdjVertex(G,w))
{if(w!=NULL&&G.vertex[w].flag==false)
{printf("%c\n",G.vertex[w].data);
EnQueue(Q,w);
}
}
}
}
}
}
//无向图的广度优先搜索#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "public.h"
#include "queue.h"
#include "graph.h"void main()
{
Graph G;
CreateGraph(G);
BFSGraph(G,0);
}
enum Status
{
OK,
ERROR,
}; //定义枚举类型typedef struct QNode
{
int data; //数据域
struct QNode *next; //指针域
}QNode, *QueuePtr; //定义链队列结点typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue; //定义链队列头尾指针Status InitQueue( LinkQueue &Q )
{
//将Q初始化为一个具有头结点的空的链队列
Q.front=Q.rear=( QueuePtr ) malloc ( sizeof( QNode ) ); //申请头结点空间
if( Q.front==NULL ) return ERROR; //内存空间申请不成功
Q.front->next=NULL;
return OK;
}Status DestroyQueue(LinkQueue &Q)
{
//销毁队列Q
QueuePtr p;
while(Q.front->next)
{
p=Q.front->next;
Q.front->next=p->next;
free(p);
}
free(Q.front); //释放头结点
return OK;
}Status QueueIsEmpty(LinkQueue Q)
{
//判断队列是否为空
if (Q.front->next==NULL) return OK;
return ERROR;
}Status EnQueue(LinkQueue &Q, int e)
{
//将数据元素e插入到队列Q的队尾
QueuePtr p;
p=( QueuePtr ) malloc ( sizeof( QNode ) );
if( p==NULL ) return ERROR;
p->data=e;
p->next=NULL; //创建新结点
Q.rear->next=p;
Q.rear=p; //插入
return OK;
}Status DeQueue(LinkQueue &Q, int &e)
{
//将队列Q的队头元素出队,并存放到e中
QueuePtr p;
if( Q.front==Q.rear ) return ERROR; //空队出错
p=Q.front->next; //记住要删除的结点
Q.front->next=p->next; //队头元素p出队
if( Q.rear==p ) Q.rear=Q.front; //如果队中只有一个元素p,则p出队后成为空队
e=p->data;
free(p); //释放存储空间
return OK;
}#define MAX_VERTEX_NUM 100
typedef struct ArcNode
{
int adjvertex; //关联的顶点序号
struct ArcNode *nextarc; //指向下一条边
} ArcNode, *ArcLink; //边结点的定义
typedef struct VertexNode
{
char data; //顶点信息
bool flag; //标志,是否被访问过
ArcNode *firstarc; //指向关联的第一条边
} VertexNode; //顶点结点的定义
typedef struct Graph
{
VertexNode vertex[MAX_VERTEX_NUM];
int vexnum,arcnum; //图的顶点数,边数
} Graph; //图的定义void CreateGraph(Graph &G)
{
int m,n,i;
ArcLink p;
//输入顶点数和边数
printf("请输入顶点数和边数: ");
scanf("%d %d",&G.vexnum,&G.arcnum);
while(G.arcnum>G.vexnum*(G.vexnum-1)/2 || G.arcnum<0)
{
printf("输入的数字不符合要求,请重新输入: ");
scanf("%d %d",&G.vexnum,&G.arcnum);
}
//构建顶点集
for(i=0;i<G.vexnum;i++)
{
printf("请输入第%d个顶点的信息: ",i);
getchar(); //躲避回车符
scanf("%c",&G.vertex[i].data);
G.vertex[i].flag=false;
G.vertex[i].firstarc=NULL;
}
//构建边集
for(i=0;i<G.arcnum;i++)
{
printf("请输入第%d条边的2个顶点的序号(序号只能从0——%d,且不能重复): ",i,G.vexnum-1);
scanf("%d %d",&m,&n);
while(m<0 || m>=G.vexnum || n<0 || n>=G.vexnum || m==n)
{
printf("输入的数字不符合要求,请重新输入: ");
scanf("%d %d",&m,&n);
}
p=(ArcLink) malloc (sizeof(ArcNode)); //新建边结点,插入在顶点结点后面
p->adjvertex=n;
p->nextarc=G.vertex[m].firstarc;
G.vertex[m].firstarc=p;
}
}int NextAdjVertex(Graph &G,int t)
{
ArcLink p;
p=G.vertex[t].firstarc->nextarc;
if(p!=NULL)
{p++;t=p->adjvertex;}
else
t=NULL;
return t;
}void BFSGraph(Graph &G,int v) //v0表示起始顶点的序号
{
LinkQueue Q;
InitQueue (Q);
int e,w;
for(v=0;v<G.vexnum;++v)
{if(G.vertex[v].flag==false)
{printf("%c\n",G.vertex[v].data);
EnQueue(Q,v);
while(QueueIsEmpty(Q)==ERROR)
{DeQueue(Q,e);
printf("%c\n",G.vertex[e].data);
for(w=G.vertex[w].firstarc->nextarc->adjvertex;w>=0;w=NextAdjVertex(G,w))
{if(w!=NULL&&G.vertex[w].flag==false)
{printf("%c\n",G.vertex[w].data);
EnQueue(Q,w);
}
}
}
}
}
}
//无向图的广度优先搜索#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "public.h"
#include "queue.h"
#include "graph.h"void main()
{
Graph G;
CreateGraph(G);
BFSGraph(G,0);
}
数据结构书上有附码,自己对着改就是了