图的算法分析

好久没聊图了，这东西在算法体系里，跟一头巨兽一样，看着唬人，但一旦摸清了它的脾气，驯服它也就是时间问题。很多面试官就喜欢拿图来考验候选人，因为它能一下看出来你对数据结构、算法、抽象建模的能力。

第一关：怎么把一张图告诉计算机？

你脑子里有一张地图，上面有城市（点），有公路（边）。这玩意怎么用代码表示出来？这其实就是算法的第一步：建模。同样一张图，可以用不同的数据结构来描述，各有优劣。没有最好的，只有最合适的。

解法一：邻接矩阵 (Adjacency Matrix) - 最直观的暴力

刚接触图，我脑子里第一个蹦出来的想法就是，这不就是一个关系网嘛。两个点之间要么有关系，要么没关系。我可以用一个二维数组，一个矩阵来表示。

比如有 N 个点，我就搞一个 N*N 的 int[][] matrix。matrix[i][j] = 1 就表示点 i 和点 j 之间有条边，如果是 0 就表示没边。如果边有权重，那这里就存权重值。

// 假设有 4 个节点 (0, 1, 2, 3)
int N = 4;
int[][] matrix = new int[N][N];

// 0 -> 1
matrix[0][1] = 1;
// 0 -> 2
matrix[0][2] = 1;
// 1 -> 3
matrix[1][3] = 1;
// 2 -> 3
matrix[2][3] = 1;

// 如果是无向图, 记得要对称
// 1 -> 0
matrix[1][0] = 1; 
// ...以此类推

思路分析：

优点：简单粗暴，非常直观。查询两个点之间是否有边，速度飞快，O(1) 的复杂度，直接访问数组就行。
缺点：太浪费空间了！如果一个图有一万个节点，但只有几百条边（这种叫稀疏图），你为了这几百条边，硬生生开了一个 10000 * 10000 的巨大数组，里面绝大部分都是 0，内存直接就爆了。空间复杂度是 O(V²)，V 是节点数。

这方案，面试的时候一提，能证明你思考过最基础的情况，但如果只说这个，那基本就凉了。

解法二：邻接表 (Adjacency List) - 精打细算的标配

既然邻接矩阵浪费空间，那咱们就按需分配。每个点，我只关心它跟谁有连接，我用一个列表把它的邻居都存起来不就行了？

可以用一个 Map 或者一个 List 数组来实现。Map 的 key 是节点，value 是一个 List，装着它所有的邻居。

// 节点可以是任何类型，这里用 Integer 举例
Map<Integer, List<Integer>> adjList = new HashMap<>();

// 添加边 0 -> 1 和 0 -> 2
adjList.putIfAbsent(0, new ArrayList<>());
adjList.get(0).add(1);
adjList.get(0).add(2);

// 添加边 1 -> 3
adjList.putIfAbsent(1, new ArrayList<>());
adjList.get(1).add(3);

// 添加边 2 -> 3
adjList.putIfAbsent(2, new ArrayList<>());
adjList.get(2).add(3);

// 对于节点3，它没有出度（没有指向别人的边），可能是空的List
adjList.putIfAbsent(3, new ArrayList<>());

思路分析：

优点：空间效率极高。有多少条边，就耗费多少存储空间（再加上节点的存储）。空间复杂度是 O(V+E)，V是节点数，E是边数。这对于稀疏图来说是巨大的优化。遍历一个节点的所有邻居也非常方便。
缺点：查询两个特定节点 u 和 v 之间是否有边，就没那么快了。你需要遍历 u 的邻居列表，看看里面有没有 v，复杂度是 O(k)，k 是 u 节点的度（邻居数量）。

邻接表是图的标准表示法，绝大多数场景下都是最优选。面试时能写出这个，说明你基本功是过关的。

解法三：自定义对象结构 - 面向对象的终极形态

上面的邻接表虽然好，但还是有点“原始”，所有的信息都散落在 Map 和 List 里。一个真正的软件工程项目，我们更喜欢用自定义的类来封装数据和行为。这种方式是对图最精准、最灵活的描述。

咱们可以定义三个类：Node（节点）、Edge（边）、Graph（图）。

