为什么广度搜索遍历不了！望各位大侠帮忙看看
#include<iostream.h>#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define MAX_VERTEX_NUM 20
typedef char Vertex_Type[5];
typedef enum
{
DG,UDG
}Graph_Kind;
typedef struct Arc_Node
{
int adjvex; //邻接点在向量表中的位置
struct Arc_Node *nextarc;
int weight; //权
}Arc_Node;
typedef struct Vertex_Node
{
Vertex_Type data;
Arc_Node *firstarc;
}Vertex_Node;
typedef struct
{
Vertex_Node vexs[MAX_VERTEX_NUM];//顶点向量
int vexnum; //顶点数
int arcnum;
Graph_Kind kind;
}ALGraph;
typedef struct QNode//队列的定义
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
///////////////////////////队列的操作函数的定义
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q->front)
exit(0);
Q->front->next=NULL;
}
void DestoryQueue(LinkQueue *Q)
{
while(Q->front)
{
Q->rear=Q->front->next;
free(Q->front);
Q->front=Q->rear;
}
}
void EnQueue(LinkQueue *Q,int e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)
exit(0);
p->data=e; //说明这个结点的两个域1
p->next=NULL;//2
Q->rear->next=p;
Q->rear=p;
}
void DeQueue(LinkQueue *Q,int *e)
{
QueuePtr p;
if(Q->front==Q->rear)
exit(0);
p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
}
int QueueEmpty(LinkQueue *Q)
{
if(Q->front==Q->rear)
return(0);
else
return(1);
}
//初始化图中的有关信息
void Init_ALGraph(ALGraph &G)
{
printf("输入图的类型(DG:1 UDG:2):");
//cin>>G.kind;
scanf("%S",&G.kind);
cout<<"输入图的顶点数:";
cin>>G.vexnum;
cout<<"输入图的边数:";
cin>>G.arcnum;
int i;
cout<<"输入定点值:";
for(i=0;i<G.vexnum;++i)
{
cin>>G.vexs[i].data;
G.vexs[i].firstarc=NULL;
}
}
//获取定点在向量中的位置 如果出错就终止运行
int Get_Vertex_Location(ALGraph G,Vertex_Type v)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(v,G.vexs[i].data)==0)
return i;
exit(0);
}
void Greate_ALGraph(ALGraph &G)
{
Init_ALGraph(G);
Vertex_Type v1,v2;
int i,m,n;
cout<<"输入图形的边数:";
for(i=0;i<G.arcnum;++i) //输入并构造邻接表
{
cin>>v1>>v2;
m=Get_Vertex_Location(G,v1); //确定i和j在G中位置，即顶点的序号
n=Get_Vertex_Location(G,v2);
Arc_Node *p1,*p2;
p1=(Arc_Node*)malloc(sizeof(Arc_Node));
p1->adjvex=n; //对弧结点赋邻接点位置信息
p1->nextarc=G.vexs[i].firstarc;
G.vexs[i].firstarc=p1;
switch(G.kind)
{
case DG:
break;
case UDG:
p2=(Arc_Node*)malloc(sizeof(Arc_Node));
p2->adjvex=m;
p2->nextarc=G.vexs[n].firstarc;
G.vexs[n].firstarc=p2; //头插入
break;
}
}
}
void DFSTraverse(ALGraph G, bool *&visited, int i)
{
visited[i]=true;
Arc_Node *p;
cout << G.vexs[i].data << ' ';/*输出访问点*/
// printf("%s ", G.vertices[i].data);
p = G.vexs[i].firstarc;
while(p!=NULL)
{
int j=p->adjvex;
if(!visited[j])
{
DFSTraverse(G,visited,j);
}
p=p->nextarc;
}
}
void BFSTraverse(ALGraph G,bool *&visited,int i)
{
int u; //接受队列中弹出的元素值
Arc_Node *p;
LinkQueue Q; //结构体类型
for(i=1;i<=G.vexnum;++i)
visited[i]=false;
InitQueue(&Q);
for(i;i<=G.vexnum;++i)
{
if(!visited[i])
{ visited[i]=true; //标识它
printf("%d",G.vexs[i].data); //访问第v个结点
EnQueue(&Q,i);//结点的编号进队列
while(!QueueEmpty(&Q))
{
DeQueue(&Q,&u);
for(p=G.vexs[u].firstarc;p!=NULL;p=p->nextarc)
if(!visited[p->adjvex]) //p为u的存储有（尚未访问的邻接顶点）的结构体指针,p->adjvex即为尚未访问的邻接顶点
visited[p->adjvex]=true;
EnQueue(&Q,p->adjvex);
}
}
}
}
void Print_ALGraph(ALGraph G)
{
int i;
for(i=0;i<G.vexnum;++i)
{
Arc_Node *p=G.vexs[i].firstarc;
while(p)
{
switch(G.kind)
{
case UDG:
cout<<G.vexs[i].data<<"--";
cout<<G.vexs[p->adjvex].data;
break;
case DG:
cout<<G.vexs[i].data<<"--";
cout<<G.vexs[p->adjvex].data<<endl;
break;
}
p=p->nextarc;
}
}
}
int main()
{
ALGraph G;
int i;
Greate_ALGraph( G );
Print_ALGraph( G );
bool *visited = new bool[G.vexnum];/*定义定点是否访问过的标志数组 TRUE 表示访问过 否则false*/
cout<<"图的深度优先遍历序列:"<<endl;
for(i=0; i<G.vexnum; ++i) /*初始化访问标志数组 为未访问值*/
visited[i] = false;
DFSTraverse(G, visited, 1);
cout << endl;
cout<<"图的广度优先遍历序列:"<<endl;
for(i=0; i<G.vexnum; ++i)
visited[i] = false;
BFSTraverse( G,visited,1);
return 0;
}
