UCB CS61B 学习笔记
写在前面
Java是我接触的第一门编程语言，磕磕绊绊的学习也收获了不少。最早跟随尚硅谷2014年免费课进行学习，虽然最终学习进度停在了泛型等其他高级类特性，但是受到这么多年在计算机世界的熏陶后，对编程语言还是有了比较深入的了解，因而本笔记不再按照lecture分节，仅记录我认为是重点或者有趣、有用的东西（当然还是大体上按照课程顺序）
实际上这门课叫《算法与数据结构》，编程语言只是实现方法，不是最终目的，因而不必在这上面纠结过多。
课程的作业依赖org.junit.jupiter和com.google.common.truth，其中com.google.common.truth还依赖com.google.common.guava，所以需要导入外部库文件。
在File/Project Structure/Project Settings/Modules，选择添加JAR即可。
Maven Repository: com.google.guava » guava » 33.3.0-jre
Maven Repository: com.google.truth » truth » 1.4.4
数据类型
Java的数据类型可以分为基本数据类型和引用数据类型，其中基本数据类型有八种byte,short,int,long,char,boolean,float,double，它们栈内存中直接存储数据值，有明确的默认值（如int默认 0，boolean默认false）且固定大小。
而引用数据类型存储对象的引用（内存地址），而非对象本身，变量在栈内存中存储引用，对象本身在堆内存中，默认值为null，表示不指向任何对象，引用本身大小固定（通常为 32/64 位），但对象大小不定。
这在C/C++与Java中存在区别。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public class People{
public int age;
private String name;
public People(int age,String name){
this.age = age;
this.name = name;
}
}
public class Main{
public static void main(String args[]){
People p1 = new People(18,"Tom");
People p2 = p1;
p2.age = 10;
System.out.println(p1.age);
}
}
|
上述Java代码的执行结果应该是10而不是18，因为p2和p1共享一个内存空间。在C/C++中：
1
2
3
4
5
6
7
8
9
10
11
|
class Point {
public:
int x, y;
};
int main() {
Point p1{10, 20};
Point p2 = p1; // 值传递：复制p1的所有成员到p2
p2.x = 100;
// p1.x仍为10，p2.x为100（内存独立）
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <stdio.h>
typedef struct {
int x;
int y;
} Point;
int main() {
Point p1 = {10, 20};
Point p2 = p1; // 值传递：复制p1的内容到p2
p2.x = 100; // 修改p2的成员
printf("p1.x = %d, p1.y = %d\n", p1.x, p1.y); // 输出: p1.x = 10, p1.y = 20
printf("p2.x = %d, p2.y = %d\n", p2.x, p2.y); // 输出: p2.x = 100, p2.y = 20
return 0;
}
|
在C/C++中需要自定义行为来实现深拷贝或引用传递。
需要注意的是，数组在Java中也不是基本数据类型，因而数组也需要实例化对象，这表明Java的数组是存在堆中的。这与C/C++有显著差异，在C/C++中，一般的数组是存在栈上的，若需要存在堆上，则需要自己分配内存并回收内存。
因而可以这么认为，在Java中，new关键字相当于申请内存，相当于malloc()，除了基本数据类型以外，所有的数据类型都是指针。
数据结构
二叉搜索树（Binary Search Tree）
二叉搜索树是一种将有序数组以大小关系转换为二叉树的数据结构，确保每个节点的左子树的任何值都小于该节点、每个节点的右子树的任何值都大于该节点。
在二叉搜索树（BST）中删除节点时，需要保证删除后树仍然保持 BST 的性质，删除操作的复杂度在于需要处理三种不同情况，下面我将详细解释。
假设我们要删除的节点为N：
-
节点N没有子节点（叶子节点）
直接删除该节点，将其父节点的对应指针置为null。
1
2
3
4
5
6
7
8
9
10
11
|
原树：
5
/ \
3 7
/
2
删除后：
5
/ \
2 7
|
-
节点N只有一个子节点
用子节点替换N的位置，即让父节点直接指向N的子节点。
1
2
3
4
5
6
7
8
9
10
11
|
原树：
5
/ \
3 7
/
2
删除后：
5
/ \
2 7
|
-
节点N有两个子节点
需要找到N的 中序后继节点（Inorder Successor） 或 中序前驱节点（Inorder Predecessor） 来替换N。其中中序后继指的是右子树中的最小节点（即右子树的最左节点）；而中序前驱指的是左子树中的最大节点（即左子树的最右节点）。通常选择中序后继进行替换，因为实现更简单。替换后，原后继节点的位置需要递归调整（通常是删除原后继节点，因为它一定没有左子节点）。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
原树：
5
/ \
3 7
/ \ / \
2 4 6 8
中序后继是6（右子树的最小节点），用6替换5：
6
/ \
3 7
/ \ \
2 4 8
|
Java实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
class BST{
private static class Node {
int data;
Node left, right;
public Node(int data,Node left,Node right){
this.data = data;
this.left = left;
this.right = right;
}
public int Data(){return this.data;}
public Node Left(){return this.left;}
public Node Right(){return this.right;}
}
private Node root = null;
private Node buildTree(int lpos, int rpos, int[] arr){
if(lpos > rpos)return null;
int mid = lpos + (rpos - lpos) / 2;
Node curr = new Node(arr[mid], null, null);
curr.left = buildTree(lpos, mid - 1, arr);
curr.right = buildTree(mid + 1, rpos, arr);
return curr;
}
/** return the max node of the right subtree */
private Node findMin(Node N){
while(N.left != null) N = N.left;
return N;
}
private Node BSTinsert(Node N,int val){
if(N==null){
return new Node(val, null, null);
}
if(val < N.Data()){
N.left = BSTinsert(N.left,val);
}else if(val > N.Data()){
N.right = BSTinsert(N.right,val);
}
return N;
}
private Node BSTdelete(Node N, int val){
if(N == null){
return null;
}
if(val < N.Data()){
N.left = BSTdelete(N.left, val);
}else if(val > N.Data()){
N.right = BSTdelete(N.right, val);
}else{
//no child or only have one child
if(N.left == null) return N.right;
if(N.right == null) return N.left;
//have two child
Node tmp = findMin(N.right);
N.data = tmp.data;
N.right = BSTdelete(N.right, tmp.data);
}
return N;
}
/** The constructor of Binary Search Tree
*
* need a no-sorted array, because the constructor has
* already sorted the array
**/
public BST(int[] arr){
Arrays.sort(arr);
int len = arr.length;
int mid = len/2;
root = buildTree(0, len-1, arr);
}
public void insert(int val){
root = BSTinsert(root,val);
}
public void delete(int val){
root = BSTdelete(root,val);
}
public void inorderTraversal(){
}
}
|
B树（B-tree）
B树是一种自平衡的搜索树，被广泛应用于索引和搜索操作。平衡树是指任意节点的左子树和右子树的高度差（平衡因子）的绝对值不超过1的树。B树不是二叉树而是多叉树，常见的B树有2-3树（2-3 tree）和2-3-4树（2-3-4 tree）。
2-3树是最简单的B树，是指每个节点最多有2个数据，每个节点最多有3个子节点。2-3-4树是指每个节点最多有四个字节点和三个数据项，可以理解为非叶节点的子节点数总是比它含有的数据项多1。如果子节点个数为L，数据项个数为D，那么满足关系L = D + 1。
红黑树（Red-Black Tree）
红黑树实际上是B树的变体。2-3树等价于左旋红黑树（LLRB），2-3-4树等价于红黑树。红黑树每个节点只有一个数据，由B树转换为红黑树时，需要将B树中多数据节点拆开，产生红边（以区别B树中正常连接的黑边）。
红黑树（图解+秒懂+史上最全） - 技术自由圈 - 博客园一文很好的介绍了这个数据结构。
高阶数据结构：红黑树原理与代码实现 - 知乎一文介绍了红黑树的C++实现。
由于个人能力有限，暂时无法复现B树与红黑树的代码，本部分等待后续更新。
哈希表（Hash Table）
Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码，这些编码值叫做Hash值。也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。
哈希表本质是一个数组，数组存储着指针，指向一个链表。当一个数据产生哈希值后，便会被插入这个数组中，其索引为哈希值。然而，两个不同的数据可能产生相同的哈希值，为了解决哈希碰撞的问题，在每一个数组索引对应的值上插入一个指针指向链表，链表依次向后搜索或者插入数据，相同哈希值的数据被存入链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
public class HashTable{
//定义节点，数据以int为例
private static class Node{
Node next;
int key;
int val;
public Node(Node next,int key,int val){
this.next = next;
this.val = val;
this.key = key;
}
}
//以长度为10举例
private Node[] list;
public HashTable(){
list = new Node[10];
}
public int search(int key){
int index = ???.gethash(key);
Node curr = list[index];
while(curr != null){
if(curr.key == key){
return val;
}
curr = curr.next;
}
return 0;
}
public void insert(int key,int val){
int index = ???.gethash(key);
Node curr = list[index];
while(curr != null){
if(curr.key == key){
curr.val = val;
}
curr = curr.next;
}
Node tmp = new Node(null,key,val);
tmp.next = list[index];
list[index] = tmp;
}
}
|
Java 【数据结构】 哈希（Hash超详解）HashSet&HashMap【神装】_java hash-CSDN博客一文详细介绍了哈希表（Hash Table，又称哈希桶，Hash Basket）和HashSet与HashMap
堆（Heap）
堆（Heap）是一类特殊的数据结构，通常用于实现优先级队列。堆通常是一个可以被看做一棵树的数组对象。堆可以看作是一棵完全二叉树的数组对象，具有以下两个主要性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值。
- 堆总是一棵完全二叉树。
根据根节点的值，堆可以分为最大堆（大根堆）和最小堆（小根堆）。在最大堆中，根节点的值是所有节点中最大的；在最小堆中，根节点的值是所有节点中最小的
以下是小根堆的基础实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
public class Heap {
private int keys[];
private int size = 100;
private int index = 0;
public Heap() {
keys = new int[size + 1];
}
public int getKey(int index) {
return keys[index];
}
public int top(){
return keys[1];
}
private void swap(int i, int j) {
int temp = keys[i];
keys[i] = keys[j];
keys[j] = temp;
}
public void swim(int pos) {
if (pos == 1) return;
if (keys[pos] < keys[pos / 2]) {
swap(pos, pos / 2);
swim(pos / 2);
}
}
public void insert(int key) {
keys[++index] = key;
swim(index);
}
public void deleteMin() {
keys[1] = keys[index--];
int pos = 1;
while (index >= 2 * pos) {
int j = 2 * pos;
if(j < index && keys[j] > keys[j + 1]) j++;
if(keys[j] >= keys[pos]) break;
swap(j, pos);
pos = j;
}
}
}
|
优先队列（Priority Queue）
是一种抽象数据类型（ADT），定义了一组操作（如插入元素、取出优先级最高的元素等），核心特性是每次取出的元素都是当前队列中优先级最高的（具体优先级由规则定义，如数值大小、自定义比较器等）。如果用小根堆实现优先队列，则可以实现最小值优先的优先队列。
算法
树的遍历（Tree Travelers）
树的遍历分为前序（PreOrder）、中序（InOrder）、后序（PostOrder）遍历。前序遍历按照根节点 → 左子树 → ··· → 右子树的顺序遍历，广泛出现于各种递归、暴力搜索的过程中。中序遍历按照左子树 → 根节点 → 右子树的顺序遍历，特别地，对于二叉搜索树，中序遍历结果是升序序列。后序遍历按照左子树 → 右子树 → 根节点，常用于删除树节点，以确保先删除子节点，再删除根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void preorder(TreeNode root) {
if (root == null) return;
System.out.print(root.val + " "); // 访问根
preorder(root.left); // 遍历左
preorder(root.right); // 遍历右
}
void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left); // 遍历左
System.out.print(root.val + " "); // 访问根
inorder(root.right); // 遍历右
}
void postorder(TreeNode root) {
if (root == null) return;
postorder(root.left); // 遍历左
postorder(root.right); // 遍历右
System.out.print(root.val + " "); // 访问根
}
|
图的存储
树是特殊的图。对于一般的图，一般有三种存储方式：
邻接矩阵（Adjacency Matrix）
使用二维数组表示图中节点之间的连接关系。适用于稠密图（边数接近节点数的平方）。
- 二维数组
matrix[i][j] 表示节点 i 到 j 是否有边
- 对于无权图，
matrix[i][j] = 1 表示有边，0 表示无边
- 对于有权图，
matrix[i][j] 存储边的权重，∞ 表示无边
复杂度分析：
- 空间复杂度：O (V²)，V 为顶点数
- 添加边：O(1)
- 判断两节点是否相邻：O(1)
- 遍历所有边：O(V²)
邻接表（Adjacency List）
使用链表数组表示每个节点的邻接节点。适用于稀疏图（边数远小于节点数的平方）。
- 数组
adj 存储每个节点的邻接表
adj[i] 是一个链表，包含所有从节点 i 出发的边的终点- 对于有权图，链表节点还需存储边的权重
复杂度分析：
- 空间复杂度：O (V+E)，V 为顶点数，E 为边数
- 添加边：O(1)
- 判断两节点是否相邻：O (E/V)（平均情况）
- 遍历所有边：O(V+E)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
import java.util.*;
public class AdjacencyListGraph {
private int numVertices;
private LinkedList<Integer>[] adj; // 无边权邻接表数组
// 初始化
public AdjacencyListGraph(int vertices) {
this.numVertices = vertices;
adj = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adj[i] = new LinkedList<>();
}
}
// 添加边（无权图）
public void addEdge(int src, int dest) {
adj[src].add(dest);
}
// 有权图边的定义
static class Edge {
int dest;
int weight;
public Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight;
}
}
private LinkedList<Edge>[] weightedAdj; // 带权邻接表
// 加有权边
public void addWeightedEdge(int from, int dest, int weight) {
weightedAdj[from].add(new Edge(dest, weight));
}
}
|
链式前向星（Linked Forward Star）
国人发明的数据结构，十分好用。链式前向星是一种高效存储图的数据结构，结合了邻接表和数组的优势，适合处理大规模稀疏图。它通过静态数组模拟链表，避免了频繁内存分配的开销，广泛应用于图论算法。
- 边的结构：
to：边的终点next：同起点的下一条边的索引（通过head数组连接同起点的所有边）weight：边的权重
- 头数组
head：
head[u] 存储顶点u的第一条边的索引- 初始化为
-1，表示没有出边
- 添加边的顺序：
- 新边总是插入到链表头部（类似栈的 LIFO）
- 例如，依次添加边
u→v1, u→v2, u→v3，链表顺序为 v3 → v2 → v1
复杂度分析
- 空间复杂度：O (V + E)，V 为顶点数，E 为边数
- 添加边：O(1)
- 遍历某个顶点的所有出边：O (该顶点的出度)
- 遍历所有边：O(E)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
struct edge{
int to,len,nxt;
// to 边的终点
// len 边的长度，即权重
// nxt 同起点下一条边的索引
}edge[MAXN];
int head[MAXN],cnt;
// head[u] 存储顶点u的第一条边的索引
// cnt 总边数，为最后一条边的索引
void add(int x,int y,int z){
cnt++;// 更新索引
edge[cnt].to = y;
edge[cnt].len = z;
edge[cnt].nxt = head[x];
head[x] = cnt;// 更新头
}
|
图的遍历（Map Travelers）
由于图可能存在环，在遍历时需要一个数组显式地记忆该节点是否被访问过。如果使用深度优先搜索，可以使用递归。
1
2
3
4
5
6
7
8
9
10
11
|
bool vis[MAXN];
void DFS(int now){
vis[now] = TRUE;
printf(now);
for(now可到达的边 = i){
if(vis[i] == FALSE){
DFS(i);
}
}
}
|
也可以使用广度优先搜索，二者的区别是前者需要用到栈（先进后出，以确保一直先搜索第一条路径直到头），后者需要队列（先进先出，以确保一直搜索上一级节点能到达的所有节点）。由于调用递归时，用到了内存的栈结构，所以不需要在自行定义一个栈进行使用。而在广度优先搜索中，没有可以使用的抽象硬件结构，所以需要显式定义队列这一数据类型。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class BFS {
public void bfs(Graph graph, int start) {
boolean[] visited = new boolean[graph.getV()];
Queue<Integer> queue = new LinkedList<>();
// 起始顶点入队并标记访问
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
// 将未访问的邻接顶点入队
for (int neighbor : graph.getAdj().get(v)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
}
|
单源最短路算法
在图论中，单源最短路算法用于求解从一个固定起点（源点）到图中所有其他顶点的最短路径。
Dijkstra 算法
图中无负权边（可含非负权边，有向图 / 无向图均可）时使用，时间复杂度较低，适合稠密图或稀疏图。该算法使用贪心策略，每次从 “未确定最短路径的顶点” 中选择距离源点最近的顶点，确定其最短路径，同时有“松弛操作”，以该顶点为中介，更新其他顶点到源点的距离。
要实现该算法，初始化时首先定义源点距离为 0，其他顶点距离为∞，标记所有顶点为 “未访问”，然后重复以下操作，直到所有顶点被访问：
- 选择距离源点最近的 “未访问” 顶点
u，标记为 “已访问”。
- 对
u的所有邻接顶点v，若distance[v] > distance[u] + weight(u, v)，则更新distance[v]。
朴素实现下（邻接矩阵 + 线性查找）：O(n²)（n 为顶点数），优化实现下（邻接表 + 优先队列）：O(m log n)（m 为边数），适用于稀疏图。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
namespace Dijkstra {
const int MAXN = 1e5 + 5; // 最大顶点数
typedef long long LL; // 防止距离溢出
struct Edge {
int to; // 终点
int weight; // 边权
int next; // 同起点的下一条边的索引
} edges[MAXN * 2]; // 边表（无向图需双倍空间）
LL dist[MAXN]; // 源点到各点的最短距离
int head[MAXN]; // 每个顶点的第一条边的索引
int edgeCount; // 边计数器
// 小根堆：存储{距离, 顶点}对
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> minHeap;
// 初始化图
void init(int vertexCount) {
edgeCount = 0;
memset(head, -1, sizeof(head)); // -1表示没有边
fill(dist, dist + vertexCount + 1, LLONG_MAX / 2); // 初始化为极大值
}
// 添加有向边
void addEdge(int from, int to, int weight) {
edges[edgeCount] = {to, weight, head[from]};
head[from] = edgeCount++;
}
// 添加无向边
void addUndirectedEdge(int u, int v, int weight) {
addEdge(u, v, weight);
addEdge(v, u, weight);
}
// 计算从源点source到所有点的最短路径
void compute(int vertexCount, int source) {
// vertexCount：最大节点数，防止数组越界
dist[source] = 0;
minHeap.push({0, source});
while (!minHeap.empty()) {
LL currentDist = minHeap.top().first;
int currentVertex = minHeap.top().second;
minHeap.pop();
// 跳过已处理的节点（避免重复计算）
if (currentDist > dist[currentVertex]) continue;
// 遍历当前顶点的所有邻接边
for (int i = head[currentVertex]; i != -1; i = edges[i].next) {
int neighbor = edges[i].to;
int edgeWeight = edges[i].weight;
// 松弛操作
if (dist[neighbor] > dist[currentVertex] + edgeWeight) {
dist[neighbor] = dist[currentVertex] + edgeWeight;
minHeap.push({dist[neighbor], neighbor});
}
}
}
}
}
|
该算法的核心应该是：
$$
Dist[neighbor]=min(Dist[currentVertex]+edgeWeight,Dist[neighbor])
$$A*算法
A*实际上是一个思想，利用启发式函数进行最短路搜索。A * 算法为每个节点 n 维护两个值：
g(n)：从起点到节点 n 的实际代价h(n)：从节点 n 到终点的估计代价（启发函数）f(n) = g(n) + h(n)：总估计代价
每次选择 f(n) 值最小的节点进行扩展，直到找到终点或遍历完所有可达节点。
一般来说，启发函数选择：
- 曼哈顿距离（网格只能上下左右移动）：
h(n) = |x1-x2| + |y1-y2|
- 欧几里得距离（网格可斜向移动）：
h(n) = √((x1-x2)² + (y1-y2)²)
- 对角线距离（网格允许 8 方向移动）：
h(n) = max(|x1-x2|, |y1-y2|)
而在常规的抽象图问题中，只存在边权，不存在网格，通常选择启发式函数h(n)=0，此时算法退化为Dijkstra。
其他算法
最短路 - floyd 算法 - OI Wiki
最短路 - Bellman Ford 算法 - OI Wiki
最小生成树（Minimum Spanning Tree）
最小生成树详解(模板 + 例题)-CSDN博客给出了非常详细且直观的算法说明。
Kruskal 算法
Kruskal 算法基于贪心策略，通过按边权从小到大的顺序选择边，确保每次选择的边不形成回路，直到构建出包含所有顶点的最小生成树。该算法使用并查集（Union-Find）数据结构高效判断是否形成回路。
首先算法初始化并查集，然后从边权最小的边开始枚举，每次找到一个边，就把边连接到的两个节点union到并查集中，当枚举到第n-1个边时就得到了最小生成树，具体来说：
- 将所有边按权重从小到大排序
- 初始化并查集，每个顶点的父节点为自身
- 遍历排序后的边：
- 若边的两个端点属于不同集合（即不形成回路），则将该边加入 MST，并合并两个集合
- 若形成回路则跳过该边
- 重复步骤 3 直到加入 n-1 条边或遍历完所有边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
import java.util.*;
class Edge implements Comparable<Edge> {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
public class Kruskal {
private int V;
private List<Edge> edges;
private int[] disjointSet;
private Edge[] ans;
public Kruskal(int V) {
this.V = V;
edges = new ArrayList<>();
disjointSet = new int[V];
ans = new Edge[V-1];
for (int i = 0; i < V; i++) {
disjointSet[i] = i;
}
}
public void addEdge(int src, int dest, int weight) {
edges.add(new Edge(src, dest, weight));
}
public void doKruskal() {
Collections.sort(edges);
int e = 0, i = 0;
while (e < V - 1 && i < edges.size()){
Edge curr = edges.get(i++);
int Pfrom = find(curr.src);
int Pto = find(curr.dest);
if(Pfrom != Pto){
ans[e++] = curr;
union(Pfrom,Pto);
}
}
}
public void printKruskal() {
for (Edge e : ans) {
System.out.println(e.src + " -> " + e.dest + " == " + e.weight);
}
}
private int find(int x) {
if (disjointSet[x] == x) return x;
return disjointSet[x] = find(disjointSet[x]);
}
private void union(int from, int to) {
int xRoot = find(from);
int yRoot = find(to);
disjointSet[xRoot] = yRoot;
}
public static void main(String[] args) {
int V = 4; // 4个顶点
Kruskal graph = new Kruskal(V);
// 添加边
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(1, 3, 15);
graph.addEdge(2, 3, 4);
graph.doKruskal();
graph.printKruskal();
}
}
|
Prim 算法
Prim算法以点为核心，使用深度优先搜索，类似Dijkstra算法。每搜到一个点就去找它边权最短的一条边，由于是一个图，总会存在一条路径使其遍历完整个图的节点，且满足只要局部最小全局一定最小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
import java.util.*;
class Edge implements Comparable<Edge> {
int to, weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
public class Prim {
private int V;
private List<List<Edge>> adj;
private boolean[] inMST;
private int[] key;
private int[] parent;
public Prim(int V) {
this.V = V;
adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
inMST = new boolean[V];
key = new int[V];
parent = new int[V];
Arrays.fill(key, Integer.MAX_VALUE);
Arrays.fill(parent, -1);
}
public void addEdge(int src, int dest, int weight) {
adj.get(src).add(new Edge(dest, weight));
adj.get(dest).add(new Edge(src, weight)); // 无向图
}
public void doPrim() {
// 从顶点0开始
key[0] = 0;
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.offer(new Edge(0, 0));
while (!pq.isEmpty()) {
int u = pq.poll().to;
if (inMST[u]) continue;
inMST[u] = true;
for (Edge edge : adj.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (!inMST[v] && weight < key[v]) {
key[v] = weight;
parent[v] = u;
pq.offer(new Edge(v, key[v]));
}
}
}
}
public void printPrim() {
int totalWeight = 0;
System.out.println("Prim算法生成的MST:");
for (int i = 1; i < V; i++) { // 从1开始，因为顶点0是根
if (parent[i] == -1) {
System.out.println("错误：输入的图不连通，无法生成完整的最小生成树！");
return;
}
System.out.println(parent[i] + " -> " + i + " == " + key[i]);
totalWeight += key[i];
}
System.out.println("总权重: " + totalWeight);
}
public static void main(String[] args) {
int V = 4;
Prim graph = new Prim(V);
// 添加边（与Kruskal示例相同）
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(1, 3, 15);
graph.addEdge(2, 3, 4);
graph.doPrim();
graph.printPrim();
}
}
|
有向无环图的单源最短路径树（Directed Acyclic Graph Shortest Path Spanning Tree，DAG SPT）
有向无环图是一种特殊的图。
拓扑序（Topological Order）是针对有向无环图（DAG） 的一种顶点排序方式，它满足一个核心条件：对于图中任意一条有向边 u−>vu−>v，顶点 u 在拓扑序中一定排在顶点 v 之前。简单来说，拓扑序是一种 “按依赖关系排序” 的方式，所有 “前置条件”（前驱顶点）都排在 “后续任务”（后继顶点）之前，且图中不存在环（否则无法满足这种排序）。一个 DAG 可能有多个拓扑序。
AcyclicSP（Directed Acyclic Graph Shortest Path）是专门针对有向无环图（DAG） 的单源最短路径算法。它利用 DAG 的拓扑序特性，高效地计算从源点到所有其他顶点的最短路径，并且允许边权为负。
算法步骤
- 拓扑排序：获取 DAG 的拓扑序列（例如使用 Kahn 算法或 DFS）。
- 初始化：
- 距离数组
dist[]：dist[s] = 0（源点），其余顶点初始化为无穷大（∞）。
- 前驱数组
edgeTo[]：记录最短路径的边。
- 按拓扑序松弛边：
- 对拓扑序列中的每个顶点
v：
- 对
v的每条出边 v->w：
- 若
dist[w] > dist[v] + weight(v->w)，则更新 dist[w] 和edgeTo[w]。
特别地，如果要求最长路，则给所有边权取相反数，然后求最短路，即为最长路。
字典树（Trie）