目录
4.3.1 深度优先方法 DFS（Depth First Search）
4.3.2 广度优先 BFS（Breadth First Search）
7.树
7.1 特性
7.1.1 什么是树
树(Tree)是(n>=0)个节点的有限集合T，它满足两个条件：
(1) 有且仅有一个特定的称为根（Root）的节点。
- 其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树（Subtree）。
树的特性：层次关系，一对多，每个节点最多有一个前驱，但是可以有多个后继(根节点无前驱，叶节点无后继)。
关于树的节点：和链表类似，树存储结构中也将存储的各个元素称为 "结点"。
7.1.2 关于树的一些术语
- 度数：一个节点的子树的个数 （一个节点有几个孩子为该节点度数）
- 树度数：树中节点的最大度数
- 叶节点或终端节点: 度数为零的节点
- 分支节点：度数不为零的节点 （A B C D E H）
- 内部节点：除根节点以外的分支节点 （去掉根和叶子）
- 节点层次: 根节点的层次为1，根节点子树的根为第2层，以此类推
- 树的深度或高度: 树中所有节点层次的最大值
7.2 二叉树
最多只有俩孩子的树，并且分为左孩子和右孩子。
7.2.1 什么是二叉树
二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0）， 或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。
7.2.2 二叉树性质（重点）
- 二叉树第k（k>=1）层上的节点最多为2的k-1次幂 // 2^(k-1)
- 深度为k（k>=1）的二叉树最多有2的k次幂-1个节点。//满二叉树的时候
做多的节点数 2^k-1
- 在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。
设度数为0的节点数为n0，度数为1的节点数为n1以及度数为2的节点数为n2，则：
总节点数为各类节点之和: n = n0 + n1+ n2
总节点数为所有子节点数加一：n = n0*0 + n1*1 + n2*2 + 1
下面式子减上面式子得： 0 = -n0 + n2 +1 ==> n0 = n2 + 1
7.2.3 满二叉树和完全二叉树
满二叉树: 深度为k（k>=1）时节点数为2^k - 1(2的k次幂-1)
完全二叉树: 只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。(先挂树的左边向右, 从上向下挂)
7.2.4 二叉树的存储结构
1. 二叉树的顺序存储结构
顺序存储结构 ：完全二叉树节点的编号方法是从上到下，从左到右，根节点为1号节点。设完全二叉树的节点数为n，某节点编号为i：
- 当i>1（不是根节点）时，有父节点，其父节点编号为i/2;
- 当2*i<=n时，有左孩子，其编号为2*i ,否则没有左孩子，本身是叶节点;
- 当2*i+1<=n时，有右孩子，其编号为2*i+1 ,否则没有右孩子；
有n个节点的完全二叉树可以用有n+1 个元素的数组进行顺序存储，节点号和数组下标一一对应，下标为零的元素不用。
利用以上特性，可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚节点构成完全二叉树，然后用数组存储，
2. 二叉树的遍历（重点）
前序： 根 ----> 左 -----> 右
中序: 左 ----> 根 -----> 右
后序: 左 ----> 右 -----> 根
例如：
前序: A B C D E F G H K
中序：B D C A E H G K F
后序：D C B H K G F E A
练习：
已知遍历结果如下，试画出对应的二叉树。
前序: A B C E H F I J D G K
中序：A H E C I F J B D K G
提示：用前序确定根节点，然后用中序找到根节点然后再找左右子。
练习：
(2) 深度为8的二叉树，其最多有( 2^8-1 ) 个节点，第8层最多有( 2^7 )个节点
(网易)
(3) 数据结构中，沿着某条路线，一次对树中每个节点做一次且仅做一次访问，对二叉树的节点从1开始进行连续编号，要求每个节点的编号大于其左、右孩子的编号，同一节点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号(网易)
A 先序 B 中序 C 后序 D 从根开始层次遍历
(4)一颗二叉树的 前序： A B D E C F, 中序：B D A E F C 问树的深度是 ( ) (网易)
A 3 B 4 C 5 D 6
7.3 二叉树的链式存储
用链表实现，基于完全二叉树规律来构建树，按照完全二叉树的编号方法，从上到下，从左到右。一共n个节点。
第i个节点：
左子节点编号：2*i （2*i<=n）
右子节点编号：2*i+1 (2*i+1<=n)
可以根据左右节点编号来判断是否对二叉树构建完成
代码实现：
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data; //数据域存数据
struct node *lchild; //左子
struct node *rchild; //右子
} node_t, *node_p;
//创建二叉树,用递归函数创建
node_p CreateBitree(int n, int i) //i 根节点的编号，n：节点数
{
//创建根节点
node_p r = (node_p)malloc(sizeof(node_t));
if (NULL == r)
{
perror("r malloc err");
return NULL;
}
//初始化根节点
r->data = i;
if (2 * i <= n)
r->lchild = CreateBitree(n, 2 * i);
else
r->lchild = NULL;
if (2 * i + 1 <= n)
r->rchild = CreateBitree(n, 2 * i + 1);
else
r->rchild = NULL;
return r;
}
//前序
void PreOrder(node_p r)
{
if (NULL == r)
return; //直接结束函数无返回值
printf("%d ", r->data); //根
if (r->lchild != NULL)
PreOrder(r->lchild); //左
if (r->rchild != NULL)
PreOrder(r->rchild); //右
}
//中序
void InOrder(node_p r)
{
if (NULL == r)
return; //直接结束函数无返回值
if (r->lchild != NULL)
InOrder(r->lchild); //左
printf("%d ", r->data); //根
if (r->rchild != NULL)
InOrder(r->rchild); //右
}
//后序
void PostOrder(node_p r)
{
if (NULL == r)
return; //直接结束函数无返回值
if (r->lchild != NULL)
PostOrder(r->lchild); //左
if (r->rchild != NULL)
PostOrder(r->rchild); //右
printf("%d ", r->data); //根
}
int main(int argc, char const *argv[])
{
node_p root = CreateBitree(5, 1);
PreOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
return 0;
}
7.4 层次遍历
层次遍历（队列思想）一定要懂
补充（面试可能会遇到）：
哈夫曼树 Huffman
哈夫曼树又称为最优树.
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
先明确以下概念：
1、路径和路径长度
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。
2、结点的权及带权路径长度
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
3、树的带权路径长度
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。（
Weighted Path Length of Tree）
WPL=2*2+5*2+7*1=21
哈夫曼树的构造：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
例如：对 2，3，4，8 这四个数进行构造：
第一步：
第二步：
第三步：
图
1.什么是图
图结构常用来存储逻辑关系为“多对多”的数据。比如说，一个学生可以同时选择多门课程，而一门课程可以同时被多名学生选择，学生和课程之间的逻辑关系就是“多对多“。或者说之前学习的田径比赛的例子，一个人进行好几种比赛，而每个比赛也会被好几个人进行，那么田径比赛和人的关系就是多对多。
再举个例子，{V1, V2, V3, V4} 中各个元素之间具有的逻辑关系如下图所示：
2.图的基本概念
1. 弧头和弧尾
有向图中，无箭头一端的顶点通常被称为"初始点"或"弧尾"，箭头一端的顶点被称为"终端点"或"弧头"。
2. 入度和出度
对于有向图中的一个顶点 V 来说，箭头指向 V 的弧的数量为 V 的入度（InDegree，记为 ID(V)）；箭头远离 V 的弧的数量为 V 的出度（OutDegree，记为OD(V)）。拿图 2 中的顶点 V1来说，该顶点的入度为 1，出度为 2，该顶点的度为 3。
3. (V1,V2) 和 <V1,V2> 的区别
无向图中描述两顶点 V1 和 V2 之间的关系可以用 (V1, V2) 来表示；有向图中描述从 V1 到 V2 的"单向"关系可以用 <V1,V2> 来表示。
由于图存储结构中顶点之间的关系是用线来表示的，因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线，又称为边；同样，<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线，又称为弧。
4.集合 VR
并且，图中习惯用 VR 表示图中所有顶点之间关系的集合。例如，图 1 中无向图的集合 VR={(v1,v2),(v1,v4),(v1,v3),(v3,v4)}，图 2 中有向图的集合 VR={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。
5.路径和回路
无论是无向图还是有向图，从一个顶点到另一顶点途经的所有顶点组成的序列（包含这两个顶点），称为一条路径。如果路径中第一个顶点和最后一个顶点相同，则此路径称为"回路"（或"环"）。
在此基础上，若路径中各顶点都不重复，此路径被称为"简单路径"；若回路中的顶点互不重复，此回路被称为"简单回路"（或简单环）。拿上图来说，从 V1 存在一条路径还可以回到 V1，此路径为 {V1,V3,V4,V1}，这是一个回路（环），而且还是一个简单回路（简单环）。在有向图中，每条路径或回路都是有方向的。
6.权和网
有些场景中，可能会为图中的每条边赋予一个实数表示一定的含义，这种与边（或弧）相匹配的实数被称为"权"，而带权的图通常称为网。例如，下图就是一个带权的网结构：
7. 子图
指的是由图中一部分顶点和边构成的图，称为原图的子图。
3.图的分类
根据不同的特征，图又可细分为完全图，连通图、稀疏图和稠密图：
完全图：若图中各个顶点都与除自身外的其他顶点有直接关系，这样的无向图称为完全图（如图 5a)）。同时，满足此条件的有向图则称为有向完全图（图 5b)）。
上图完全图具有 n 个顶点的完全图，图中边的数量为 n(n-1)/2；而对于具有 n 个顶点的有向完全图，图中弧的数量为 n(n-1)。
稀疏图和稠密图：这两种图是相对存在的，即如果图中具有很少的边（或弧），此图就称为"稀疏图"；反之，则称此图为"稠密图"。稀疏和稠密的判断条件是：e<nlogn，其中 e 表示图中边（或弧）的数量，n 表示图中顶点的数量。如果式子成立，则为稀疏图；反之为稠密图。
3.1 连通图
3.1.1 什么是连通图
前面讲过，图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的。例如下图中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径，分别是 V1-V2-V3 和 V1-V4-V3，因此称 V1 和 V3 之间是连通的。
上图是顶点之间的连通状态示意图
在无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。例如下图中的无向图就是一个连通图，因为此图中任意两顶点之间都是连通的。
连通图示意图
若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量。
前面讲过，由图中部分顶点和边构成的图为该图的一个子图，但这里的子图指的是图中"最大"的连通子图（也称"极大连通子图"）。
如下图所示，虽然图 a) 中的无向图不是连通图，但可以将其分解为 3 个"最大子图"，图b)，它们都满足连通图的性质，因此都是连通分量。
3.1.2 强连通图
有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图。下图所示就是一个强连通图。
与此同时，若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。
如图 所示，整个有向图虽不是强连通图，但其含有两个强连通分量。
可以这样说，连通图是在无向图的基础上对图中顶点之间的连通做了更高的要求，而强连通图是在有向图的基础上对图中顶点的连通做了更高的要求。
3.2 生成树
在学习连通图的基础上，本节学习什么是生成树，以及什么是生成森林。
对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。
图中连通图及其对应的生成树
如图所示，图a) 是一张连通图，图 b) 是其对应的 2 种生成树。
连通图中，由于任意两顶点之间可能含有多条通路，遍历连通图的方式有多种，往往一张连通图可能有多种不同的生成树与之对应。
- 连通图中的生成树必须满足以下 2 个条件：包含连通图中所有的顶点。
- 任意两顶点之间有且仅有一条通路。
因此，连通图的生成树具有这样的特征，即生成树中边的数量 = 顶点数 - 1。
4.图的存储
4.1 图的顺序存储
4.1.1 特性
使用图结构表示的数据元素之间虽然具有“多对多”的关系，但是同样可以采用顺序存储，也就是使用数组有效地存储图。
使用数组存储图时，需要使用两个数组，一个数组存放图中顶点本身的数据（一维数组），另外一个数组用于存储各顶点之间的关系（二维数组）。
存储图中各顶点本身数据，使用一维数组就足够了；存储顶点之间的关系时，要记录每个顶点和其它所有顶点之间的关系，所以需要使用二维数组。
不同类型的图，存储的方式略有不同，根据图有无权，可以将图划分为两大类：图和网 。
图，包括无向图和有向图；网，是指带权的图，包括无向网和有向网。存储方式的不同，指的是：在使用二维数组存储图中顶点之间的关系时，如果顶点之间存在边或弧，在相应位置用 1 表示，反之用 0 表示；如果使用二维数组存储网中顶点之间的关系，顶点之间如果有边或者弧的存在，在数组的相应位置存储其权值；反之用 0 表示。
图中是有向图和无向图
例如，存储图中的无向图（B）时，除了存储图中各顶点本身具有的数据外，还需要使用二维数组存储任意两个顶点之间的关系。
由于 （B） 为无向图，各顶点没有权值，所以如果两顶点之间有关联，相应位置记为 1 ；反之记为 0 。构建的二维数组R如下图所示。
图中无向图对应的二维数组R
在此二维数组中，每一行代表一个顶点，依次从 V1 到 V5 ，每一列也是如此。比如 R[0][1] = 1 ，表示 V1 和 V2 之间有边存在；而 arcs[0][2] = 0，说明 V1 和 V3 之间没有边。
对于无向图来说，二维数组构建的二阶矩阵，实际上是对称矩阵，在存储时就可以采用压缩存储的方式存储下三角或者上三角。
通过二阶矩阵，可以直观地判断出各个顶点的度，为该行（或该列）非 0 值的和。例如，第一行有两个 1，说明 V1 有两个边，所以度为 2。
存储图 1 中的有向图（A）时，对应的二维数组如下图所示：
4.1.2 代码实现
//有向图和无向图
#include <stdio.h>
#include <string.h>
#define N 5
typedef struct
{
int V[N];
int R[N][N];
}adjmatrix_t;
int main(int argc, const char *argv[])
{
adjmatrix_t graph;
int i,j;
//1.初始顶点集合
for(i = 0; i < N; i++)
graph.V[i] = i;
//2.将关系集合清空置0，然后输入顶点之间的关系
bzero(graph.R,sizeof(graph.R));
printf("请您输入顶点关系:\n");
while(scanf("(V%d,V%d) ",&i,&j) == 2)//scanf函数，如果输入i j两个值成功，返回值为 2代表输入成功有两个，如果不成功为EOF
{
graph.R[i][j] = 1;//vi --> vj
graph.R[j][i] = 1;//vj --> vi 如何将此行代码注销，可用表示有向图
}
//3.打印图
for(i = 0; i < N; i++)
{
printf("V%d:",graph.V[i]);
for(j = 0; j < N; j++)
{
if(graph.R[i][j] == 1)// == 1说明vi ---> vj
{
printf("V%d ",graph.V[j]);//将Vi 所有能到达的顶点Vj打印
}
}
printf("\n");
}
return 0;
}
//scanf输入
(V0,V1) (V0,V2) (V1,V4) (V2,V1) (V2,V3) (V3,V0) (V4,V3) -14.2 图的邻接表存储
邻接表（Adjacency List）是图的一种链式存储结构，可以存储无向图或有向图。
邻接表存储图的核心思想是：将图中的所有顶点存储到顺序表或链表中，同时为各个顶点配备一个单链表，用来存储和当前顶点有直接关联的边或者弧（边的一端是该顶点或者弧的弧尾是该顶点）。
举个简单的例子，下图是一张有向图和它对应的邻接表：
图中是有向图和它对应的邻接表
以顶点 V0 为例，它对应的单链表中有两个结点，存储的值分别是 1 和 2。2是 V2 顶点在顺序表中的位置下标，存储 2 的结点就表示 <V1, V2> 这条弧。同理，1 是 V1 顶点在顺序表中的位置下标，存储 1 的结点就表示 <V0, V1> 这条弧。
也就是说，邻接表中存储边或弧的方法，就是存储边或弧另一端顶点在顺序表中的位置下标。
//有向图和无向图
#include <stdio.h>
#include <stdlib.h>
#define N 5 //5代表5个顶点
typedef struct node_t
{
int vertex;//保存顶点
struct node_t *next;//指向下一个节点的指针
}adjlist_node_t;
//画边函数，也就是将顶点vj插入到对应的链表vi中 draw 画 edge边
void drawEdge(adjlist_node_t *vi, int vj)//vi代表的是对应链表的头结点的指针
{//在插入的时候对其进行排序同霍夫曼树插入根据权值排序思想一样
adjlist_node_t *pnew = NULL;
while(vi->next != NULL && vj > vi->next->vertex)
vi = vi->next;
//创建新的节点保存vj
pnew = (adjlist_node_t *)malloc(sizeof(adjlist_node_t));
if(NULL == pnew)
{
perror("pnew malloc failed");
return;
}
//创建pnew后装东西
pnew->vertex = vj;
pnew->next = NULL;
//将节点链接到链表中，先连后面再连前面
pnew->next = vi->next;
vi->next = pnew;
return;
}
int main(int argc, const char *argv[])
{
int i,j;
adjlist_node_t *h = NULL;//用来保存每条链表的头指针(无头)
//1.创建一个结构体数组
adjlist_node_t g[N] = { 0 };
for(i = 0; i < N; i++)
g[i].vertex = i;
printf("请您输入顶点的关系:\n");
//2.输入顶点之间的关系
while(scanf("(V%d,V%d) ",&i,&j) == 2)
{
//将vj这个顶点插入到vi顶点的链表中
drawEdge(g+i,j);//此行等价于 &g[i]
// drawEdge(g+j,i);//如果输入的想代表无向图，将此行代码解除注释
}
//3.将各个顶点所有到达的顶点进行打印
for(i = 0; i < N; i++)
{
printf("V%d:",g[i].vertex);//g[i].vertex 代表的是Vi这个顶点
h = g[i].next;
//相当于遍历无头链表，需要对每一条链表进行遍历
while(h != NULL)
{
printf("V%d ",h->vertex);
h = h->next;
}
printf("\n");//遍历完一条链表后打印一个换行
}
printf("\n---------------\n");
return 0;
}
//scanf输入
//(V0,V1) (V0,V2) (V1,V4) (V2,V1) (V2,V3) (V3,V0) (V4,V3) -14.3 图的搜索方法
4.3.1 深度优先方法 DFS（Depth First Search）
- 所谓深度优先搜索，就是从图中的某个顶点出发，不停的寻找相邻的、尚未访问的顶点：如果找到多个，则任选一个顶点，然后继续从该顶点出发。
- 如果一个都没有找到，则回退到之前访问过的顶点，看看是否有漏掉的。
例如：
4.3.2 广度优先 BFS（Breadth First Search）
简单理解光度优先就是逐个访问图中的顶点，确保每个顶点都只访问一次。
例如：
广度优先搜索算法遍历图
使用广度优先搜索算法，遍历图中无向图的过程是：
1) 初始状态下，图中所有顶点都是尚未访问的，因此任选一个顶点出发，开始遍历整张图。比如从 V1 顶点出发，先访问 V1：
2) 从 V1 出发，可以找到 V2 和 V3，它们都没有被访问，所以访问它们：
3) 根据图 3 中的顶点访问顺序，紧邻 V1 的顶点已经访问过，接下来访问紧邻 V2 的顶点。从 V2 顶点出发，可以找到 V1、V4 和 V5，尚未访问的有 V4 和 V5，因此访问它们：
4) 根据图 4 中的顶点访问顺序，接下来访问紧邻 V3 的顶点。
从 V3 顶点出发，可以找到 V1、V6 和 V7，尚未访问的有 V6 和 V7，因此访问它们：
5) 根据图 5 中的顶点访问顺序，接下来访问紧邻 V4 的顶点。
从 V4 顶点出发，可以找到 V2 和 V8，只有 V8 尚未访问，因此访问它：
6) 根据图 6 的顶点访问顺序，接下来访问紧邻 V5 的顶点。
与 V5 紧邻的 V2 和 V8 都已经访问过，无法再找到尚未访问的顶点。此时，广度优先搜索算法会直接跳过 V5，继续从其它的顶点出发。
7) 广度优先搜索算法先后从 V6、V7、V8 出发，寻找和它们紧邻、尚未访问的顶点，但寻找的结果都和 V5 一样，找不到符合要求的顶点。
8) 自 V8 之后，访问序列中再无其它顶点，意味着从 V1 顶点出发，无法再找到尚未访问的顶点。这种情况下，广度优先搜索算法会从图的所有顶点中重新选择一个尚未访问的顶点，然后从此顶点出发，以同样的思路继续寻找其它尚未访问的顶点。
5.实现图的代码
图的顺序存储的广度和深度搜索实现：
#include "graph.h"
#include "linkqueue.h"
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
//1.创建一个图
adjmatrix_t *createGraph()
{
int i,j;
adjmatrix_t *g = (adjmatrix_t *)malloc(sizeof(adjmatrix_t));
if(NULL == g)
{
perror("createGraph malloc failed");
return NULL;
}
//2.初始化顶点集合
for(i = 0; i < N; i++)
g->V[i] = i;
//清空下关系结合
bzero(g->R,sizeof(g->R));
printf("请您输入顶点的关系(V0,V1):\n");
while(scanf("(V%d,V%d) ",&i,&j) == 2)
{
g->R[i][j] = 1;
g->R[j][i] = 1;
}
return g;
}
//2.获取第一个邻接点 v是被搜索的顶点
int firstAdj(adjmatrix_t *g,int v)//v == 0,找v0第一个邻接点
{
int j;
for(j = 0; j < N; j++)
{
if(g->R[v][j] == 1)
return j;
}
return -1;//代表没有邻接点
}
//int u;//保存v的第一个邻接点
//u = fristAdj(g,0);//得到第一个
//u =====> 1
// u = nextAdj(g,0,u);//下一个
// u = nextAdj(g,0,u);//再下一个
//3.获取下一个邻接点 v被搜索的顶点 u 前一个邻接点
int nextAdj(adjmatrix_t *g, int v, int u)
{
//获取下一个邻接点函数的使用，需要fristAdj函数的配合
int j;
for(j = u+1; j < N; j++)//j = u+1 是因为第一个邻节点是u，那么继续找下一个从u+1位置开始遍历
{
if(g->R[v][j] == 1)
return j;
}
return -1;
}
//4.深度搜索 visited 拜访，访问 v代表的是从那个顶点开始深度搜索
//visited是一个指向整型数组的指针，用来标记这个节点是否被访问
void DFS(adjmatrix_t *g, int v, int *visited)
{//visited[v] == 0代表没被访问， 1代表被访问
int u;//用来保存邻接点
if(visited[v] == 0)//说明该顶点没有被访问
{
printf("V%d ",g->V[v]);//相当于已经被访问了
visited[v] = 1;//将标志位置1，变为已经被访问,已经被打印输出
}
//获取v的第一个邻接点
u = firstAdj(g,v);
while(u != -1)//如果u == -1代表,没有邻接点
{
if(visited[u] == 0)//没有被访问
{
DFS(g,u,visited);
}
u = nextAdj(g,v,u);//获取下一个邻接点
}
}
//5.广度搜索
void BFS(adjmatrix_t *g, int v, int *visited)
{
int u;
//创建一个队列
linkqueue_t *p = createEmptyLinkQueue();
inLinkQueue(p,v);
while(!isEmptyLinkQueue(p))
{
v = outLinkQueue(p);
if(visited[v] == 0)//说明v未被访问
{
printf("V%d ",g->V[v]);
visited[v] = 1;//打印之后标记为已经访问
}
//开始遍历v所有能达到的顶点
u = firstAdj(g,v);
while(u != -1)
{
if(visited[u] == 0)//v到达的顶点没有被访问
{
inLinkQueue(p,u);
}
u = nextAdj(g,v,u);//在上面入列的u基础上，在找到下一个邻接点返回
}
}
}