CS61B 课程笔记（DISC 12 Graphs, Sorting)

题目：
对于下图，设 \(g(u, v)\) 为节点 \(u\) 和 \(v\) 之间边的权重。设 \(h(u, v)\) 为任意节点 \(u\) 和 \(v\) 的启发式值。

分析：
使用Dijkstra算法找到从A到每个其他顶点的最短路径。可以使用一个优先队列来跟踪当前的距离。

最终结果：

分析：
A*搜索从A开始，目标为G，返回的路径是 \(A \rightarrow D \rightarrow E \rightarrow G\)。

分析：
一个启发式值是可接受的，当且仅当它的所有估计值 \(h(x)\) 都是乐观的。这里的启发式不是可接受的，因为从A到G的实际最短路径的成本是7，但启发式估计为8。

题目：
给定图的边权重，使用Prim算法和Kruskal算法找到最小生成树。

    A
   / \
  1   2
 /     \
B---2---C
|       |
1       3
|       |
D---2---E
   |
   1
   |
   F

分析：
选择A作为起始节点。每次处理成本相同的节点时，按字母顺序处理。

最小生成树结果：

分析：
Kruskal算法将会输出与Prim算法相同的最小生成树。这并不总是如此。

分析：
可以找到多个最小生成树。用权重为2的边有3个可替换的选择，用权重为3的边有2个可替换的选择。因此，总共有 \(3 \times 2 = 6\) 种可能的最小生成树。

题目：
对以下无序列表进行排序：0, 4, 2, 7, 6, 1, 3, 5

步骤：

0 | 4 2 7 6 1 3 5
0 4 | 2 7 6 1 3 5
0 2 4 | 7 6 1 3 5
0 2 4 7 | 6 1 3 5
0 2 4 6 7 | 1 3 5
0 1 2 4 6 7 | 3 5
0 1 2 3 4 6 7 | 5
0 1 2 3 4 5 6 7 |

步骤：

0 | 4 2 7 6 1 3 5
0 1 | 2 7 6 4 3 5
0 1 2 | 7 6 4 3 5
0 1 2 3 | 6 4 7 5
0 1 2 3 4 | 6 7 5
0 1 2 3 4 5 | 7 6
0 1 2 3 4 5 6 | 7
0 1 2 3 4 5 6 7 |

步骤：

0 4 2 7 6 1 3 5
0 4 | 2 7 | 6 1 | 3 5
0 2 4 | 7 | 1 6 | 3 5
0 1 2 3 4 5 6 7

步骤：

6 4 2 0 7

4 0 2 6 7

2 0 4 6 7

0 2 4 6 7

0 2 4 6 7