算法的基本数据结构-图专题

2022-05-31  本文已影响0人  后厂村村长

图论，Graph[ɡræf] Theory，是数学的一个分支。

图，是由若干给定的点及连接两点的线所构成的图形，通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线代表两个事物间具有这种关系。

图是一种最复杂的数据结构，前面所说的各类数据结构，都可以看作是图的特例，既然如此，直接用图就好，为啥还要分这么多类型？

这是因为，大多时候，我们不需要用到这么复杂的功能，与其称之为图的xx特例，不如干脆分离出来。

数据结构是为算法服务的，其目的是为了更高效地存取数据，那么，什么类型的数据适合用图来存储呢？答案很简单，如果你用其他数据结构无法很好地进行存储，就用图；
举个栗子：如果我们要存储一种双向的朋友关系，并且这种朋友关系是多对多的，那就要用到图，因为其他数据结构无法很好的模拟。

图，分为 无向图（Undirected Graph）& 有向图（Deriected Graph）。

无向图，比如前面提到的二叉树；
有向图，以下重点介绍。

有向图
如果两个事务间的关系是有方向的，就是有向图，反之为无向图；
比如，A认识B，但是B不一定认识A，如果用无向图存储就无法得知到底是A认识B，还是B认识A。

习惯上，我们画图时用箭头标识方向，即，带箭头的为有向图，反之为无向图。

有权图（Weighted Graph）& 无权图（Unweighted Graph）
如果边是有权重的，则为有权图（带权图），反之为无权图（不带权图），该如何理解权重呢？比如，汇率，就是一种有权重的逻辑图。货币A，1个，可以兑换 货币B，7个，那么A和B的边的权重就是7，而上面提到的，朋友关系，这种就属于无权图。

入度（inDegree）&出度（outDegree）
有多少条边指向节点N，那么节点N的入度就是多少；同理，有多少条边从节点N出发，那么节点N的出度就是多少。
如下图所示，所有节点的入度和出度都为 1。

有向图-示例

路径&环

连通图&强连通图

生成树
一个连通图的生成树是指：一个连通子图，虽然包含构成图的全部n个顶点，但却只有构成一棵树的 n-1 条边，并且，有且仅有 n-1 条边，如果生成树再添加一条边，则必定构成环。
在连通图的所有生成树中，所有边的【代价和最小】的生成树，称为最小生成树，代价和，指所有边的 权重和。

图的建立
一般来说，LC中的图相关题目，都不会给你一个现成的图的数据结构，所以，当你意识到这是一个图类型的题目时，解题的第一步通常是，建图。
我们知道，图是由点和边组成的，所以我们只要存储图中的所有边的关系即可，因为边中已经包含了两个点的关系。

两种常见的建图方式：邻接矩阵（常用且重要）& 邻接表

