Java 中的图数据结构

介绍

在本教程中，你将学习如何在 Java 中创建和操作图（graph）数据结构。图是一种用于表示对象之间关系的基本数据结构。我们将探讨不同类型的图、如何表示它们，以及如何实现常见的操作，例如添加和删除顶点（vertices）和边（edges）、广度优先搜索（breadth-first search）、深度优先搜索（depth-first search）等。

Skills Graph

创建 Node 类

首先，我们将创建一个 Node 类来表示图中的顶点（vertices）。每个节点将有一个名称，可能还包含其他信息，例如值或权重。

public class Node {
    private String name;

    public Node(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

创建 Graph 类

接下来，我们将创建一个 Graph 类来表示图本身。我们将使用邻接表（adjacency list）来存储边及其端点。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {
    private Map<Node, List<Node>> adjacencyList;

    public Graph() {
        this.adjacencyList = new HashMap<>();
    }

    public void addNode(Node node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(Node node1, Node node2) {
        adjacencyList.get(node1).add(node2);
        adjacencyList.get(node2).add(node1);
    }

    public void removeNode(Node node) {
        adjacencyList.values().stream().forEach(e -> e.remove(node));
        adjacencyList.remove(node);
    }

    public void removeEdge(Node node1, Node node2) {
        List<Node> list1 = adjacencyList.get(node1);
        List<Node> list2 = adjacencyList.get(node2);
        if (list1 != null) {
            list1.remove(node2);
        }
        if (list2 != null) {
            list2.remove(node1);
        }
    }

    public List<Node> getNeighbors(Node node) {
        return adjacencyList.get(node);
    }
}

创建图

现在，让我们创建一个图并添加一些节点和边。

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

广度优先搜索

现在，我们将实现一个广度优先搜索（Breadth-First Search, BFS）算法，以广度优先的顺序遍历图中的节点。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class BreadthFirstSearch {
    public List<Node> bfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            List<Node> neighbors = graph.getNeighbors(node);
            for (Node neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return visited;
    }
}

运行示例：

javac Graph.java BreadthFirstSearch.java Node.java && java BreadthFirstSearch

深度优先搜索

现在，我们将实现一个深度优先搜索（Depth-First Search, DFS）算法，以深度优先的顺序遍历图中的节点。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DepthFirstSearch {
    public List<Node> dfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        dfsHelper(graph, start, visited, new HashSet<>());
        return visited;
    }

    private void dfsHelper(Graph graph, Node current, List<Node> visited, Set<Node> seen) {
        visited.add(current);
        seen.add(current);
        for (Node neighbor : graph.getNeighbors(current)) {
            if (!seen.contains(neighbor)) {
                dfsHelper(graph, neighbor, visited, seen);
            }
        }
    }
}

运行示例：

javac Graph.java DepthFirstSearch.java Node.java && java DepthFirstSearch

删除节点

我们可以从图中移除一个节点，同时移除与该节点相连的所有边。

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

graph.removeNode(nodeC);

删除边

我们可以移除图中两个节点之间的边。

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");

graph.addNode(nodeA);
graph.addNode(nodeB);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);

graph.removeEdge(nodeA, nodeB);

总结

在本教程中，我们学习了如何使用节点和邻接表表示法在 Java 中创建图数据结构。我们还实现了操作图的功能，包括添加和删除节点以及边。最后，我们实现了两种搜索算法：广度优先搜索和深度优先搜索。