目录
--------------------------------------目录------------------------------------------
图的定义和术语
图的邻接矩阵构建法
深度优先遍历算法（DFS）
广度优先遍历算法 （BFS）
全部代码
图：G = （V,E) V:顶点的有穷非空集合 E:边的有穷集合
无向图：每条边都是无向的
有向图：每条边都是有方向的
邻接：有边相连的两个顶点之间的关系
想要构建图，则首先得知道图的存储结构，从上图可以看出，我们需要有个数组存储各个顶点的数据，如v1、v2、v3等等。。再者因为我们今天要用邻接矩阵来表示图，所以我们需要个二维数组，再为了方便，我们需要再设两个变量，表示现有的结点与边，可以不难看出是个结构体结构，如下图：
假设我们现在顶点数为5个，边数为5，顶点数据为 a,b,c,d,e，矩阵元素都为无穷，并定义个结构体变量则结构表示出来为：
存储结构知道后，我们就可以对它进行初始化操作啦，而我们的初始化操作，就是对照上图，其中数字，数据都是随机的，根据你的喜好，并且你还可以美化它，这里不多赘述，下面为思想：
1、确定顶点数和边数，
2、给顶点表赋值
3、arr二维数组都初始化为极大值（这里的极大值一般为int的最大值32767，而上图为了美观写成∞）表示现在每个顶点之间都没有线（关系），我们接下来构造就是加线操作而已。
初始化完成后，我们就可以，看看自己邻接矩阵长什么样啦，写一个遍历二维数组的算法（比较简单，这里就不写了），而后就是构造顶点之间的联系，思想就是：
1、先输入两个点（这两个点是邻接的，就是有关系的），并赋予权值，
2、用这两个点去顶点表里去找，找到了返回对应坐标
3、找到坐标后就在矩阵（二维数组）对应下标赋值
4、因为为无向图，则为对称的，所以行列坐标对换后再赋值一遍即可（如为有向图这步省略）
假设我们现在按照 下面这个图来构建邻接矩阵，则结果为：
深度优先算法就是一条路走到黑，走不下去就回来换条路的人性化算法，也是我这种路痴的常用探路的方法。
1、即随机选个顶点，
2、顺着与它有联系的点走下去，发现走不下去了，就回退一个顶点
3、如此如此最后再回退到当初选的第一个点
从步骤看出我们只是要去下一个顶点，然后用相同的方法再去下一个顶点，则我们可以用递归算法，可以用栈写出来（非递归），也可以用本来有的栈来做（递归）
走不下去了，退一格，再去没访问过的顶点，访问过的点不访问。
依次下去，直至最后一个点都访问了，然后顺着原路返回。
实现代码则需要一个辅助数组，这个数组作用是表示这个顶点是否被访问过了没，这里我们用0代表没访问过1反之，既然是递归，我们要有个递归的结束条件，可以不难看出走不下去即为结束条件，这时会有两种情况，一是没有邻接的顶点了，或者是邻接的顶点已经访问过了，那我们根据这个特性就不难写出代码了。
1、随机选个顶点
2、打印这个顶点，并设置为访问过了
3、如果还有邻接的顶点并且未访问过，递归函数
广度优先遍历也是先随机选个点，先让这个点的所有邻接点都访问一遍，然后从第一个访问的点再去访问它所有的邻接点，依次下去，到最后一个点都访问过为至。
那我们要怎么实现这个算法呢，从第二个图那个矩阵内部图结果可以看出，如果我们要使用广度优先遍历的话，救得一次性把第0行的所有邻接点都访问一遍，然后就是第1行，依次下去，那就是说我们就让这些行数排排队，只要每个行都能把邻接点都访问一遍就可以啦。
顺着这个思想，我们就要去想那怎么知道这一行的邻接点呢，答案是我们应该写个函数，去获取第一个邻接点的坐标，然后再写个函数得到下一个邻接点的坐标，直到没有邻接点了，那我们就去访问下一行，那我们怎么去访问下一行呢，上面讲到了排队，所以我们就可以写一个队列，让现在访问的行入队，因为我们知道这个矩阵是个方阵所以行和列是对应的，就是顶点数据对应的行坐标就是顶点数据的列坐标。
举个例子，现在是访问0行的1列那对应的就是顶点数据b这个元素，那我们就把b在矩阵中对应的列下标入列，虽然这是列下标，但是实际上也是数据b在矩阵中对应的行下标，所以我们出队的时候其实就是访问b在矩阵中对应的行下标。
算法步骤：
1、输出随机访问的顶点数据，并让其对应的辅助数组下标置为1
2、让顶点下标入队
3、 队不为空，出队，并把出队元素保存
4、访问第一个邻接点，并打印其顶点数据，然后让其对应的辅助数组下标置为1
5、入队，访问下一邻接点，如此反复直至队空
发这个也是为了理清自己的思路，顺带一起学习下，继续学习咯，加油陌生人！！
学自严老师的教材---------------------------------------------------------------------------------------------------------
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/14612.html