1. 概述

在本教程中,我们将介绍图(Graph)这种数据结构的基本概念,并探讨它在 Java 中的具体实现方式、常见操作,以及可用于图处理的主流 Java 库。

图是一种用于表示相互连接的数据结构,例如社交网络中用户之间的关系。

2. 图数据结构

图由顶点(Vertex)和边(Edge)组成

  • 顶点表示实体(例如人)
  • 边表示实体之间的关系(例如朋友关系)

我们来看一个简单的图示例:

graph1

这是一个包含五个顶点和六条边的无向图。圆圈代表人,连线代表他们在某个在线平台上的好友关系。

根据边的不同属性,图可以分为以下几种类型,我们将在后续章节简要介绍。但为了保持代码示例简洁,本文将主要围绕“简单无权无向图”展开。

2.1. 有向图

如果图中的边具有方向性,则该图为有向图(Directed Graph)

例如,可以用来表示谁发出了好友请求:

graph2

可以看到,图中每条边都有明确的方向。有些边可能是双向的。

2.2. 带权图

如果图中的边带有权重(Weight),则称为带权图(Weighted Graph)

比如可以表示好友关系建立的时间长短:

graph3

可以看到,每条边上都标注了数值,表示关系的强度或时间。

3. 图的表示方式

图可以用多种方式表示,常见的包括邻接矩阵(Adjacency Matrix)邻接表(Adjacency List)。两者各有优劣。

3.1. 邻接矩阵

邻接矩阵是一个大小为 V×V 的二维数组(V 是顶点数)。

  • 矩阵元素值为 1 表示两个顶点之间存在边
  • 值为 0 表示无边

以我们前面的图为例,其邻接矩阵如下:

graph4

✅ 优点:查询两个顶点是否相连非常高效
❌ 缺点:空间占用较大,尤其是稀疏图时浪费严重

3.2. 邻接表

邻接表是一个数组,每个元素是一个链表(或集合),记录与该顶点相邻的所有顶点。

同样以前面的图为例:

graph5

✅ 优点:节省空间,适合稀疏图
❌ 缺点:查询两个顶点是否相连不如邻接矩阵快

在本教程中,我们将使用邻接表来实现图结构。

4. Java 中的图实现

Java 标准库中没有内置的图结构,但我们可以通过 Java Collections 来实现。

首先定义一个顶点类:

class Vertex {
    String label;
    Vertex(String label) {
        this.label = label;
    }

    // equals and hashCode
}

⚠️ 注意:为了配合 Java 集合框架(如 Map、Set),必须重写 equals()hashCode() 方法

接着定义图类,使用邻接表结构:

class Graph {
    private Map<Vertex, List<Vertex>> adjVertices;
    
    // standard constructor, getters, setters
}

图本质上就是一组顶点和边的集合,我们可以通过 Java 的 Map 来表示邻接表。

5. 图的变更操作

我们来实现图的基本操作,包括添加/删除顶点和边。

添加/删除顶点

void addVertex(String label) {
    adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
}

void removeVertex(String label) {
    Vertex v = new Vertex(label);
    adjVertices.values().stream().forEach(e -> e.remove(v));
    adjVertices.remove(new Vertex(label));
}

添加/删除边

void addEdge(String label1, String label2) {
    Vertex v1 = new Vertex(label1);
    Vertex v2 = new Vertex(label2);
    adjVertices.get(v1).add(v2);
    adjVertices.get(v2).add(v1);
}

void removeEdge(String label1, String label2) {
    Vertex v1 = new Vertex(label1);
    Vertex v2 = new Vertex(label2);
    List<Vertex> eV1 = adjVertices.get(v1);
    List<Vertex> eV2 = adjVertices.get(v2);
    if (eV1 != null)
        eV1.remove(v2);
    if (eV2 != null)
        eV2.remove(v1);
}

构建图示例

Graph createGraph() {
    Graph graph = new Graph();
    graph.addVertex("Bob");
    graph.addVertex("Alice");
    graph.addVertex("Mark");
    graph.addVertex("Rob");
    graph.addVertex("Maria");
    graph.addEdge("Bob", "Alice");
    graph.addEdge("Bob", "Rob");
    graph.addEdge("Alice", "Mark");
    graph.addEdge("Rob", "Mark");
    graph.addEdge("Alice", "Maria");
    graph.addEdge("Rob", "Maria");
    return graph;
}

