无向图

图的概念：

图是算法中树的扩展，树是从上向下的数据结构，结点都有一个父结点(根结点除外)，而图没有父子结点的概念，图中的节点都是平等关系，结果更为复杂。

图的分类：

图可以分为无向图(简单连接)，有向图(连接有方向)，加权图(连接带权值)，加权有向图(连接既有权值又有方向)。下面介绍无向图的表示方法：

邻接矩阵

边的数组

邻接表数组

邻接矩阵：

我们可以使用一个V*V的布尔矩阵graph来表示图，当顶点v与顶点w有边相连时，graph[v][w]和graph[w][v]都为true，反之都为false。但是这种方法占用的空间比较大，因为稀疏图更常见，这就导致了很多空间的浪费。

边的数组：

我们可以使用数组来存放所有的边，这样数组的大小仅为E，但是我们的操作总是要访问某个顶点的相邻节点，对于这种数据类型，要访问某个顶点的相邻节点的话就要遍历整个数组造成效率低下。

邻接表数组：

我们使用一个邻接表数组来表示，数组中每个元素都是链表表头，链表中存放对应下标结点所连接的边。这种数据结构使用的空间为V(顶点数目)+E(边数目)，并且可以相当方便的获取邻接节点。

代码实现：

图的深度优先搜索：

搜索图中所有的结点，就想走迷宫一样，需要探索迷宫中所有的通道，那我们需要做什么呢？

我们需要选择一条没有标记的路，并且一边走一遍铺上绳子

标记走过的路

当走到一个标记的地方时，根据绳子回退到上一个地方

当回退的地方没有可以走的路了就要继续回退

循环往复遍历整个图

我们要用一个数组来标记某个结点是否已经走过了，如果走过了我们就不会再走了。并且我们有一个数组去保存是从哪个结点到达当前结点，这样我们回溯的时候就可以找到一条路径。

图的广度优先搜索：

广度优先搜索并不是先一条路走到黑，而是慢慢的根据距离进行搜索。例如一开始先根据距离为1进行搜索，搜索所有距离为1的点，如果没有找到，再搜索距离为2的点，依次类推。如果我们希望找到一条最短路径，我们应该使用广度优先搜索。