在我们学习图之前，我们先来复习一下之前学过的树：

树

树的定义

树由一系列节点与一系列连接这些节点的边组成，且要求任意两个节点之间有且仅有一条路径。

选择一个节点作为“根”的树是有根树。

从节点 N 到根节点路径上的第一个节点被称为 N 的父节点。除了根节点，每个节点有且仅有一个父节点。
没有子节点的节点被称为叶子节点。

树的遍历

有时你会需要像访问列表那样迭代地访问一棵树，这种行为被称为 树的遍历（tree traversal）。但不同于列表只能从头遍历到尾，我们在遍历一棵树的时候可以有多种不同的顺序：

层序遍历
- 从上到下，从左到右：DBFACEG
深度优先遍历
- 分为前序/中序/后序遍历
- 优先遍历深层节点（如 A）而不是浅层节点（如 F）

前序遍历

前序遍历（Preorder traversal）：先访问当前节点，再遍历它的左右孩子。

preOrder(BSTNode x) {
    if (x == null) return;
    print(x.key)
    preOrder(x.left)
    preOrder(x.right)
}

用上面的程序遍历这棵树时，先将根节点 D 传入，程序会先输出根节点的键值 D，再递归地访问它的左孩子 B；将 B 节点传入后，程序先输出键值 B，接着递归访问 B 的左孩子 A；将 A 节点传入后，程序先输出键值 A，接着递归访问 A 的左孩子。但 A 的左右孩子均为空，程序直接返回上个递归调用去访问 B 的右孩子······

以此类推，我们最终会得到一个访问序列：DBACFEG

中序遍历

中序遍历（Inorder traversal）：先遍历左孩子，再访问当前节点，最后遍历右孩子。

inOrder(BSTNode x) {
    if (x == null) return;
    inOrder(x.left)
    print(x.key)
    inOrder(x.right)
}

中序遍历的访问序列：ABCDEFG

后序遍历

后序遍历（Postorder traversal）：先遍历左孩子，再遍历右孩子，最后访问当前节点。

postOrder(BSTNode x) {
    if (x == null) return;
    postOrder(x.left)
    postOrder(x.right)
    print(x.key)
}

后序遍历的访问序列：ACBEGFD

小技巧

看这些递归的代码对人类来说多少有些困难，所以我们可以用对人类来说易懂的可视化小技巧来帮助我们理解：

遍历的用处

那这些树的遍历有什么用处呢？

后序遍历计算文件大小

图（Graphs）

图的定义

树非常适合用于表示像文件系统这种严格的层次关系。

但并非所有的关系都具有分明的层次，像纽约的地铁地图：

这已经不是一棵树了，从 A 点到 B 点已经有不止一条通路了。

而假如我们将树的“任意两个节点之间有且仅有一条路径”要求去掉，我们便得到了一个更加一般化的东西叫做 图（Graphs）。只要有一堆被边连接着的节点，这个结构就可被称为图。

所有的树都是图。

这些都是图

图的术语

一、图的构成

一个图由一系列顶点（Vertex）和边（Edge）构成。

邻接（Adjacency）：如果两个顶点之间有一条边直接相连，则称这两个顶点是相邻的。
关联（Incidence）：一条边与其连接的两个顶点是相关联的。
度（Degree，对于无向图）：一个顶点的度是指与该顶点相关联的边的总数。
- 入度（In-degree，对于有向图）：指向该顶点的边的数量。
- 出度（Out-degree，对于有向图）：从该顶点指出的边的数量。
路径（Path）：从一个顶点到另一个顶点经过的边的序列。如 A -> B -> C -> D 是一条从 A 到 D 的路径。
- 简单路径 (Simple Path)：没有重复顶点的路径。
环（Cycle）：一条起点和终点是同一个顶点且长度大于 0 的路径。
- 自环（Self-loop）：一条边的两个端点都是同一个顶点。
- 有环的 (Cyclic)：如果一个图中至少包含一个环，那么这个图就是 有环图。
- 无环的 (Acyclic)：如果一个图中不包含任何环，那么这个图就是 无环图。
多重边（Multiple Edges）：两个顶点之间存在多条相同的边。
简单图（Simple Graph）：没有自环和多重边的图。