获取相邻顶点

List<Vertex> getAdjVertices(String label) {
    return adjVertices.get(new Vertex(label));
}

6. 图的遍历

图的遍历是很多图算法的基础,常见的有深度优先遍历(DFS)广度优先遍历(BFS)

6.1. 深度优先遍历(DFS)

深度优先遍历会沿着一条路径尽可能深入,然后再回溯。

Set<String> depthFirstTraversal(Graph graph, String root) {
    Set<String> visited = new LinkedHashSet<String>();
    Stack<String> stack = new Stack<String>();
    stack.push(root);
    while (!stack.isEmpty()) {
        String vertex = stack.pop();
        if (!visited.contains(vertex)) {
            visited.add(vertex);
            for (Vertex v : graph.getAdjVertices(vertex)) {              
                stack.push(v.label);
            }
        }
    }
    return visited;
}

✅ 使用栈(Stack)实现
🧪 示例测试:

@Test
public void givenAGraph_whenTraversingDepthFirst_thenExpectedResult() {
    Graph graph = createGraph();
    assertEquals("[Bob, Rob, Maria, Alice, Mark]", 
      GraphTraversal.depthFirstTraversal(graph, "Bob").toString());
}

6.2. 广度优先遍历(BFS)

广度优先遍历会先访问当前层的所有顶点,再进入下一层。

Set<String> breadthFirstTraversal(Graph graph, String root) {
    Set<String> visited = new LinkedHashSet<String>();
    Queue<String> queue = new LinkedList<String>();
    queue.add(root);
    visited.add(root);
    while (!queue.isEmpty()) {
        String vertex = queue.poll();
        for (Vertex v : graph.getAdjVertices(vertex)) {
            if (!visited.contains(v.label)) {
                visited.add(v.label);
                queue.add(v.label);
            }
        }
    }
    return visited;
}

✅ 使用队列(Queue)实现
🧪 示例测试:

@Test
public void givenAGraph_whenTraversingBreadthFirst_thenExpectedResult() {
    Graph graph = createGraph();
    assertEquals("[Bob, Alice, Rob, Mark, Maria]", 
      GraphTraversal.breadthFirstTraversal(graph, "Bob").toString());
}

7. 初始化与打印图

我们可以编写一个简单的 Java 应用来初始化并打印图结构:

static Graph createGraph() {
    Graph graph = new Graph();
    graph.addVertex("Bob");
    graph.addVertex("Alice");
    graph.addVertex("Mark");
    graph.addVertex("Rob");
    graph.addVertex("Maria");
    graph.addEdge("Bob", "Maria");
    graph.addEdge("Bob", "Mark");
    graph.addEdge("Maria", "Alice");
    graph.addEdge("Mark", "Alice");
    graph.addEdge("Maria", "Rob");
    graph.addEdge("Mark", "Rob");

    return graph;
}

public static void main(String[] args) {
    Graph graph = createGraph();
    Set result = GraphTraversal.breadthFirstTraversal(graph, "Bob");
    System.out.println(result.toString());   
}

输出结果:

[Bob, Maria, Mark, Alice, Rob]

8. Java 图处理库

在实际开发中,我们并不总是需要从零实现图结构。以下是一些优秀的 Java 图处理库:

8.1. JGraphT

JGraphT 是 Java 中最流行的图处理库之一,支持创建简单图、有向图、带权图等,并提供大量图算法实现。

8.2. Google Guava

Google Guava 提供了 GraphValueGraphNetwork 接口,支持可变和不可变图。

8.3. Apache Commons Graph

Apache Commons Graph 是 Apache 提供的图结构工具包,支持常见图算法。

8.4. JUNG

Java Universal Network/Graph (JUNG) 是一个功能强大的图建模与可视化框架,支持聚类、分解、优化等算法。

这些库不仅提供图结构的实现,还支持更高级的图处理框架,例如:

9. 总结

在本文中,我们介绍了图的基本概念、表示方式,并用 Java 实现了简单的图结构。我们还演示了图的遍历方法(DFS 和 BFS),并介绍了常用的图处理库。

图结构是很多高级算法和系统的基础,掌握它的实现与应用对 Java 开发者来说非常重要。


原始标题:Graphs in Java | Baeldung