跳至主要內容

《算法（第四版）》笔记

图

  1. 自环，即一条连接一个顶点和其自身的边；
  2. 连接同一对顶点的两条边称为平行边；
  3. 含有平行边的图称为多重图；
  4. 没有平行边或自环的图称为简单图。

广度优先搜索用于在非加权图中查找最短路径。

狄克斯特拉算法用于在权重为正的加权图中查找最短路径，权重为负的用贝尔曼-福德算法（Bellman-Ford algorithm）。

无向图

解决的问题

问题解决方法参阅
单点连通性DepthFirstSearch4.1.3.2 节
单点路径DepthFirstPaths算法 4.1
单点最短路径BreadthFirstPaths算法 4.2
连通性CC算法 4.3
检测环Cycle表 4.1.7

无向图的 API

public class Graph {
    public Graph(int V) // 创建一个含有 V 个顶点但不含有边的图
	public Graph(In in) // 从标准输入流 in 读入一幅图
	public int V() // 顶点数
	public int E() // 边数
	public void addEdge(int v, int w) // 向图中添加一条边 v-w
	public Iterable<Integer> adj(int v) // 和 v 相邻的所有顶点
	public String toString() // 对象的字符串表示
}

图处理算法的 API

// 搜索算法
public class Search {
    private int s // 起点 s
    public Search(Graph G, int s) //找到和起点 s 连通的所有顶点
    public boolean marked(int v) //v 和 s 是连通的吗
    public int count() //与 s 连通的顶点总数
}

DFS可找出开始顶点到结束顶点的一条路径（即一个子图）。

BFS可找出开始顶点到结束顶点的一条最短路径（即一个子图）。

路径的 API

public class Paths {
	public Paths(Graph G, int s) // 在 G 中找出所有起点为 s 的路径
	public boolean hasPathTo(int v) // 是否存在从 s 到 v 的路径
	public Iterable<Integer> pathTo(int v) // s 到 v 的路径，如果不存在则返回 null
}

连通分量的 API

public class CC {
	public CC(Graph G) // 预处理构造函数
	public boolean connected(int v, int w) // v 和 w 连通吗
	public int count() // 连通分量数
	public int id(int v) // v 所在的连通分量的标识符（0 ～ count()-1）
}

使用 union-find 算法。

可检测图 G 是否为无环图。

用符号作为顶点名的图的 API

public class SymbolGraph {
	private Graph G() // 隐藏的 Graph 对象
	public SymbolGraph(String filename, String delim) // 根据 filename 指定的文件构造图，使用 delim 来分隔顶点名
	public boolean contains(String key) // key 是一个顶点吗
	public int index(String key) // Key 的索引
	public String name(int v) // 索引 v 的顶点名
}

有向图

解决的问题

问题解决方法参阅
单点和多点的可达性DirectedDFS算法 4.4
单点有向路径DepthFirstDirectedPaths4.2.3.2
单点最短有向路径BreadthFirstDirectedPaths4.2.3.2
有向环检测DirectedCycle4.2.4.2 框注“寻找有向环”
深度优先的顶点排序DepthFirstOrder4.2.4.2 框注“有向图中基于深度优先搜索的顶点排序”
优先级限制下的调度问题Topological算法 4.5
拓扑排序Topological算法 4.5
强连通性KosarajuSCC算法 4.6
顶点对的可达性TransitiveClosure4.2.5.4 节

有向图的 API

public class Digraph {
	public Digraph(int V) // 创建一幅含有 V 个顶点但没有边的有向图
	public Digraph(In in) // 从输入流 in 中读取一幅有向图
	public int V() // 顶点总数
	public int E() // 边的总数
	public void addEdge(int v, int w) // 向有向图中添加一条边 v → w
	public Iterable<Integer> adj(int v) // 由 v 指出的边所连接的所有顶点
	public Digraph reverse() // 该图的反向图
	public String toString() // 对象的字符串表示
}

最小生成树

最小生成树：给定一幅加权无向图，找到它的一棵最小生成树。

图的生成树是它的一棵含有其所有顶点的无环连通子图。一幅加权图的最小生成树（MST）是它的一棵权值（树中所有边的权值之和）最小的生成树。