二、图的分类

三、子图

子图 (Subgraph)：对于一个图 $G = (V, E)$ ，如果另一个图 $G' = (V', E')$ 满足 $V' \subseteq V$ 且 $E' \subseteq E$ ，并且 $E'$ 中的边的端点都必须在 $V'$ 中，则称 $G'$ 是 $G$ 的子图。
生成子图 (Spanning Subgraph)：如果子图 $G'$ 包含了原图 $G$ 的 全部顶点 ( $V' = V$ )，但只包含了其边的子集 ( $E' \subseteq E$ )，则称 $G'$ 是 $G$ 的生成子图。
诱导子图 (Induced Subgraph)：对于原图 $G$ 的一个顶点子集 $V'$ ， $G$ 的由 $V'$ 诱导出的子图是指：顶点集为 $V'$ ，边集包含 $G$ 中所有两个端点都在 $V'$ 中的边。

四、连通性

连通性 (Connectivity)
- 连通图 (Connected Graph)：在无向图中，如果任意两点间都存在路径，则图是连通的。
- 连通分量 (Connected Component)：一个无向图中的极大连通子图。“极大”意味着无法再加入另一个顶点及其相连的边而仍然保持连通。极大连通子图必须包含原图里已经确定的顶点之间的所有边。
- 如下面这个图中有两个连通分量：顶点 1~5 形成一个连通分量，顶点 6,7 形成另一个连通分量。
- 强连通图（Strongly Connected Graph）：在有向图中，如果任意两个顶点 u 和 v 之间，既存在从 u 到 v 的路径，也存在从 v 到 u 的路径，则图是强连通的。
- 弱连通图（Weakly Connected Graph）：如果一个有向图忽略方向后得到的无向图是连通的，则原图是弱连通的。
- 强连通分量 (Strongly Connected Component, SCC)：有向图中的极大强连通子图。
- 如下面这个图有两个强连通分量：顶点 1~3 形成一个强连通分量，顶点 4~6 形成另一个强连通分量。
- 弱连通分量（Weakly Connected Component, WCC）：一个有向图忽略所有方向后，得到的无向图中的一个连通分量就称为原有向图的一个弱连通分量。
- 如上面那个图有一个弱连通分量：顶点 1~6 形成了一个弱连通分量。

连通分量的确定

先确定一组顶点

如果这组顶点在原图中能构成一个连通图（也就是说，任意两点之间都有路径相连），那就有了一个候选子图。

检查是否能再加顶点

如果往这组顶点之外再加任何一个顶点，都会破坏连通性（也就是没法和原来的顶点全部连通），那这组顶点就是“极大”的。

补齐边

在极大连通子图里，必须把这组顶点在原图中的所有边都带上，不能缺边。

于是，这样的子图就是一个 极大连通子图，也就是一个 连通分量。

著名的图问题

关于一个图我们能问出很多有趣的问题，下面是一些著名的图问题及其常见名称：

s-t 路径问题：顶点 s 与 t 之间是否存在路径？
连通性问题：图是否连通？即所有顶点间是否存在路径？
双连通性问题：是否存在某个顶点，移除后会使图不连通？
最短 s-t 路径问题：顶点 s 与 t 之间的最短路径是什么？
环检测问题：图中是否包含环？
欧拉回路问题：是否存在使用每条边恰好一次的环？
哈密顿回路问题：是否存在访问每个顶点恰好一次的环？
平面性问题：能否在平面上绘制该图且边无交叉？
同构问题：两个图是否同构（本质上是同一个图）？

图问题的难度具有欺骗性：

欧拉回路算法早在 1873 年就被发现，时间复杂度为 $O(edges)$ 链接
而尽管经过数十年深入研究，至今未找到高效的哈密顿回路算法，最佳算法仍是指数级时间复杂度

图问题是计算机科学理论中数学内涵最丰富的领域之一。

图的遍历

s-t连通性问题

让我们先从一个经典的图问题开始着手：s-t 连通性问题。

给定源顶点（source vertex）s 和目标顶点（target vertex）t，如何判断 s 与 t 之间是否存在路径？

似乎需要我们用某种方式像遍历树一样来遍历整个图。

所以我们采用递归的方法 connected(s, t)，从源顶点开始检查相邻顶点是否为目标顶点。

若当前顶点与目标顶点相等，则返回 true
不相等就选择一个相邻顶点作为当前顶点调用 connected() 检查
若当前顶点的所有相邻顶点经检查后与目标顶点都不相等，返回 false

但这个方法还有一个问题：邻接具有对称性，即 0 与 1 相邻，1 就与 0 相邻，所以可能陷入 0 与 1 无限互相调用的死循环中。

所以我们需要引入一个 标记顶点 的思想：每当我们检查过一个顶点，就对该顶点做标记，下次就不需要再对该顶点进行检查了。

所以整个算法的流程大致如下：

点击展开

这种在转向下一个邻居之前，先探索当前邻居整个子图的遍历方式被称为 深度优先遍历（Depth First Traversal） 或 深度优先搜索（Depth First Search, DFS）。

例如在下图中，我们会在探索顶点 3 前优先将顶点 1 的子图完全探索。

之所以称为“深度优先”，是因为算法会优先尽可能深入地探索路径。

深度优先搜索

DFS 是一个非常强大的技巧，可以用来解决非常多的图问题。下面是另一个例子：

让我们讨论一种能够计算到每个顶点的路径的算法，并称这个算法为 DepthFirstPaths。
目标：找到从源顶点 s 到每个其他可达顶点的路径，且每个顶点至多访问一次。

该算法的流程大致如下：

当调用 dfs(v) 时：

将顶点 v 标记
对于未标记的相邻顶点 w：
- 设置 edgeTo[w] = v
- dfs(w)

点击展开

我们在 DepthFirstPaths 中执行的操作称为 DFS 前序（DFS Preorder）。

DFS 前序：在对邻居进行 DFS 递归调用之前执行操作。
- 如在 dfs(2) 前先设置 edgeTo[2] = 1
- 该图的一个有效 DFS 前序序列为：012543678，等于 dfs() 调用的顺序

当然有了 DFS 前序，就会有 DFS后序（DFS Postorder）。

DFS 后序：在完成所有邻居的 DFS 递归调用之后执行操作。
- 先进行 dfs() 调用，得到 dfs() 返回值后再设置 edgeTo[]
- 该图的一个有效 DFS 后序序列为：347685210，等于 dfs() 递归返回的顺序

除了了深度优先搜索，还有 广度优先搜索（Breadth First Search, BFS）

类似于树的层序遍历
该图的一个有效 BFS 序列为：0 1 24 53 68 7

BFS、DFS 与实现

空谈了这么多，是时候谈谈实现了。要想实现一个图，我们需要确定：

图能提供的 API
- 例如 List 能够提供 addFirst() 和 addLast()，PQ 能够提供 getSmallest() 和 removeSmallest()
- API 决定了使用图的人如何理解图，因为他们只能通过我们定义的方法与图进行交互
能够实现图的具体数据结构
- 例如用来实现 PQ 的堆

而我们的选择将对 运行时间、内存使用、实现各种图算法的难度 产生显著影响。

API

普林斯顿教材为我们提供了图的 API：

public class Graph {
    public Graph(int V):               创建一个有 V 个顶点的空图
    public void addEdge(int v, int w): 添加一条边 v-w
    Iterable<Integer> adj(int v):      返回一个存储顶点 v 的所有邻接顶点的可迭代对象
    int V():                           返回顶点数量
    int E():                           返回边的数量
...

要求：

所有顶点都标记为整数
顶点数量必须提前指定
不支持边的权重
没有取得顶点度数的方法

该 API 每个顶点只支持数字编号作为标识。若需要使用字符串或其他对象（如 “Dallas”、Person 对象）作为顶点标签，需要通过 Map<String, Integer> 映射到内部编号。

API 没有提供取得定点度数的方法，如何在外部实现？

/** degree of vertex v in graph G */
public static int degree(Graph G, int v) {
    int degree = 0;
    for (int w : G.adj(v)) {
        degree += 1;
    }
    return degree;
}

我们还想要打印出整个图的外部方法应该如何实现？

public static void print(Graph G) {
    for (int v = 0; v < G.V(); v += 1) {
        for (int w : G.adj(v)) {
            System.out.println(v + "-" + w);
        }
    }
}

图的表示

这里并非按照课程顺序

明确了图所需要提供的 API，接下来我们应该用什么样的数据结构来实现我们的图呢？

就像之前我们可以用各种花哨的方式来实现树一样，我们也有各种不同的数据结构用来实现图。

邻接矩阵（Adjacency Matrix）

用一个二维数组记录两个顶点之间是否存在边。

矩阵的行和列都代表图中的顶点。
如果图中存在从顶点 i 到顶点 j 的边，那么矩阵中 matrix[i][j] 的值就设为 1（对于无权图）或该边的权重（对于加权图）。
如果不存在边，则设为 0。

有向图

无向图

无向图的每条边都被在矩阵中表示了两次，这是以空间为代价换取的实现简洁性。

邻接表（Adjacency List）

假设我们的图的节点非常多，有 1000 个；但图非常稀疏，边很少，我们的临界矩阵中将会是一堆 0 中掺了几个 1，这不太好。这是我们的邻接表就派上用场了：

它为每个顶点维护一个链表（或数组、集合），用于存储所有与该顶点直接相连的邻接顶点。

用一个大小为 V 的数组（或列表）来存储所有顶点。
数组的每个元素 adj[i] 是一个链表，里面存储了所有与顶点 i 相邻的顶点（对于加权图，可以存储顶点和权重的二元组）。

这也是用于表示图的最常用的方法。

边集（Edge Set）

最简单粗暴的方法，就是直接存储图中所有的边。

运行时间

那么我们的实现又将如何影响运行时间呢？

如果我们的图以邻接表的形式存储，其中 $V$ 是顶点数量， $E$ 是边的数量，那么 print() 方法的时间复杂度是怎样的呢？

点击查看详解

外层循环无论顶点有没有邻居，都会遍历所有顶点，一共执行 $V$ 次；
内层循环遍历顶点 $v$ 的所有邻居。设顶点 $v$ 的度（邻居数量）为 deg(v)，那么内层循环对于每个 $v$ 会执行 deg(v) 次;
print 语句的总执行次数等于所有顶点的度数之和，即： $\sum\limits_{i = 0}^{V - 1} deg(v_i)$ ；

所有顶点的度数之和与边数 $E$ $E$ 的关系为：
- 无向图：所有顶点的度数之和 $= 2E$ （因为每条边被计算了两次，分别出现在两个端点的邻接表中）。
- 有向图：所有顶点的度数之和 $= E$ （因为每条边只出现在起点的邻接表中）。
因此内层循环的总迭代次数为：
- 无向图： $2E$
- 有向图： $E$

整体时间复杂度

外层循环执行 $V$ 次。
内层循环总执行次数为 $\Theta(E)$ （对于有向图）或 $\Theta(2E) = \Theta(E)$ （对于无向图）。
打印操作是 $\Theta(1)$ 的。

因此，总时间复杂度为 $\Theta(V + E)$ 。

`DepthFirstPaths` 的实现

你可以直接用一个 traverse() 方法来实现 DFS 算法，需要 DepthFirstPaths 的时候直接调用这个方法；但普林斯顿教材选择将 DepthFirstPaths 封装在一个对象中，用的时候直接 new 一个出来，然后就可以直接调用成员方法。

一个 Paths 对象就像是一个全知全能的菩萨，你只要把图和源顶点传进去，菩萨就能告诉你 s 到 v 是否相通？经过了哪些顶点？它的 API 如下：

public class Paths {
    public Paths(Graph G, int s):    从 G 中找出所有的路径
    boolean hasPathTo(int v):        从 s 到 v 存在路径吗？
    Iterable<Integer> pathTo(int v): （如果存在）s 到 v 的路径经过了哪些顶点？
}

普林斯顿教材给出的 DepthFirstPaths 实现如下：

public class DepthFirstPaths {
    private boolean[] marked;   // s 与 v 连通时 marked[v] = true
    private int[] edgeTo;       // 通往 v 的顶点是 edgeTo[v]
    private int s;

    public DepthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];  // 一系列初始化
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G, s);              // 找出与 s 连通的顶点
    }

    // 深度优先遍历
    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;     // 不连通直接返回
        List<Integer> path = new ArrayList<>();
        // 由于 edgeTo[] 数组的存储方式，需要从目标顶点开始反向遍历
        for (int x = v; x != s; x = edgeTo[x]) {
            path.add(x);
        }
        path.add(s);    // 添加源顶点
        Collections.reverse(path);  // 由于 path 中存储的顶点是反向的，需要进行一次反转
        return path;
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }
}

