用C++实现的无向图广度优先遍历

用

C++

实现的实现无向图的广度优先遍历

#include

#include

using namespace std;

//

图的邻接表存储表示

#define MAX_NAME 5 //

顶点字符串的最大长度

#define MAX_VERTEX_NUM 20

typedef char VertexType[MAX_NAME];

typedef struct ArcNode{ //

表结点

int adjvex;

struct ArcNode *nextarc;

int *info;

}ArcNode;

typedef struct VNode{ //

头结点

VertexType data;

ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{ //

图

AdjList vertices;

int vexnum,arcnum;

string kind;

}ALGraph;

队列的链式存储结构

P61(

元素类型为整形

)

typedef struct QNode

{

int data;

struct QNode *next;

}QNode,*QueuePtr;

typedef struct

{

QueuePtr front;//

队头指针

QueuePtr rear; //

队尾指针

}LinkQueue;

int InitQueue(LinkQueue &Q)//

构造一个空队列

{

==(QueuePtr)malloc(sizeof(QNode));

if(!) exit(-1);//

存储分配失败

->next=NULL;

return 1;

}

bool QueueEmpty(LinkQueue Q)//

判空

{

if(==)

return true;

return false;

}

int EnQueue(LinkQueue &Q,int e)//

队列的插入（尾）

{

QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode));

if(!p) exit(-1); //

存储分配失败

p->data=e;

p->next=NULL;

->next=p;

=p;//

尾指针后移

return 1;

}

int DeQueue(LinkQueue &Q,int &e)//

队列的删除（首）

{

QueuePtr p;

if(==)

return 0;//

队列空，返回

0

p=->next;

e=p->data;

->next=p->next;

if(==p)

=; //

尾指针回送

free(p);

return 1;

}

int LocateVex(ALGraph G,VertexType u)

//

返回顶点在图中的位置，无则返回

-1

{

for(int i=0;i

.vexnum;++i)

if(strcmp(u,G

.ve rtices[i].data)==0)

return i;

return -1;

}

int CreateGraph(ALGraph &G)

{

int w; //

权值

VertexType va;

VertexType vb;

ArcNode *p;

cout <<

请输入图的类型

(DG

.