从这篇博客开始便到了图结构的代码部分，对于图相关的代码，以深度优先和广度优先遍历等等算法为主。下面我们先对广度优先遍历算法进行介绍。
广度优先算法介绍
1、图结构表示
- 在介绍图相关的代码之前，对于图的图形表示方法进行介绍，
- 其主要以邻接矩阵和邻接表两种方式对图进行表示。
- 下面是例子图，主要以邻接矩阵方式实现：
其中邻接矩阵的画法主要包括下面的步骤： - 观察图中是否存在指向自身的环路，也就是1---->1，这样的自循环的结点；
- 若存在则在矩阵的对角线的相应位置置1，若无则置0；
- 根据图中的无向图的设计原则，在邻接矩阵中的相应的对称位置进行置1操作；
- 重复上述过程，便会实现上述的图形的邻接矩阵；
在对上述的图结构进行表示完成后，我们对其进行结构体的代码设计，方便后续对广度优先遍历进行设计。
2、图结构体
对于图的结构体主要包括：顶点集、权值声明、邻接矩阵表示等要素组成，下面是结构体的代码：
typedef int EdgeType;//声明
//图结构
typedef struct {
int adj;//代表权值是否存在，这里以整形数据代替数值为0和1
char * info;//权值具体数值
int vexnum; //代表顶点数
int arcnum;//代表图的边数
//邻接矩阵
EdgeType arc[MAXSIZE][MAXSIZE];
}Graph;
在完成图结构体的声明后，进行最后一项的准备工作----回顾二叉树层次遍历算法的非递归实现方式。
3、二叉树的层序遍历算法非递归实现（回顾）
至于为什么要回顾二叉树的非递归实现层次遍历算法呢，是因为图结构的广度优先遍历便是建立在二叉树的层次遍历实现的基础上，同样需要借助一个数据结构-----队列。 层次遍历非递归代码–最后一题
下面是对二叉树的层次遍历算法进行回顾：
typedef struct TNode{
ElemType data;
struct TNode* lchild, *rchild;
}TNODE,*BiTree;
//层次遍历代码
void BehindTraverse(BiTree root){
if(root == NULL){
return ;
}
InitQueue(Q);//初始化队列
TNODE *p;
//根节点如队列
EnterQueue(Q,root);
while(!isEmpty(Q)){
DeQueue(Q,p);//出队列
visit(p->data);//访问数据
//有左子树入队列
if(p->lchild != NULL){
EnterQueue(Q,p->lchild);
}
//右子树入队列
if(p->rchild != NULL){
EnterQueue(Q,p->rchild);
}
}
}
当前的准备工作就绪了，下面是让我们来介绍下图的广度优先遍历算法
4、广度优先遍历算法介绍
要点：
- 需要一个数据结构—队列；
- 找到与第一个顶点相邻的顶点；
- 标记哪些顶点被访问过；
- 需要声明图的基本操作：
1、FirstAdjVex（G，v）表示图G中的顶点的第一个临界点，若存在，则返回顶点的序号，若不存在或者图中不存在则返回-1；
2、NextAdjvex(G,v,w)：除v外的，下一个邻接点W存在，则返回序列号，若不存在，则返回-1；
对于第一个函数FirstAdjVex，可以理解为，找到与当前传入的结点第一个相邻的结点的序号，至于如何实现这个函数，先看下图：
这里我们举例，以顶点2为例子，可以看到图中的矩阵的第二行的数值为
1 0 1 0 1，在调用FirstAdjVex函数后，返回的数值必然是从一列向后找，第一个出现1的位置结点，因此返回1，这里代表第一个与节点2相连的节点的序号。
在理解了上述的FirstAdjVex函数的实现原理后，对于代码的编写也就不难了
//FirstAdjVex函数，找到当前传入节点的第一个节点并返回
void FirstAdjVex(Graph G,int v){//代表传入的第一个节点
int i;
//这里的i表示第1到5列
for(i = 1;i<=G.vexnum;i++){//进行列循环
if(G.arc[v][i].adj != 0){
//找到第一个不为0的节点，在矩阵中
return i;
}
}
return -1;//若没有找到则返回-1
}
在对FirstAdjVex函数进行算法实现后， 下面是对NextAdjvex(G,V，W)函数进行实现，其实现操作先看下图：
其实现的方式是去查找当前的传入的坐标的后边的第一个相连的节点，给出的操作代码如下：
//找到后继的第一个相连节点
void NextAdjvex(Graph G,int v,int w){
int i;
//因为传的下标节点为(v,w)，
//要找w后的第一个相连节点，因此需要从w+1开始寻找
for(i = w+1;i<=G.vexnum;i++){
//若相连，则返回
if(G.arc[v][i].adj == 1){
return i;
}
}
return -1;//若未找到则返回-1
}
在对上述的代码进行准备工作完成后，对BFS代码进行算法思路表述：
- 申请一个数组，用来对访问节点的是否已访问情况进行标记；
- 申请一个队列进行存放访问元素；
- 传入的节点，首先访问，并入队列；
- 对队列的情况进行判断：
- 若不为空，则出队列，并对当前的出队节点的相连节点进行查找；
- 查找完毕，查找的节点依次入队列；
- 重复上述过程。
结合上述的思路，其逻辑执行图如下：
结合上述的分析思路，给出BFS的实现代码：
//广度优先遍历
#define MAXSIZE 5
int visit[MAXSIZE];//新建标记数组
InitQueue(Q);//初始化队列
void BFS(Graph G,int v){
int w;
visit(v);//对v节点进行访问标记
visit[v] = 1;
EnQueue(Q,v);//入队列
while(! isEmpty(Q)){
DeQueue(Q,v);//出队列
//从 FirstAdjVex(G,v)开始，找到第一个相连的节点，
//到NextAdjvex函数为止，找到最后一个相连的节点
for(w = FirstAdjVex(G,v); w >= 0; w = NextAdjvex(G,v,w)){
if(visit[w] == 0){//若当前找到的节点，还没有被访问过，未被访问置1
visit(w);//对查找到的节点进行访问
visit[w] = 1;//进行访问
EnQueue(Q,w);//入队列
}
}
}
}
针对上述的BFS分析代码，进行代码整合，对广度优先遍历算法的完整实现，如下：
完整代码
#define MAXSIZE 5
int visit[MAXSIZE];//新建标记数组
InitQueue(Q);//初始化队列
//结构体
typedef int EdgeType;//声明
//图结构
typedef struct {
int adj;//代表权值是否存在，这里以整形数据代替数值为0和1
char * info;//权值具体数值
int vexnum; //代表顶点数
int arcnum;//代表图的边数
//邻接矩阵
EdgeType arc[MAXSIZE][MAXSIZE];
}Graph;
//FirstAdjVex函数，找到当前传入节点的第一个节点并返回
void FirstAdjVex(Graph G,int v){//代表传入的第一个节点
int i;
//这里的i表示第1到5列
for(i = 1;i<=G.vexnum;i++){//进行列循环
if(G.arc[v][i].adj != 0){
//找到第一个不为0的节点，在矩阵中
return i;
}
}
return -1;//若没有找到则返回-1
}
//找到后继的第一个相连节点
void NextAdjvex(Graph G,int v,int w){
int i;
//因为传的下标节点为(v,w)，
//要找w后的第一个相连节点，因此需要从w+1开始寻找
for(i = w+1;i<=G.vexnum;i++){
//若相连，则返回
if(G.arc[v][i].adj == 1){
return i;
}
}
return -1;//若未找到则返回-1
}
//广度优先遍历
void BFS(Graph G,int v){
int w;
visit(v);//对v节点进行访问标记
visit[v] = 1;
EnQueue(Q,v);//入队列
while(! isEmpty(Q)){
DeQueue(Q,v);//出队列
//从 FirstAdjVex(G,v)开始，找到第一个相连的节点，
//到NextAdjvex函数为止，找到最后一个相连的节点
for(w = FirstAdjVex(G,v); w >= 0; w = NextAdjvex(G,v,w)){
//这里的 w>=0 的限制条件便是对上述的两个函数返回值为-1的处理，
if(visit[w] == 0){//若当前找到的节点，还没有被访问过，未被访问置1
visit(w);//对查找到的节点进行访问
visit[w] = 1;//进行访问
EnQueue(Q,w);//入队列
}
}
}
}
上述就是对BFS进行的讲解，有不足之处还请大佬在评论区指出，嘿嘿，谢谢，一起学习！
