【DSA】数据结构与算法 04 图
图是由一组顶点和一组能够将两个顶点相连的边组成的。
1 图的存储和遍历
邻接矩阵：V * V 的矩阵。适合稠密图。
- 二维数组中的对角线为 0；
- 某个点的出度就是顶点所在行的元素之和，入度就是顶点所在列的元素之和。
邻接表：以顶点为索引的列表数组。适合稀疏图。
- 用的数组存储每个节点；
- 数组中的每个节点的所有邻接点组成一个链表，这个邻接表就是顶点的出度表。
- 以下算法均基于邻接表实现。
public class Graph {
private int V;
private int E;
private ArrayList<Integer>[] adj;
}
1.1 深度优先遍历（DFS）
private boolean[] marked = new boolean[G.V()];
private int[] edgeTo = new int[G.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);
}
}
1.2 广度优先遍历（BFS）
private boolean[] marked = new boolean[G.V()];
private int[] edgeTo = new int[G.V()];
private void bfs(Graph G, int s) {
Queue<Integer> queue = new LinkedList<Integer>();
marked[s] = true;
queue.offer(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (int w : G.adj(v))
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.offer(w);
}
}
}
2 有向图和拓扑排序
有向图的逆后序序列，就是拓扑排序序列。
public class DepthFirstOrder {
private boolean[] marked;
private Queue<Integer> pre; // 前序排列
private Queue<Integer> post; // 后序排列
private Stack<Integer> reversePost; // 逆后序排列，即为拓扑排序
public DepthFirstOrder(Digraph G) {
pre = new LinkedList<>();
post = new LinkedList<>();
reversePost = new Stack<>();
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
if (!marked[v])
dfs(G, v);
}
private void dfs(Digraph G, int v) {
pre.offer(v);
for (int w : G.adj(v))
if (!marked[w])
dfs(G, w);
post.offer(v);
reversePost.push(v);
}
public Iterable<Integer> topological(Digraph G) {
return new DepthFirstOrder(G).reversePost;
}
}
3 加权图和最小生成树
用 n - 1 条边把 n 个顶点连接起来，且连接起来的权值最小。我们把构造联通网的最小代价生成树称为最小生成树。
3.1 Prim算法
加点法：一开始这棵树只有一个顶点，然后会向它添加 V - 1 条边，每次总是将吓一跳连接树中的顶点与不在树中的顶点且权重最小的边加入树中。
public class PrimMST {
private Edge[] edgeTo; // 从树顶点到非树顶点的最短边
private double[] distTo; // 最短边权重
private boolean[] marked;
private Map<Integer, Double> pq;
public PrimMST(EdgeWeightedGraph G) {
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
pq = new HashMap<>();
distTo[0] = 0.0;
pq.put(0, 0.0);
while (!pq.isEmpty())
visit(G, delMin(pq));
}
private void visit(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (marked[w])
continue;
if (e.weight() < distTo[w]) {
edgeTo[w] = e;
distTo[w] = e.weight();
pq.put(w, distTo[w]);
}
}
}
}
3.2 Kruskal算法
加边法：按照边的权重顺序加入到最小生成树中，加入的边不会与已加入的边构成环，直到树中含有 V - 1 条边。
public class KruskalMST {
private Queue<Edge> mst;
public KruskalMST(EdgeWeightedGraph G) {
ArrayList<Edge> pq = new ArrayList<Edge>();
for (Edge e : G.edges())
pq.add(e);
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V() - 1) {
Edge e = delMin(pq);
int v = e.either();
int w = e.other(v);
if (uf.find(v) != uf.find(w)) {
uf.union(v, w);
mst.offer(e);
}
}
}
}
4 加权有向图和最短路径
Dijkstra 算法：每次为最短路径树添加一条边，该边由一个树中的顶点指向一个非树顶点 w 且它是到 s 最近的顶点。
public class DijkstraSP {
private DirectedEdge[] edgeTo;
private double[] distTo;
private Map<Integer, Double> pq;
public DijkstraSP(EdgeWeightedDigraph G, int s) {
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
pq = new HashMap<>(G.V());
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
pq.put(s, 0.0);
while (!pq.isEmpty())
relax(G, delMin(pq));
}
private void relax(EdgeWeightedDigraph G, int v) {
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
pq.put(w, distTo[w]);
}
}
}
}