Java数据结构之有向图设计与实现详解

什么是有向图

有向图是一种图形结构，其中每一个节点都有一个方向，即它指向或被其他节点指向。有向图可以用来表示许多实际问题，如路线、依赖关系、状态转移等。

有向图的基本概念

在有向图中，每一个节点都有一个唯一的标识符，被称为节点ID。如果从节点A到节点B存在一条有向边，则称B是A的后继节点，A是B的前驱节点。节点的度数是指它的入度和出度之和。有向图还有许多其他的概念，如顶点、边、邻接矩阵等，在此就不一一列举了。

有向图的实现

在Java中，实现有向图可以使用邻接矩阵或邻接表。其中邻接矩阵是一个二维数组，表示图中每个节点之间的连接关系。邻接表则是一个链表数组，每个链表对应一个节点，包含与该节点直接相连的其他节点。

以下是使用邻接表实现有向图的示例代码：

public class DirectedGraph {
    private List<Integer>[] adj;

    public DirectedGraph(int numNodes) {
        adj = new List[numNodes];
        for (int i = 0; i < numNodes; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    public void addEdge(int from, int to) {
        adj[from].add(to);
    }

    public List<Integer> getNeighbors(int node) {
        return adj[node];
    }
}

上述代码中，DirectedGraph类表示有向图，adj数组是一个链表数组，用于存储每个节点与其相邻的节点。在构造函数中，我们创建numNodes个空链表，并将它们保存在adj数组中。每条边由其起始节点和终止节点组成，可以使用addEdge方法来向有向图中添加一条边。最后，getNeighbors方法可以返回与给定节点相邻的所有节点。

以下是使用邻接矩阵实现有向图的示例代码：

public class DirectedGraph {
    private int[][] adj;

    public DirectedGraph(int numNodes) {
        adj = new int[numNodes][numNodes];
    }

    public void addEdge(int from, int to) {
        adj[from][to] = 1;
    }

    public List<Integer> getNeighbors(int node) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < adj[node].length; i++) {
            if (adj[node][i] == 1) {
                res.add(i);
            }
        }
        return res;
    }
}

与邻接表不同，邻接矩阵中的每个元素表示一个节点对应的入度和出度之和。在构造函数中，我们创建一个大小为numNodes x numNodes的二维数组。每条边由其起始节点和终止节点组成，可以使用addEdge方法来向二维数组中对应位置赋值。最后，getNeighbors方法可以返回与给定节点相邻的所有节点。

示例1

假设我们要构建一个有向图，其中有5个节点，分别标记为0到4。其中0号节点指向2号节点，2号节点指向1号和3号节点，3号节点指向4号节点。以下是使用邻接表实现该有向图的示例代码：

DirectedGraph graph = new DirectedGraph(5);
graph.addEdge(0, 2);
graph.addEdge(2, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 4);

List<Integer> neighbors = graph.getNeighbors(2);
System.out.println(neighbors); // [1, 3]

在上面的代码中，我们首先创建了一个有向图，然后向其中添加了4条边，从0号节点指向2号节点，从2号节点指向1号和3号节点，从3号节点指向4号节点。最后，我们通过调用getNeighbors方法来获取2号节点的邻居节点。输出结果为[1, 3]，符合预期。

示例2

假设我们要构建一个有向图，其中有4个节点，分别标记为A、B、C和D。其中A指向B和C，C指向D，D指向A和B。以下是使用邻接矩阵实现该有向图的示例代码：

DirectedGraph graph = new DirectedGraph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
graph.addEdge(3, 1);

List<Integer> neighbors = graph.getNeighbors(0);
System.out.println(neighbors); // [1, 2]

在上面的代码中，我们首先创建了一个有向图，然后向其中添加了5条边，从A指向B和C，从C指向D，从D指向A和B。最后，我们通过调用getNeighbors方法来获取A节点的邻居节点。输出结果为[1, 2]，符合预期。