运行时间

假设图使用邻接表实现

private void dfs(Graph G, int v) {  // 顶点访问
    marked[v] = true;
    for (int w : G.adj(v)) {
        if (!marked[w]) {           // 边访问
            edgeTo[w] = v;
            dfs(G, w);
        }
    }
}

每个顶点至多被访问 $O(V)$ 次
每条边至多被访问 $O(2E)$ 次

总运行时间为 $O(V + E)$ 。

$O(V)$ 次 dfs 调用和 $O(E)$ 次 marked[w] 检查
不能说是 $O(E)$ 因为需要构建 marked 数组
不能说是 $\Theta(V + E)$ 因为它不是紧确界，如：无边与源顶点相连的图

`BreadthFirstPaths` 的实现

`BreadthFirstPaths`

广度优先搜索：

将起始顶点 s 加入队列并标记该顶点。

队列（queue） 是一种支持两种操作的列表：入队（即 addLast）和出队（即 removeFirst）。
我们将该队列称为 边缘集合（fringe）。

重复以下步骤直到队列为空：

从队列前端移除顶点 v。
对于 v 的每个未标记邻居 n：
- 标记 n
- 设置 edgeTo[n] = v（和/或 distTo[n] = distTo[v] + 1）
- 将 n 加入队列末尾

