数据结构学习笔记 - 图

ゝ一世哀愁。 2022-11-05 08:32 154阅读 0赞

## 图 ##

### 简介 ###

图是一种非线性表数据结构, 比树更加复杂  
涉及图的算法有很多, 比如图的搜索, 最短路径, 最小生成树, 二分图等

### 图的基本概念 ###

图中的元素叫做**顶点**, 一个顶点可以与任意其他顶点建立连接关系, 这种建立的关系, 叫做**边**  
跟顶点相连接的边的条数, 叫做顶点的**度**  
图的边可以有方向, 边有方向的叫做**有向图**, 边没有方向的叫做**无向图**  
有向图中, 把度分为**入度**和**出度**, 入度表示有多少条边指向这个顶点, 出度表示有多少条边是以这个顶点为起点指向别的顶点  
另一种图, **带权图**, 每条边都有一个权重

### 图的存储 ###

1.  邻接矩阵存储方法  
    图最直观的一种存储方式就是邻接矩阵  
    底层依赖一个二维数组, 对于无向图, 若顶点i到j之前有边, 则A\[i\]\[j\]和A\[j\]\[i\]都标为1, 对于有向图, 若顶点i到j之前有指向j的边, 则A\[i\]\[j\]标为1, 带权图中数组存储相应的权重即可  
    用邻接矩阵来表示一个图, 虽然简单直观, 但是比较浪费存储空间, 如果存储的是稀疏图(顶点非常多), 而每个顶点的边并不多, 则大部分空间都被浪费了  
    优点是存储方式简单, 获取两个顶点的关系时非常高效, 其次是方便计算, 可以将很多图的运算转换成矩阵之间的计算
2.  邻接表存储法  
    邻接表有点像散列表, 每个顶点对应一条链表, 链表中存储的是与这个顶点相连接的其他顶点  
    邻接表存储起来比较节省空间, 但使用起来就比较耗时间, 要查询是否存在一条顶点a到b的边, 就要遍历顶点a的链表  
    为了提高查找效率, 这里的链表也可换成其他更高效的数据结构, 比如平衡二叉查找树, 跳表, 散列表等

### 深度优先和广度优先 ###

深度优先搜索算法和广度优先搜索算法都是基于图这个数据结构的, 因为图的表达能力强, 大部分涉及搜索的场景, 都可以抽象成图  
图上的搜索算法, 最直接的理解就是在图中找出从一个顶点出发到另一个顶点的路径  
其中最简单最暴力的两种搜索就是, **深度优先搜索**和**广度优先搜索**

1.  广度优先搜索(BFS)  
    其实就是一种地毯式层层推进的搜索策略, 先查找离起始顶点最近的, 然后是次近的, 依次往外搜索  
    广度优先搜索需要借助队列来实现  
    广度优先搜索找出来的是最短路径  
    代码示例(todo)
2.  深度优先搜索(DFS)  
    类似走迷宫, 在分叉口随意选择一个节点, 直到走不通再回退  
    深度优先搜索用的是一种比较著名的算法思想, 回溯思想, 借助栈来实现  
    深度优先搜索找出来的不是最短路径  
    代码示例(todo)