邻接矩阵（Adjacency[ə'dʒeɪsənsɪ] Matrixs）
可以使用数组或哈希表来存储图，这里我们使用二维数组。
用一个 n*n 的矩阵来描述图 graph，其中 graph[i][j] 用来描述边的关系。

一般而言，对于无权图，我们可以使用 graph[i][j] = 1 来表示 顶点 i 和顶点 j 之间有一条边，且边的指向是从 i 到 j；
用 graph[i][j] = 0 来表示 顶点 i 和顶点 j 之间不存在一条边；
对于有权图来说，我们可以存储其他数字，用来表示权重。

邻接矩阵的优点主要有：

典型题目-LC-743. 网络延迟时间：

    // 743. 网络延迟时间
    function networkDelayTime($times, $n, $k) {
        $graph = [];
        foreach ($times as $sub) {
            //建立邻接矩阵：From -  To: time
            $graph[$sub[0]][$sub[1]] = $sub[2];
        }
        $timeCost = $this->dijkstra($graph, $n, $k);
        return $timeCost;
    }
    // dijkstra 不适用于带 负权 的计算；具体见如下代码
    function dijkstra($graph, $n, $k) {
        $got = []; // 已获取的，从 k 到 可到达的目标点 v(包含k自身) 的最短路径集合
        $dist = []; // 从 k 到 目标点 v(包含k自身) 的最短路径的权值，即 网络延迟 的最短时间；
        for ($i=1; $i <= $n; $i++) { 
         $dist[$i] = PHP_INT_MAX; // 初始均设为最大值        }
         $dist[$k] = 0; // k 到达自身的最短时间为 0
        $loopCnt = 0;
        while ($loopCnt < $n) {
            // 本次循环得到的【可到达的】最短路径节点，节点为正数，所以 -1 即可；
            $toNode = -1;
            for ($i=1; $i <= $n; $i++) { 
                if (isset($got[$i])) {
                    // 已获取最短路径的节点，跳过
                    continue;
                }
                if ($toNode == -1 || $dist[$i] < $dist[$toNode]) {
                    $toNode = $i;
                }
            }

            $got[$toNode] = 1; // 标记本次获取的最短路径节点放入大集合，下次不再循环

            // 重新计算并入本次获取的最短路径节点后的到达时间
            for ($i=1; $i <= $n; $i++) {
                if (!isset($graph[$toNode][$i])) {
                    // 如果未设置，则代表 本次获取的节点 不可直接到达 i 节点
                    continue;
                }
                // k 到本次获取的最短节点时间 + 本次节点到 i 的时间，即经过本次节点到 i 的最短时间
                $dist[$i] = min($dist[$i], $graph[$toNode][$i] + $dist[$toNode]);
            }
            $loopCnt++;
        }
        $timeCost = max($dist);
        if ($timeCost == PHP_INT_MAX) {
            return -1;
        }
        return $timeCost;
    }

图的遍历

常见的有两种方法：
深度优先遍历（Depth First Search, DFS）；
广度优先搜索（Breadth First Search, BFS）；
不管是哪种遍历方式， 如果图有环，一定要记录节点的访问情况（visited），防止死循环；
DFS 和 BFS 只是一种算法思想，不属于具体的算法，因此其有着很强的适应性，本文讲的图可以用，前文讲的树也可以用。实际上， 只要是非线性的数据结构都可以借用。

常见算法
图类型的题目比较适合套模板，这里介绍几种常见的板子题。主要有：

Dijkstra
Floyd-Warshall
最小生成树（Kruskal & Prim）
A 星寻路算法
二分图（染色法）〔Bipartitie〕
拓扑排序〔Topological Sort〕

这里简单介绍其中一个经典算法：Dijkstra 算法
Dijkstra 算法，俗称，最短距离 或 最短路径 算法；
Dijkstra 这个名字比较难记，可以简单记为DJ 算法。

基本思想是广度优先遍历。实际上搜索的最短路算法基本思想都是广度优先，只不过具体的扩展策略不同而已；
主要解决的是图中任意一点到图中另外任意一个点的最短距离，即单源最短路径。

比如给你几个城市，以及城市之间的距离。让你规划一条最短的从城市 a 到城市 b 的路线。
这个问题，我们就可以先将城市间的距离用图建立出来，然后使用 dijkstra 来做。

DJ 算法的基本思想是贪心。从起点 start 开始，每次都遍历所有邻居，并从中找到距离最小的，本质上是一种广度优先遍历。这里我们借助堆这种数据结构，使得可以在 logN 的时间内找到 cost 最小的点。

而如果使用普通的队列的话，其实是图中所有边权值都相同的特殊情况。
比如我们要找从点 start 到点 end 的最短距离。我们期望 dj 算法是这样被使用的:
有如下类型的图：

E -- 1 --> B -- 1 --> C -- 1 --> D -- 1 --> F
 \                                         /\
  \                                        ||
    -------- 2 ---------> G ------- 1 ------

构造邻接矩阵：

G = {
    "B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["G", 2]],
    "F": [],
    "G": [["F", 1]],
}
shortDistance = dijkstra(G, "E", "C")
print(shortDistance)  # E -- 3 --> F -- 3 --> C == 6

具体思路：

代码可参考上面的 LC-743. 网络延迟时间；

Floyd-Warshall 算法
算法主要思路很简洁，可以参考数学中的交换律：
如果 a->b 且 b->c，则a->c；
如果 a 能到b，b能到c，则a可以到c；
如果是带权图，则上面的判断逻辑追加条件即可，如果取最小路径，可以加判断：【a->b->c 】< 【a->c 】，再赋值即可。
代码主要逻辑为 3 层循环；
伪代码（JavaScript）：

function floydWarshall (graph, v) {
  const dist = new Array(v).fill(0).map(() => new Array(v).fill(Number.MAX_SAFE_INTEGER));
  for(let i = 0; i < v; i++){
    for(let j = 0; j < v; j++){
      //两个点相同，距离为0
      if(i === j) dist[i][j] = 0;
      //i 和 j 的距离已知
      else if(graph[i][j]) dist[i][j] = graph[i][j];
      //i 和 j 的距离未知，默认是最大值
      else dist[i][j] = Number.MAX_SAFE_INTEGER;
    }
  }

  //检查是否有一个点 k 使得 i 和 j 之间距离更短，如果有，则更新最短距离
  for(let k = 0; k < v; k++){
    for(let i = 0; i < v; i++){
      for(let j = 0; j < v; j++){
        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j])
      }
    }
  }
  return dist;
}

总结

理解图的常见概念，我们就算入门了。接下来就可以做题了。
一般的图题目有两种，一种是搜索题目，一种是动态规划题目。

对于搜索类题目：

图的题目相对而言比较难，尤其是代码书写层面。

对于动态规划题目：
一个经典的例子就是 Floyd-Warshall 算法，理解好了之后大家不妨拿 LC-787. K 站中转内最便宜的航班 练习一下。当然这要求大家应该先学习动态规划。

常见的图的板子题有以下几种：

----END----

上一篇 下一篇

猜你喜欢

热点阅读