在做数据结构的图的广度遍历，发现一个问题。
运行环境codeblcok
BFS代码如下
void BFS(Lgraph v, int i, que q) //广度遍历
{
int t;
ptradjlist w = NULL;
w = v->G[i].firstedge;
if(w->next == NULL) //i=0
printf("over\n");
visit[i] = 1;
Inserts(q, i);
while(!Isempty(q))
{
t = Delete(q);
printf("%d ",t);
if(w->next == NULL)//t=0
printf("over\n");
for(w = v->G[t].firstedge; w; w = w->next)
{
if(w->next == NULL)
printf("null\n");
if(!visit[w->adj])
{
visit[w->adj] = 1;
Inserts(q, w->adj);
}
}
}
putchar('\n');
}
运行结果中却只输出了null并没有运行over。
想了一个一下午，还是没有想出来。
下面附完全代码和运行结果
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30
typedef struct Gnode *Lgraph; //输入的n个结点必须从
typedef struct adjnode *ptradjlist;
typedef struct Enode *Edge;
typedef struct Queue *que;
typedef struct Vnode
{
ptradjlist firstedge;
}ad;
struct Queue
{
ptradjlist front;
ptradjlist rear;
};
struct Gnode
{
int nv;
int ne;
ad G[MAX];
};
struct adjnode
{
int adj;
int weight;
ptradjlist next;
};
struct Enode
{
int v,w;
int weight;
};
int visit[MAX];
Lgraph CreateLgraph(int n); //初始化有n个结点的图
void Insert(Lgraph G, Edge E); //把边插入
Lgraph BuildLgraph(); //完整的创建一个图
void DFS(Lgraph v,int i); //深度遍历图
void RESET(int nv); //重置visit的值
que Createqueue(); //创建有头结点的队列
int Delete(que q);
void Inserts(que q, int x);
void BFS(Lgraph v, int i, que q); //广度遍历
int Isempty(que q);
int main(void)
{
Lgraph v;
que q;
v = BuildLgraph();
printf("DFS\n");
DFS(v,0);
putchar('\n');
RESET(v->nv);
if(v->G[0].firstedge->next == NULL)
printf("over\n");
printf("BFS\n");
q = Createqueue();
BFS(v,0,q);
return 0;
}
Lgraph CreateLgraph(int n) //初始化有n个结点的图
{
Lgraph g = (Lgraph)malloc(sizeof(struct Gnode));
int i;
g->nv = n;
g->ne = 0;
for(i = 0; i < n; i++)
g->G[i].firstedge = NULL;
return g;
}
void Insert(Lgraph G, Edge E) //把边插入
{
ptradjlist aj;
aj = (ptradjlist)malloc(sizeof(struct adjnode));
aj->adj = E->w;
aj->weight = E->weight;
aj->next = G->G[E->v].firstedge;
G->G[E->v].firstedge = aj;
/*aj = (ptradjlist)malloc(sizeof(struct adjnode));
aj->adj = E->v;
aj->weight = E->weight;
aj->next = G->G[E->w].firstedge;
G->G[E->w].firstedge = aj;
*/
}
Lgraph BuildLgraph() //完整的创建一个图
{
Lgraph g;
int n, i;
Edge e;
e = (Edge)malloc(sizeof(struct Enode));
printf("please input nv\n");
scanf("%d",&n);
g = CreateLgraph(n);
printf("please input ne\n");
scanf("%d",&g->ne);
for(i = 0; i < g->ne; i++)
{
scanf("%d %d %d",&e->v,&e->w,&e->weight);
Insert(g,e);
}
return g;
}
void DFS(Lgraph v,int i) //深度遍历图
{
ptradjlist w = v->G[i].firstedge;
if(visit[i] == 0)
{
visit[i] = 1;
printf("%d ",i);
}
for( ; w; w = w->next)
{
if(visit[w->adj] == 0)
{
visit[w->adj] = 1;
printf("%d ",w->adj);
/*if(v->G[w->adj].firstedge==NULL && w->next!=NULL && visit[w->next->adj]==0)
printf("\n%d ",i);
*/
DFS(v,w->adj);
}
}
}
void RESET(int nv) //重置visit的值
{
int i;
for(i = 0; i < nv; i++)
visit[i] = 0;
}
que Createqueue() //创建有头结点的队列
{
que q = (que)malloc(sizeof(struct Queue));
q->front = (ptradjlist)malloc(sizeof(struct adjnode));
q->front->next = NULL;
q->rear = q->front;
return q;
}
int Delete(que q)
{
int y;
ptradjlist temp;
if(q->front->next == q->rear)
{
temp = q->front->next;
y = temp->adj;
free(temp);
q->front->next = NULL;
q->rear = q->front;
return y;
}
temp = q->front->next;
q->front = temp->next;
y = temp->adj;
free(temp);
return y;
}
void Inserts(que q, int x)
{
ptradjlist temp = (ptradjlist)malloc(sizeof(struct adjnode));
temp->adj = x;
temp->next = NULL;
q->rear->next = temp;
q->rear = temp;
}
int Isempty(que q)
{
if(q->front == q->rear)
return 1;
else
return 0;
}
void BFS(Lgraph v, int i, que q) //广度遍历
{
int t;
ptradjlist w = NULL;
w = v->G[i].firstedge;
if(w->next == NULL)
printf("over\n");
visit[i] = 1;
Inserts(q, i);
while(!Isempty(q))
{
t = Delete(q);
printf("%d ",t);
if(w->next == NULL)
printf("over\n");
for(w = v->G[t].firstedge; w; w = w->next)
{
if(w->next == NULL)
printf("null\n");
if(!visit[w->adj])
{
visit[w->adj] = 1;
Inserts(q, w->adj);
}
}
}
putchar('\n');
}
/*
0 1 5
1 2 5
0 3 5
*/
运行如下：
求解，十分感谢。