求解 BreadthFirstPaths 的流程大致如下：

目标：找出 s 与其它顶点之间的最短路径
初始化 fringe（带有源顶点 s 的队列）并标记该顶点
重复下列操作直到 fringe 为空：
- 从 fringe 移除当前顶点 v
- 对于所有未标记的邻居 n：标记并添加到 fringe 中，设置 edgeTo[n] = v 和 distTo[n] = distTo[v] + 1

点击展开

`BreadthFirstPaths` 的实现

普林斯顿教材给出的 BreadthFirstPaths 实现如下：

public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    ...

    private void bfs(Graph G, int s) {
        Queue<Integer> fringe = new Queue<Integer>();
        fringe.enqueue(s);
        marked[s] = true;
        while (!fringe.isEmpty()) {
            int v = fringe.dequeue();
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    fringe.enqueue(w);
                    marked[w] = true;
                    edgeTo[w] = v;
                }
            }
        }
    }
}

该算法的运行时间复杂度同样为 $O(V + E)$

基于相同的成本模型：
- 执行 $O(V)$ 次 .next() 调用
- 执行 $O(E)$ 次 marked[w] 检查

空间复杂度为 $\Theta(V)$

需要长度为 $V$ 的数组来存储信息

最短路径问题

问题引入

为何 BFS 失效了？

