[What]数据结构与算法 -> 图

课程:王争 –> <数据结构与算法之美>

之前在 <算法图解> 对有个简单的理解,这次再来加深一下。

图的概念

graph.jpg

图的存储

邻接矩阵(Adjacency Matrix)

邻接矩阵使用二维数组的方式存储连接关系:

  • 对于无权重无向图来说: 若顶点i与j有边,则A[i][j] 和 A[j][i] 设为1
  • 对于无权重有向图来说: 若顶点i指向j,但顶点j不指向i,则仅将 A[i][j] 设为1
  • 对于有权重图来说: 则将对应边设为权重值即可
adj_save.jpg

优点:

  1. 基础数组存储,其操作效率高
  2. 方便使用矩阵运算来计算图

缺点:

  1. 无向图重复存储了一对关系,浪费空间
  2. 当顶点的边比较少时也很浪费空间

邻接表(Adjacency List)

使用数组和链表存储指向关系:

  • 数组存放顶点,链表表示每个顶点的关系
list_save.jpg

优点:

  1. 节省存储空间

缺点:

  1. 查找效率没有邻接矩阵高

图的搜索

搜索就是指根据一个顶点找到到另一个顶点的路径。

广度优先搜索(Breadth-First-Search, BFS)

方法: 先搜索当前节点的直接连接节点,再搜索其连接节点的直接连接节点,层层扩展。

  • 其目的还是为了得到一个节点到另一个节点的最短路径

时间复杂度

最坏情况下,被搜寻的点在最后,需要遍历整个图才可以找到。

假设顶点个数是V,边数是E,其时间复杂度是O(V+E)

空间复杂度

需要数组来存储顶点以得出遍历路径,所以空间复杂度是O(V)

深度优先搜索(Depth-First-Search, DFS)

方法: 以顶点做起始,不断递归搜寻终点,和走迷宫的方式类似。

  • 此种算法得到的路径并不一定是最短路径

时间复杂度

最坏情况下,每条边被搜寻两次,一次是遍历一次是回退,时间复杂度是O(E)

空间复杂度

仍然需要数组存储顶点,并且其递归深度也不会超过最大顶点数,空间复杂度是O(V)

实践

bfs.jpg

如上图,想从 you 开始搜寻谁有 key ,其最短路径便是绿色路径。

这是我的一个糟糕的示例,对应修改方案是是将图进行一个映射,以数值的方式来执行图的算法。

Last Updated 2019-06-09 日 22:49.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)