// 节点类
public class Node {
    public int value; // 节点的值
    public int in;    // 入度
    public int out;   // 出度
    public List<Node> nexts; // 直接邻居
    public List<Edge> edges; // 从我出发的边

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

// 边类
public class Edge {
    public int weight; // 权重
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

// 图类
public class Graph {
    public Map<Integer, Node> nodes; // 节点集合 (Integer是节点编号)
    public Set<Edge> edges;         // 边集合

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

当你要构建一张图时，你创建的是这些类的实例，并把它们之间的关系建立起来。比如，有一条从节点A到节点B，权重为10的边，你就 new Edge(10, nodeA, nodeB)，然后把它加到 nodeA 的 edges 列表和整个 graph 的 edges 集合里。

思路分析：

优点：结构最清晰，扩展性最强。想给节点加个属性？改 Node 类。想给边加个类型？改 Edge 类。所有的信息都被完美地封装，非常符合面向对象的思想。对于复杂的算法，比如Dijkstra、Prim等，这种结构处理边的权重、节点的附加信息时会非常方便。
缺点：比邻接表稍微复杂一点，代码量多一些。但这点付出对于换来的清晰和扩展性来说，完全值得。

这种方法是你解决复杂图问题的利器。它不仅仅是表示图，更是在用面向对象的方式设计图。

第二关：怎么在图里溜达？图的遍历

把图装进内存了，接下来就要在里面走一走，看一看。怎么才能不重不漏地访问所有节点呢？主要就两种策略：广度优先和深度优先。

假设我们用的是上面第三种自定义结构。

解法一：广度优先遍历 (BFS) - 一圈一圈往外浪

BFS，我喜欢叫它“水波纹”遍历。从一个起点开始，就像往水里扔了块石头，先访问离它最近的一圈，再访问次近的一圈，一层一层地往外扩散。

要实现这种一层一层的效果，什么数据结构最合适？队列！先进先出，完美符合我们的要求。

思路：

准备一个队列 queue，用来存放待访问的节点。
准备一个 Set，用来记录哪些节点已经访问过（或者已经加进队列了），防止走回头路或者在环里死循环。
把起始节点 start 放进队列，并加入 Set。
只要队列不空，就循环：
- 从队列里弹出一个节点 cur。
- 处理 cur（比如打印）。
- 遍历 cur 所有的邻居 next。
- 如果 next 不在 Set 里，说明是第一次遇到，就把它加进队列，并加入 Set。

public static void bfs(Node start) {
    if (start == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    Set<Node> set = new HashSet<>(); // 用来记录已访问或已入队的节点

    queue.add(start);
    set.add(start);

    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value); // 处理当前节点

        for (Node next : cur.nexts) {
            if (!set.contains(next)) {
                set.add(next);
                queue.add(next);
            }
        }
    }
}

BFS 的一个巨大应用就是找无权图的最短路径，因为它是一层一层搜的，第一次搜到目标节点时，走过的路径一定是最短的。

解法二：深度优先遍历 (DFS) - 一条道走到黑

DFS，我管它叫“不撞南墙不回头”。从一个起点开始，随便选一个邻居，一条路走下去，直到走不通了（没有未访问的邻居了），再退回来，换条路继续走。

这种“后进先出”的回溯特性，用什么数据结构实现？栈！

思路：

准备一个栈 stack。
准备一个 Set，作用同BFS。
把起始节点 start 压入栈，并加入 Set。
只要栈不空，就循环：
- 从栈里弹出一个节点 cur。
- 处理 cur（比如打印）。
- 遍历 cur 所有的邻居 next。（注意这里压栈的顺序可能影响遍历结果）
- 如果 next 不在 Set 里，就把它加入 Set，并压入栈。

public static void dfs(Node start) {
    if (start == null) {
        return;
    }
    Stack<Node> stack = new Stack<>();
    Set<Node> set = new HashSet<>();

    stack.push(start);
    set.add(start);
    System.out.println(start.value); // 注意：入栈时就处理

    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        for (Node next : cur.nexts) {
            if (!set.contains(next)) {
                // 找到了一个没走过的邻居
                stack.push(cur); // 把自己再压回去，方便回溯
                stack.push(next); // 把新邻居压进去
                set.add(next);
                System.out.println(next.value); // 处理新节点
                break; // 立刻以新节点为起点，深入下去
            }
        }
    }
}

这个非递归版的DFS实现有点小技巧，需要把当前节点也压回去才能保证回溯时能探索其他分支。

解法三：递归版 DFS - 最优雅的写法

其实，系统函数调用的栈本身就是一个天然的栈结构。所以DFS用递归写起来，代码会极其简洁优美。

思路：

写一个递归函数 process(node, set)。
base case：如果 node 是 null，直接返回。
在 set 中检查 node 是否被访问过，如果是，也直接返回。
将 node 加入 set，并处理 node（比如打印）。
遍历 node 的所有邻居 next，对每个 next 递归调用 process(next, set)。

public static void dfsRecursive(Node start) {
    if (start == null) {
        return;
    }
    Set<Node> set = new HashSet<>();
    process(start, set);
}

private static void process(Node node, Set<Node> set) {
    // base case 隐含在 for 循环的结束和下面的 if 判断
    if (set.contains(node)) {
        return;
    }

    set.add(node);
    System.out.println(node.value); // 处理当前节点

    for (Node next : node.nexts) {
        process(next, set);
    }
}

递归写法的逻辑和“一条道走到黑”的思想完全吻合，非常清晰。DFS 在寻找路径、拓扑排序、检测环等问题上非常有用。

总结一下

今天咱们就干了两件事：

如何描述图：
- 邻接矩阵：暴力直观，空间换时间，适合稠密图。
- 邻接表：省空间，工业标准，适合稀疏图。
- 自定义对象：最灵活，扩展性最强，是复杂算法和工程实践的基础。
如何遍历图：
- BFS：用队列，一层一层地访问，天生适合解决最短路径问题。
- DFS (栈)：用栈，一条路走到黑，再回头。
- DFS (递归)：利用系统栈，代码优雅，逻辑自然。