4.图论
4.1 无向图
4.1.1 DFS连通性与路径
public Iterable<Integer> pathTo(int v) {
// 少了检查和hasPathTo检查
checkIndex(v);
if (!hasPathTo(v)) {
return null;
}
ArrayDeque<Integer> stack = new ArrayDeque<>();
// 这里计算路径时出了错误,越简洁越不容易处错误
for (int w = v; w != s; w = edgeTo[w]) {
stack.push(w);
}
4.1.2 DFS连通分量
4.1.3 DFS检测环
4.1.4 DFS检查二分图
4.1.5 BFS最短路径
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w : G.adj(v)) {
if (!marked[w]) {
// 严重的错误:这里忘记标记marked[w]!
marked[w] = true;
4.2 最小生成树
4.2.1 无向加权图
// 不要忘了更新E
E++;
public Iterable<Edge> adj(int v) {
// 不要忘了对入参进行检查
checkIndex(v);
return adj.get(v);
}
4.2.2 延时Prim算法
4.2.3 即时Prim算法
4.2.4 Kruskal算法
4.3 有向图
4.3.1 DFS单点连通性与路径
4.3.2 拓扑排序
private void dfs(int v) {
marked[v] = true;
onStack[v] = true;
for (int w : G.adj(v)) {
if (hasCycle()) {
return;
}
if (!marked[w]) {
edgeTo[w] = v;
dfs(w);
} else if (onStack[w]) {
cycle = new ArrayDeque<>();
cycle.push(w);
for (int u = v; u != w; u = edgeTo[u]) {
cycle.push(u);
}
cycle.push(w);
}
}
// 特别注意,不要忘了这个,递归代码必须遵守的规则
onStack[v] = false;
}
4.3.3 强联通分量
4.3.4 BFS最短路径
4.4 最短路径
4.4.1 非负权重边Dijkstra算法
4.4.2 无环
4.4.3 普通情况(无负权重环)——Bellman-Ford
// 之前未注意存在正无穷!
Arrays.fill(distTo, Double.POSITIVE_INFINITY);
4.5 最大流
网友评论