前面我们深入讨论了两种在图中寻找路径的方法：DFS 和 BFS。那这两种方法哪种更好呢？

正确性：两种算法是否适用于所有图？
- 两种算法对于所有图都适用。
输出质量：哪种算法能提供更好的结果？
- BFS 是“一举两得”的方案：不仅能得到路径，还能保证路径具有最少的边数。
时间效率：一种算法比另一种更高效吗？
- 应非常相似。两种算法都会对所有边进行两次处理。需要实验或非常仔细的分析来验证。
空间效率：一种算法比另一种更高效吗？
- DFS 在细长图中表现更差：
  - 调用栈会变得非常深
  - 计算机需要 $\Theta(V)$ 内存来记录递归调用（参见 CS61C 课程）
- BFS 在稠密图中表现更差：
  - 队列会变得非常大。最坏情况下，队列需要 $\Theta(V)$ 内存
  - 示例：100 万个全连通的顶点，会有 999,999 个顶点同时入队
注：在我们的实现中，无论如何都需要 $\Theta(V)$ $Θ (V)$ 内存来存储 distTo 和 edgeTo 数组。
- 可通过使用映射代替数组来存储 distTo 和 edgeTo 以优化空间。

看来在寻找最短路径方面还是 BFS 更胜一筹。那么如果我们将 BFS 应用于谷歌地图的导航，效果如何？

