//初始化队列，新建队列
void InitQueue(queue *q)
{
q->rear = new qNode; //新建队列结点，赋予队尾
q->front = q->rear; //空队列的队头与队尾为同一单元
/*
if(q->front == NULL) //分配单元失败
{
cout << "InitQueue Error!" << endl;
exit(1);
}
*/
q->front->nextQNode = NULL; //队头的指向下一结点的指针为空
//因为队首队尾为同一单元，则队尾结点的下一结点指针也为空，即q->rear->nextQNode == NULL
}
//入队，队尾添加
void EnQueue(queue *q, int e) //形参为队列q地址，要添加的新的队列结点的数据域
{
qNode *p = new qNode; //新建结点，并分配内存
/*if(p == NULL ) //若分配内存失败则退出
{
cout << "EnQueue Error!" << endl;
exit(1);
}
*/
p->qVerIndex = e; //新结点的数据域为传入的参数
p->nextQNode = NULL; //新结点指针域为空
q->rear->nextQNode = p; //原队尾指向下一结点的指针指向p
//因为空队的队首与队尾单元相同，则若为空队时，q->front->nexQNode = p
//即空队的 队头的指向下一结点的指针 指向新结点
//若非空队，则对队首不影响
q->rear = p; //p成为新的队尾
//这时，队首q->front仍为第一次初始化时的单元，而队尾则成了新加的结点单元
//队尾的指向下一结点的指针永远指向NULL
}
int QueueEmpty(queue *q) //判断队列是否为空，空则返回1，非空为0
{
return(q->front == q->rear ? 1:0); //判断条件为，队头与队尾为同一单元
}
//出队，队首删除
void DeQueue(queue *q, int *m) //队列q指针传参，m为指针形参，用于保存删除的结点的数据域
{
qNode *p = new qNode; //新建队列结点，用于缓存
if(QueueEmpty(q)) //若为空队列，则报错退出
{
cout << "DeQueue Error!" << endl;
exit(1);
}
p = q->front->nextQNode; //要删除的结点缓存为p
*m = p->qVerIndex; //要删除的结点的数据域放入m所指单元
q->front->nextQNode = p->nextQNode; //队头指向下一结点的指针指向要删除的结点的下一个结点
if(q->front->nextQNode == NULL) //判断是否已经清空队列
{
q->rear = q->front; //若队首指向下一个结点的指针为空，则表明队列已经清空，队首队尾为同一单元
//注：不能写反了
}
free(p); //释放缓存
}
//BFS广度优先搜索
void BFSTraverse(graphList *g, int dist[VerNum][VerNum]) //数组形参，传址，所做修改在函数结束时仍然有效
{
queue q; //定义队列
edgeNode *p = new edgeNode; //定义边表结点类型指针，下面访问各个结点的边表时用到
int index;
/*
此处使用循环来得到所有点相对其他点的最短路径，
若图有未达到的点，需要再设置一个循环来达到遍历所有点的目的，
因为此题中任何点均可以达到其他所有点，不必再设下一循环
*/
for(index=0; index<VerNum; index++)
{
InitQueue(&q); //初始化队列q，每个新的起点都重置一下队列
Boolean visited[VerNum] = {FALSE}; //定义各顶点访问标志，并初始化为FALSE
/*
设置一个层次标志
BFS算法是把图从一个顶点转化为树，并按照距离的远近设置树的层次，
处于同一层次的叶结点与根结点的距离相同
而且根结点与页结点的距离，就是层次数
*/
int level[VerNum][VerNum]; //树的最大度为VerNum（第一个），每层中最大叶结点为VerNum（第二个）
//此数组用于保存每层的各叶子结点
int r1, r2; //数组横下标为r1，纵下标r2
for(r1=0; r1<VerNum; r1++) //初始化层次数组
{
for(r2=0; r2<VerNum; r2++)
{
level[r1][r2] = VerNum; //因为没有VerNum序号的结点，用于判断是否赋值，或作其他用途
}
}