在图的广度遍历中用到的队列有问题,麻烦看一下
这是我写的图的四个基本操作,创建和深度遍历我自己试了没有问题,可是我一用广度遍历就显示Acess Violation.麻烦各位看下我哪个地方出错了#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100
#define true 1
#define false 0
typedef struct//图
{
int edges[MAX][MAX]; //邻接矩阵
int n; //顶点数
int e; //边数
}Tu;
int visited[MAX]; //标记顶点是否被访问过
typedef struct QNode
{
int data;
struct QNode *next;
}QNode,*QPtr;
typedef struct LinkQueue{
QPtr front;
QPtr tail;
}LinkQueue;
void InitQ(LinkQueue Q);//初始化队列
void EnQueue(LinkQueue Q,int e);//从队尾插入元素
void DeQueue(LinkQueue Q,int e);//从队首删除元素
int QEmpty(const LinkQueue Q);//队列是否为空,为空返回1,否则返回0
int firstAjdVex(Tu G,int v);//得到第一个未被访问的相邻节点下标,若无,则返回-1
int nextAjdVex(Tu G,int v,int w);//得到下一个未被访问的相邻节点下标,若无,则返回-1
void InitQ(LinkQueue Q)//初始化队列
{
Q.front = Q.tail = (QPtr)malloc(sizeof(struct QNode));
if ( !Q.front )
{
printf("InitQ分配内存出错!\n");
return ;
}
Q.front->next = NULL;
Q.tail->next=NULL;
}
void EnQueue(LinkQueue Q,int e)//从队尾插入元素
{
QPtr q;
q = (QPtr)malloc(sizeof(struct QNode));
if ( !q )
{
printf("EnQueue分配内存出错!\n");
return ;
}
q->data = e;
q->next = NULL;
Q.tail->next = q; //如果是第一次插入,Q.front->next也指向了q
Q.tail = q;
}
void DeQueue(LinkQueue Q,int e){//从队首删除元素
QPtr q;
if ( Q.front == Q.tail )
{
printf("DeQueue队列为空,不能删除元素!\n");
return ;
}
q = Q.front->next;
e = q->data;
Q.front->next = q->next;
if ( Q.tail == q )
Q.tail = Q.front;
free(q);
}
int QEmpty(const LinkQueue Q)//队列是否为空,为空返回1,否则返回0
{
if ( Q.front == Q.tail )
{
return 1;
}
else
{
return 0;
}
}
Tu creat() //创建图
{
int i;
int x;
int y;
int s,t; //存储顶点编号
int v; //存储边的权值
Tu G;
for(i=0;i<MAX;i++)
visited[i]=false;
printf("输入顶点数");
scanf("%d",&x);
G.n=x;
printf("输入边数");
scanf("%d",&y);
G.e=y;
for(i=0;i<G.e;i++) //对矩阵相邻的边赋权值
{
printf("输入顶点编号及权值\n");
scanf("%d %d %d",&s,&t,&v); //输入边的顶点编号以及权值
G.edges[s][t]=v;
G.edges[t][s]=v;
}
return G;
}
void DFS(Tu G,int v) //深度优先搜索
{
int i,j;
j=G.n;
visited[v]=true;
printf("%d\n",v);
for(i=0;i<j;i++) //访问与v相邻的未被访问过的结点
{
if(visited[i]==0)
{
DFS(G,i);
}
}
}
void BFS(Tu G)//广度优先遍历函数
{
int i,w,v;
LinkQueue Q;
Q.tail=NULL;
Q.front=NULL;
InitQ(Q);
v=0;
for ( i = 0; i < G.n; i++ )
visited[i] = 0; //初始化访问标记数组
for ( i = 0; i < G.n; i++ )
{
if ( visited[i]==false )
{
visited[i] = true;
printf("%d",i);
EnQueue(Q,i);
while (!QEmpty(Q))
{
DeQueue(Q,v);
for ( w = firstAjdVex(G,v); w >= 0; w = nextAjdVex(G,v,w) )
{
if ( visited[w]==false)
{
visited[w] = true;
printf("%d",w);
EnQueue(Q,w);
}
}
}
}
}
}
int firstAjdVex(Tu G,int v)//得到第一个未被访问的相邻节点下标,若无,则返回-1
{
int i;
int j;
j=G.n;
for ( i = 0; i<j; i++ )
{
if ( visited[i]==false&&G.edges[v][i]>0)
return i;
}
return -1;
}
int nextAjdVex(Tu G,int v,int w)//得到下一个未被访问的相邻节点下标,若无,则返回-1
{
int i;
for ( i = w; i < G.n; i++ )
{
if ( visited[i]==0 && G.edges[v][i] > 0)
return i;
}
return -1;
}
void Destory(Tu G)//销毁图
{
int i;
int j;
for(i=0;i<G.n;i++)
{
for(j=0;j<G.n;j++)
{
G.edges[i][j]=0;
}
}
G.n=0;
G.e=0;
}
void main(){
Tu G;
int x;
for( ; ; ){
printf("what would you want to do\n");
printf("1.创建图\n");
printf("2.深度遍历\n");
printf("3.广度遍历\n");
printf("4.销毁\n");
for(;;){
scanf("%d",&x);
if(x<0||x>4)
printf("输入错误");
else
break;
}
switch(x)
{
case 1:
printf("图的创建\n");
G=creat();
break;
case 2:
printf("深度遍历\n");
DFS(G,0);
break;
case 3:
printf("广度遍历\n");
BFS(G);
break;
case 4:
printf("销毁\n");
Destory(G);
break;
}
}
}