图的广度优先遍历问题,望大家指点
运行“5---广度优先遍历”时总是出现内存引用错误,该内存不能为“written”。是否我在初始化队列时代码有错误呢?请大家指教!(注:红色部分是与“队列”和“广度优先遍历”有关的代码)
在tc下没有内存错误,但实现不了结果。在vc++就有内存错误
#include <stdio.h>
#define MAX 10 /* 图的最多顶点数*/
#define INF 65535 /*定义大于所有权值的一个数*/
#define MAXLEN 10 /*定义MAXLEN等于10*/
typedef enum {DGN,UDGN} GraphKind; /*DGN包括有向图和有向网,UDGN包括无向图和无向网*/
typedef char VertexType; /* 图的顶点类型 */
typedef int AdjType; /* 图的边(或弧)的类型,如果是网,则权值非负 */
typedef struct /*队的结构*/
{
VertexType* Q;
int front,rear;
}CycQue;
struct
{ VertexType vex;
AdjType lowcost;
}closeedge[MAX];
typedef struct
{ VertexType vexs[MAX+1]; /* 表示的顶点的一维向量 */
AdjType edges[MAX+1][MAX+1];
int n,e; /* n表示当前顶点数 e表示当前的边数(弧数) */
}MGraph;
void CreateGN(MGraph* G,GraphKind gk) /*构造图*/
{ int i,j,k;
AdjType w;
printf("\n\t\t请输入图的顶点数和边数(格式为:顶点数,边数)\n\t\t");
scanf("%d,%d",&(G->n),&(G->e));getchar(); /*输入图的顶点数和边数*/
for(i=1;i<=G->n;i++)
for(j=1;j<=G->n;j++)
G->edges[i][j]=INF; /*邻接矩阵的初始化,用INF表示边或弧的不存在*/
printf("\t\t请输入各顶点的值:\n\t\t");
for(i=1;i<=G->n;i++)
{ scanf("%c",&(G->vexs[i])); getchar(); printf("\t\t"); } /*构造顶点向量*/
printf("请输入边信息,如果不是网,则用0或1表示边(狐)的存在与否。\n");
printf("\t\t如果是网,则输入权值!\n");
printf("\t\t输入格式为:端点1的序号,端点2的序号,1或权值\n\t\t");
for(k=1;k<=G->e;k++)
{ scanf("%d,%d,%d",&i,&j,&w);
getchar();
printf("\t\t");
G->edges[i][j]=w;
if (gk==2)
G->edges[j][i]=w;
} /*构造邻接矩阵*/
printf("\n\t\t输入的各个顶点为: ");
for(i=1;i<=G->n;i++)
printf("%c\t",G->vexs[i]);
printf("\n\t\t输入的邻接矩阵为: \n");
for(i=1;i<=G->n;i++)
{ printf("\n\t\t");
for(j=1;j<=G->n;j++)
printf("%d\t",G->edges[i][j]);
}
}
/*队列操作函数*/
void InitCycQue(CycQue* sp) /*初始化队列*/
{
sp->Q=(VertexType *)malloc(MAXLEN*sizeof(VertexType));
sp->front=sp->rear=0;
printf("\t\t\t内存分配成功\n");
}
int InsertCycQue(CycQue* sp, VertexType x) //入队操作
{
sp->rear=(sp->rear+1)%MAXLEN;
sp->Q[sp->rear]=x;
return 1;
}
int ExitCycQue(CycQue* sp,VertexType x) //出队操作
{
sp->front=(sp->front+1)%MAXLEN;
x=sp->Q[sp->front];
return 1;
}
EmptyQue(CycQue* sp) /*判断队列是否空*/
{
if(sp->front==sp->rear)
{
return 1;
}
return 0;
}
void BFSM(MGraph* G,int i,int visited[MAX] ) /*从第i 个顶点开始的广度优先搜索遍历*/
{
int j,k;
VertexType x;
CycQue* sp;
printf("\t\t\t输入i的值:");
scanf("%d",&i);
printf("\n");
InitCycQue(sp);
printf("\t\t\tthe node is:%c\n",G->vexs[i]);
visited[i]=1;
InsertCycQue(sp,G->vexs[i]);
while(!EmptyQue(sp))
{
k=ExitCycQue(sp,x);
for(j=1;j<=G->n;j++)
if(G->edges[k][j]!= INF&& (!visited[j]))
{
printf("the node is:%c\n",G->vexs[j]);
visited[j]=1;
InsertCycQue(sp,G->vexs[j]);
}
}
}
main()
{ MGraph G;
GraphKind gk;
VertexType a;
int choice;
int i,j=1,ch2,k;
int visited[MAX]; /*定义数组存储访问标志*/
int P[MAX]; /*记录单源点的最短路径*/
AdjType D[MAX]; /*记录从源点到其余各顶点的最短路径的长度*/
printf("\t\t请输入图的类型(有向还是无向)\n");
printf("\t\t如果是有向图或有向网输入1,否则输入2\n\t\t");
scanf("%d",&gk);getchar();
CreateGN(&G,gk);
BFSM(&G,i,visited); /*广度优先搜索遍历*/
}
[[italic] 本帖最后由 诸事丁 于 2008-1-4 18:24 编辑 [/italic]]