树与图的存储

邻接矩阵

在Java中可以使用二维数组来存储邻接矩阵：

int[][] g = new int[N][N]; // 存储边 a->b

邻接表

Java中可以使用数组加链表来实现邻接表：

import java.util.ArrayList;
import java.util.List;

List<Integer>[] graph = new ArrayList[N];

// 初始化
for (int i = 0; i < N; i++) {
    graph[i] = new ArrayList<>();
}

// 添加一条边 a->b
void addEdge(int a, int b) {
    graph[a].add(b);
}

树与图的遍历

深度优先遍历 (DFS)

boolean[] visited = new boolean[N];

void dfs(int u) {
    visited[u] = true; // 标记 u 已被遍历
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

宽度优先遍历 (BFS)

import java.util.LinkedList;
import java.util.Queue;

void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[N];
    visited[start] = true; // 标记起始点已被遍历
    queue.add(start);

    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true; // 标记点 v 已被遍历
                queue.add(v);
            }
        }
    }
}

拓扑排序

boolean topsort() {
    int[] inDegree = new int[N];
    Queue<Integer> queue = new LinkedList<>();

    // 计算每个节点的入度
    for (int i = 1; i <= n; i++) {
        for (int j : graph[i]) {
            inDegree[j]++;
        }
    }

    // 将所有入度为 0 的节点加入队列
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            queue.add(i);
        }
    }

    int count = 0;

    while (!queue.isEmpty()) {
        int u = queue.poll();
        count++;

        for (int v : graph[u]) {
            if (--inDegree[v] == 0) {
                queue.add(v);
            }
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return count == n;
}

朴素 Dijkstra 算法

int[][] g = new int[N][N];  // 存储每条边
int[] dist = new int[N];    // 存储1号点到每个点的最短距离
boolean[] st = new boolean[N]; // 存储每个点的最短路是否已经确定

int dijkstra() {
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }

        st[t] = true;

        for (int j = 1; j <= n; j++) {
            dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
        }
    }

    return dist[n] == Integer.MAX_VALUE ? -1 : dist[n];
}

堆优化版 Dijkstra 算法

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;

class Pair implements Comparable<Pair> {
    int distance, node;

    Pair(int distance, int node) {
        this.distance = distance;
        this.node = node;
    }

    @Override
    public int compareTo(Pair other) {
        return Integer.compare(this.distance, other.distance);
    }
}

int n; // 点的数量
List<Pair>[] graph = new ArrayList[N]; // 邻接表存储所有边
int[] dist = new int[N]; // 存储所有点到1号点的距离
boolean[] st = new boolean[N]; // 存储每个点的最短距离是否已确定

int dijkstra() {
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[1] = 0;

    PriorityQueue<Pair> heap = new PriorityQueue<>();
    heap.add(new Pair(0, 1)); // 距离为0, 节点编号1

    while (!heap.isEmpty()) {
        Pair t = heap.poll();
        int ver = t.node, distance = t.distance;

        if (st[ver]) continue;
        st[ver] = true;

        for (Pair edge : graph[ver]) {
            int j = edge.node, w = edge.distance;
            if (dist[j] > distance + w) {
                dist[j] = distance + w;
                heap.add(new Pair(dist[j], j));
            }
        }
    }

    return dist[n] == Integer.MAX_VALUE ? -1 : dist[n];
}

Bellman-Ford 算法

int n, m; // n表示点数，m表示边数
int[] dist = new int[N]; // dist[x]存储1到x的最短路距离

class Edge {
    int a, b, w;

    Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
}

Edge[] edges = new Edge[M];

int bellmanFord() {
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[1] = 0;

    for (int i = 0; i < n; i++) {
        for (Edge edge : edges) {
            int a = edge.a, b = edge.b, w = edge.w;
            if (dist[a] != Integer.MAX_VALUE && dist[b] > dist[a] + w) {
                dist[b] = dist[a] + w;
            }
        }
    }

    return dist[n] == Integer.MAX_VALUE ? -1 : dist[n];
}

SPFA 算法 (队列优化的 Bellman-Ford 算法)

import java.util.LinkedList;
import java.util.Queue;

int n; // 总点数
List<Pair>[] graph = new ArrayList[N]; // 邻接表存储所有边
int[] dist = new int[N]; // 存储每个点到1号点的最短距离
boolean[] st = new boolean[N]; // 存储每个点是否在队列中

int spfa() {
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[1] = 0;

    Queue<Integer> queue = new LinkedList<>();
    queue.add(1);
    st[1] = true;

    while (!queue.isEmpty()) {
        int t = queue.poll();
        st[t] = false;

        for (Pair edge : graph[t]) {
            int j = edge.node, w = edge.distance;
            if (dist[j] > dist[t] + w) {
                dist[j] = dist[t] + w;
                if (!st[j]) {
                    queue.add(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n] == Integer.MAX_VALUE ? -1 : dist[n];
}

Floyd 算法

int[][] d = new int[N][N];

// 初始化
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == j) d[i][j] = 0;
        else d[i][j] = INF;
    }
}

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

朴素版 Prim 算法

int n; // n表示点数
int[][] g = new int[N][N]; // 邻接矩阵，存储所有边
int[] dist = new int[N]; // 存储其他点到当前最小生成树的距离
boolean[] st = new boolean[N]; // 存储每个点是否已经在生成树中

int prim() {
    Arrays.fill(dist, Integer.MAX_VALUE);

    int res = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))

 {
                t = j;
            }
        }

        if (i > 0 && dist[t] == Integer.MAX_VALUE) return Integer.MAX_VALUE;

        if (i > 0) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j++) {
            dist[j] = Math.min(dist[j], g[t][j]);
        }
    }

    return res;
}

Kruskal 算法

import java.util.Arrays;

class Edge implements Comparable<Edge> {
    int a, b, w;

    Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.w, other.w);
    }
}

int[] p = new int[N]; // 并查集的父节点数组

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    Arrays.sort(edges);

    for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集

    int res = 0, cnt = 0;
    for (Edge edge : edges) {
        int a = edge.a, b = edge.b, w = edge.w;
        a = find(a);
        b = find(b);
        if (a != b) { // 如果两个连通块不连通，则将这两个连通块合并
            p[a] = b;
            res += w;
            cnt++;
        }
    }

    return cnt < n - 1 ? Integer.MAX_VALUE : res;
}

染色法判别二分图

int[] color = new int[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

boolean dfs(int u, int c) {
    color[u] = c;
    for (int v : graph[u]) {
        if (color[v] == -1) {
            if (!dfs(v, 1 - c)) return false;
        } else if (color[v] == c) return false;
    }
    return true;
}

boolean check() {
    Arrays.fill(color, -1);
    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            if (!dfs(i, 0)) return false;
        }
    }
    return true;
}

匈牙利算法

int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
List<Integer>[] graph = new ArrayList[N]; // 邻接表存储所有边
int[] match = new int[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
boolean[] st = new boolean[N]; // 表示第二个集合中的每个点是否已经被遍历过

boolean find(int x) {
    for (int v : graph[x]) {
        if (!st[v]) {
            st[v] = true;
            if (match[v] == 0 || find(match[v])) {
                match[v] = x;
                return true;
            }
        }
    }
    return false;
}

// 求最大匹配数
int hungarian() {
    int res = 0;
    for (int i = 1; i <= n1; i++) {
        Arrays.fill(st, false);
        if (find(i)) res++;
    }
    return res;
}