图的存储与遍历

int[][] adj = new int[n][n]; // adj[i][j] = 权重（0 表示无边）
// 适合稠密图，空间 O(V²)

List<Integer>[] adj = new ArrayList[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
// 加边
adj[u].add(v);
adj[v].add(u); // 无向图
// 适合稀疏图，空间 O(V+E)

int[][] edges = new int[m][3]; // {from, to, weight}
// 适合 Kruskal、Bellman-Ford 等按边操作的算法

boolean[] visited;

void dfs(int u, List<Integer>[] adj) {
    visited[u] = true;
    // 处理节点 u
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj);
        }
    }
}

// 非连通图：遍历所有连通分量
for (int i = 0; i < n; i++) {
    if (!visited[i]) dfs(i, adj);
}

void dfsIterative(int start, List<Integer>[] adj) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) stack.push(v);
        }
    }
}

int[] bfs(int start, List<Integer>[] adj) {
    int n = adj.length;
    int[] dist = new int[n];
    Arrays.fill(dist, -1);
    dist[start] = 0;
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue.offer(v);
            }
        }
    }
    return dist; // 最短距离（无权图）
}