掌握图算法从零开始（Java语言图算法入门与实战教程）

图的表示方法

在Java中，我们通常用两种方式表示图：

• 邻接矩阵（Adjacency Matrix）：使用二维数组，适合稠密图。
• 邻接表（Adjacency List）：使用链表或ArrayList，适合稀疏图，更节省空间。

本教程采用邻接表实现，因为它更常用且高效。

Java实现图结构

首先，我们定义一个简单的图类：

import java.util.*;public class Graph {    private int vertices; // 节点数量    private LinkedList<Integer> adjList[]; // 邻接表    // 构造函数    public Graph(int vertices) {        this.vertices = vertices;        adjList = new LinkedList[vertices];        for (int i = 0; i < vertices; i++) {            adjList[i] = new LinkedList<>();        }    }    // 添加边    public void addEdge(int src, int dest) {        adjList[src].add(dest);        // 如果是无向图，还需添加反向边        // adjList[dest].add(src);    }}

深度优先搜索（DFS）

深度优先搜索（DFS）是一种用于遍历或搜索图的算法。它从起始节点出发，沿着一条路径尽可能深地搜索，直到无法继续为止，然后回溯并尝试其他路径。

DFS常用于检测环、拓扑排序、连通分量等问题。

// DFS辅助方法public void DFS(int startVertex) {    boolean visited[] = new boolean[vertices];    DFSUtil(startVertex, visited);}private void DFSUtil(int vertex, boolean visited[]) {    visited[vertex] = true;    System.out.print(vertex + " ");    Iterator<Integer> it = adjList[vertex].listIterator();    while (it.hasNext()) {        int adj = it.next();        if (!visited[adj]) {            DFSUtil(adj, visited);        }    }}

广度优先搜索（BFS）

广度优先搜索（BFS）从起始节点开始，逐层向外扩展，先访问所有相邻节点，再访问相邻节点的相邻节点。它使用队列（Queue）来管理待访问节点。

BFS常用于求最短路径（无权图）、社交网络中的“六度分隔”等问题。

// BFS实现public void BFS(int startVertex) {    boolean visited[] = new boolean[vertices];    LinkedList<Integer> queue = new LinkedList<>();    visited[startVertex] = true;    queue.add(startVertex);    while (!queue.isEmpty()) {        int current = queue.poll();        System.out.print(current + " ");        Iterator<Integer> it = adjList[current].listIterator();        while (it.hasNext()) {            int adj = it.next();            if (!visited[adj]) {                visited[adj] = true;                queue.add(adj);            }        }    }}

完整示例与运行

下面是一个完整的测试程序，演示如何创建图并执行DFS和BFS：

public class Main {    public static void main(String[] args) {        Graph g = new Graph(5);        g.addEdge(0, 1);        g.addEdge(0, 2);        g.addEdge(1, 3);        g.addEdge(2, 4);        System.out.println("DFS遍历结果:");        g.DFS(0); // 输出: 0 1 3 2 4        System.out.println("\nBFS遍历结果:");        g.BFS(0); // 输出: 0 1 2 3 4    }}

总结

通过本教程，你已经掌握了Java图算法的基础知识，包括图的表示、深度优先搜索和广度优先搜索的实现。这些是解决更复杂图问题（如最短路径、最小生成树）的基石。

建议你动手编写代码、修改示例，并尝试解决实际问题（如迷宫求解、社交网络好友推荐）。实践是掌握图的遍历的最佳方式！

记住：每一个复杂的图算法，都始于一次简单的DFS或BFS调用。