图的概念:
图是算法中树的扩展,树是从上向下的数据结构,结点都有一个父结点(根结点除外),而图没有父子结点的概念,图中的节点都是平等关系,结果更为复杂。
图的分类:
图可以分为无向图(简单连接),有向图(连接有方向),加权图(连接带权值),加权有向图(连接既有权值又有方向)。下面介绍无向图的表示方法:
邻接矩阵
边的数组
邻接表数组
邻接矩阵:
我们可以使用一个V*V的布尔矩阵graph来表示图,当顶点v与顶点w有边相连时,graph[v][w]和graph[w][v]都为true,反之都为false。但是这种方法占用的空间比较大,因为稀疏图更常见,这就导致了很多空间的浪费。
边的数组:
我们可以使用数组来存放所有的边,这样数组的大小仅为E,但是我们的操作总是要访问某个顶点的相邻节点,对于这种数据类型,要访问某个顶点的相邻节点的话就要遍历整个数组造成效率低下。
邻接表数组:
我们使用一个邻接表数组来表示,数组中每个元素都是链表表头,链表中存放对应下标结点所连接的边。这种数据结构使用的空间为V(顶点数目)+E(边数目),并且可以相当方便的获取邻接节点。
代码实现:
图的深度优先搜索:
搜索图中所有的结点,就想走迷宫一样,需要探索迷宫中所有的通道,那我们需要做什么呢?
我们需要选择一条没有标记的路,并且一边走一遍铺上绳子
标记走过的路
当走到一个标记的地方时,根据绳子回退到上一个地方
当回退的地方没有可以走的路了就要继续回退
循环往复遍历整个图
我们要用一个数组来标记某个结点是否已经走过了,如果走过了我们就不会再走了。并且我们有一个数组去保存是从哪个结点到达当前结点,这样我们回溯的时候就可以找到一条路径。
图的广度优先搜索:
广度优先搜索并不是先一条路走到黑,而是慢慢的根据距离进行搜索。例如一开始先根据距离为1进行搜索,搜索所有距离为1的点,如果没有找到,再搜索距离为2的点,依次类推。如果我们希望找到一条最短路径,我们应该使用广度优先搜索。
领取专属 10元无门槛券
私享最新 技术干货