假如我们想要从 s 前往 t：

正确的最短路径应该是：

而 BFS 返回的结果是：

原因是 BFS 得到最短路径的依据是路径中边的条数最少，但无法处理每条边的权重。所以接下来让我们寻找一个能够有效处理加权图的算法吧。

最短路径树

已知每条公路的长度，找到下图中从 A 镇到 F 镇的最短路径：

点击展开

很容易看出来，A 到 F 最短路径是 A -> B -> E -> F，长度为 9 英里。

而值得注意的是，（权值非负的情况下）最短路径中 永远不存在环。

而如果我们将图中源顶点到其它所有顶点的最短路径找出来：

我们将得到一棵树，原因是 每条路径中都不存在环。

如果一个连通加权图 G 有 $V$ 个顶点和 $E$ 条边，那么它的最短路径树（Shortest Paths Tree, SPT）的边数为 $V - 1$ ，原因是除了根节点，每个节点都有一条边指向它。

Dijkstra 算法

其它算法

知道了寻找图中某个顶点到其它所有顶点的最短路径的结果是一棵树，接下来让我们尝试用一些算法构造吧。

下图中以 A 为源顶点的最短路径树是什么？

点击展开

其中粉色数字表示当前顶点到源顶点的距离。

#1（BFS）

点击展开

之前我们讨论过了，BFS 对于无权图是适用的；但对于加权图，它势必不会给出让我们满意的答案。

#2（虚拟顶点）

不过既然 BFS 适用于无权图，如果我们用虚拟顶点将加权图转换成无权图呢？

点击展开

确实行得通，但很容易想象这种方法非常慢；而且对于下面这种图显得是那么弱小无力：

但我们能从中学到一些东西：由于只有当遇到原始顶点时才会向 SPT 添加路径，所以这个算法本质上是基于距离进行比较而不是 边的数目。这种算法策略被称为 最佳优先顺序（best-first order）。

#3（最佳优先搜索）

得到了如此重要的结论，我们应该充分利用：这次我们不再使用队列，而是用 优先队列 作为 fringe，每次弹出 距离最近的顶点 来保证最短的路径：

点击展开

但是结果仍然不对，到底是怎么回事？？？

点击展开

在检查每个顶点的出边时，一旦出边指向的顶点已经存在于 SPT 中，我们就不再对其进行检查了。

但我们所应该做的恰恰相反：由于 A -> C -> B 这条路径的长度显然比 A -> B 要短，因此在检查顶点 C 的出边的时候必须要重新检查到 B 的距离。如果距离更近，则更新 B 的距离和 SPT 中通往 B 的路径。

这个通过边更新路径权重的操作被称为 边松弛（edge relaxation）。

Dijkstra 算法

每次只对距离最近的顶点进行检查。（最佳优先）
松弛当前顶点的所有邻居。即检查是否存在一条通过当前顶点到达其邻居的、更短的路径。如果有，就更新邻居顶点的距离。（边松弛）

这两点就是 Dijkstra 算法的核心。

下面是 Dijkstra 算法的完整步骤：

点击展开

伪代码

Dijkstra：

PQ.add(source, 0)
PQ.add(v, infinity)
while(PQ 非空)：
- p = PQ.removeSmallest()
- 松弛 p 的所有出边

松弛权值为 w 的边 p -> q：

if (distTo[p] + w < distTo[q])：
- distTo[q] = distTo[p] + w
- edgeTo[q] = p
- PQ.changePriority(q, distTo[q])

核心不变性：