计算最小生成树的两种经典算法：Prim 算法和 Kruskal 算法。

各种最小生成树算法的性能特点

V 个顶点 E 条边，最坏情况下的增长数量级

算法空间时间
延时的 Prim 算法EElog⁡E
即时的 Prim 算法VElog⁡V
KruskalEElog⁡E
Fredman-TarjanVE+Vlog⁡V
ChazelleV非常接近但还没有达到 E

原理

树的两个最重要的性质：

  1. 用一条边连接树中的任意两个顶点都会产生一个新的环；
  2. 从树中删去一条边将会得到两棵独立的树。

图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合。横切边是一条连接两个属于不同集合的顶点的边。

贪心算法

切分定理是解决最小生成树问题的所有算法的基础，而这些算法都是一种贪心算法（使用切分定理找到最小生成树的一条边，不断重复直到找到最小生成树的所有边）的特殊情况。

加权边的 API

public class Edge implements Comparable<Edge> {
    public Edge(int v, int w, double weight) // 用于初始化的构造函数
	public double weight() // 边的权重
	public int either() // 边两端的顶点之一
	public int other(int v) // 另一个顶点
	public int compareTo(Edge that) // （父类）将这条边与 that 比较
	public String toString() // （父类）对象的字符串表示
}

加权无向图的 API

public class EdgeWeightedGraph {
    public EdgeWeightedGraph(int V) // 创建一幅含有 V 个顶点的空图
	public EdgeWeightedGraph(In in) // 从输入流中读取图
	public int V() // 图的顶点数
	public int E() // 图的边数
	public void addEdge(Edge e) // 向图中添加一条边 e
	public Iterable<Edge> adj(int v) // 和 v 相关联的所有边
	public Iterable<Edge> edges() // 图的所有边
	public String toString() // （父类）对象的字符串表示
}

最小生成树的 API

public class MST {
    public MST(EdgeWeightedGraph G) // 构造函数
	public Iterable<Edge> edges() // 最小生成树的所有边
	public double weight() // 最小生成树的权重
}

Prim 算法

它的每一步都会为一棵生长中的树添加一条权重最小的边。

Prim 算法的延时实现

具体实现：我们从优先队列中取出一条边并将它添加到树中（如果它还没有失效的话），再把这条边的另一个顶点也添加到树中，然后用新顶点作为参数调用 visit() 方法来更新横切边的集合。

Prim 算法的即时实现

Kruskal 算法

将边加入最小生成树中（图中的黑色边），加入的边不会与已经加入的边构成环，直到树中含有 V−1 条边为止。

最短路径

最短路径树（SPT），它包含了起始顶点到所有可达的顶点的最短路径。

最短路径算法的性能特点

算法局限路径长度的比较次数（增长的数量级）一般情况/最坏情况所需空间优势
Dijkstra 算法（即时版本）边的权重必须为正Elog⁡V / Elog⁡VV最坏情况下仍有较好的性能
拓扑排序只适用于无环加权有向图E+V / E+VV是无环图中的最优算法
Bellman-Ford 算法（基于队列）不能存在负权重环E+V / VEV适用领域广泛

加权有向边的 API

public class DirectedEdge {
	public DirectedEdge(int v, int w, double weight)
	public double weight() // 边的权重
	public int from() // 指出这条边的顶点
	public int to() // 这条边指向的顶点
	public String toString() // 对象的字符串表示
 }

加权有向图的 API

public class EdgeWeightedDigraph {
	public EdgeWeightedDigraph(int V) // 含有 V 个顶点的空有向图
	public EdgeWeightedDigraph(In in) // 从输入流中读取图的构造函数
	public int V() // 顶点总数
	public int E() // 边的总数
	public void addEdge(DirectedEdge e) // 将 e 添加到该有向图中
	public Iterable<DirectedEdge> adj(int v) // 从 v 指出的边
	public Iterable<DirectedEdge> edges() // 该有向图中的所有边
	public String toString() // 对象的字符串表示
}

Dijkstra 算法

拓扑排序算法

Bellman-Ford 算法

上次编辑于: 2024/10/29 06:58:45
贡献者: MIOOR
Copyright © 2025 MIOOR