edgeTo[v] 是顶点 v 的已知最佳前驱节点
distTo[v] 是从源点到 v 的已知最佳总距离
优先队列按 distTo 值存储所有未访问的顶点

关键特性：

始终按距离源点的总距离顺序访问顶点
对于已访问（白色）顶点的边，松弛操作必定失败

为什么说“对于已访问顶点的边，松弛操作必定失败”？

假设一个图的源顶点为 S，S 到其邻居 v1、v2、v3、v4 的距离分别为 c、>c、>c、>c。

松弛 S 的所有邻居后，由于 v1 的距离最近，首先会对 v1 进行访问检查。

假设接下来访问的顶点是 v4，而 v4 有一条权值为 w 的出边指向 v1，那么在检查 v4 时势必会对 v1 进行松弛。

但这个松弛操作势必会失败，因为 distTo[v4] 大于 distTo[v1]，则 distTo[v4] + w 一定大于 distTo[v1]。

而对于更深层的顶点更是如此。

但值得注意的是，一旦边的权值为负，Dijkstra 算法就会失效。 因为“始终按距离源点的总距离顺序访问顶点”的基本特性不再适用了；对于已访问顶点的边也能够进行松弛操作了。

时间复杂度分析

Dijkstra 算法共涉及到三个操作：

add()：将所有顶点添加到优先队中
removeSmallest()：每次弹出最近顶点检查
changePriority()：松弛顶点邻居时需要更新邻居距离并重新排序

对于基于二叉堆的优先队列：

总体的时间复杂度为： $O(V \log (V) + V \log (V) + E \log V)$

假设对于连通图 G： $E > V$ ，则总时间复杂度为 $O(E \log V)$ 。

A* 算法

A* 的思想和演示

还记得我们当初学最短路径算法的目的吗？我们想要实现谷歌地图的导航功能！

假如我们现在想要从丹佛前往纽约，Dijkstra 算法能够为我们规划出最合适的路线吗？

答案是肯定的，但显而易见，效率一定不会很高。因为 Dijkstra 算法只依据顶点的远近进行出队检查，所以它势必会将丹佛四面八方的所有城市都进行检查，而不是只针对“前往纽约”方向的城市进行检查。这样做大大增加了工作量。

那能不能只针对纽约方向进行路线规划呢？

我们的解决方案是：在检查一个顶点时，不仅仅考虑该顶点到源顶点的距离，还要考虑它到目标顶点的距离。也就是 d(Denver, v) + h(v, NYC)（其中 Dijkstra 只考虑 d(Denver, v)）。

换句话说，顶点 v 不仅要距离丹佛近，还要距离纽约近才会被优先纳入考虑当中。

A* 算法演示

按照 d(source, v) + h(v, goal) 的顺序对每个顶点进行存储

显而易见：

并不是所有顶点都被访问
得到的结果并不是一棵最短路径树，但到目标顶点的路径一定最短

h(v, NYC) 叫做 启发函数（Heuristic Function）。A* 算法则利用启发函数来智能地选择最有可能朝向目标的节点进行扩展，从而大大减少了需要探索的节点数量，显著提高了搜索效率。

树

树的定义

树的遍历

前序遍历

中序遍历

后序遍历

小技巧

遍历的用处

图（Graphs）

图的定义

图的术语

著名的图问题

图的遍历

s-t连通性问题

深度优先搜索

BFS、DFS 与实现

API

图的表示

邻接矩阵（Adjacency Matrix）

邻接表（Adjacency List）

边集（Edge Set）

运行时间

DepthFirstPaths 的实现

运行时间

BreadthFirstPaths 的实现

BreadthFirstPaths

BreadthFirstPaths 的实现

最短路径问题

问题引入

为何 BFS 失效了？

最短路径树

Dijkstra 算法

其它算法

#1（BFS）

#2（虚拟顶点）

#3（最佳优先搜索）

Dijkstra 算法

伪代码

时间复杂度分析

A* 算法

A* 的思想和演示

`DepthFirstPaths` 的实现

`BreadthFirstPaths` 的实现

`BreadthFirstPaths`

`BreadthFirstPaths` 的实现