有向图的表示与动态选择算法

引言

在图论中，有向图是一类节点之间具有方向关系的图结构。在实际应用中，我们常常需要对有向图进行表示和操作。为了提高效率，我们可以根据图的规模和操作频率来动态选择适当的数据结构进行表示。

邻接表 vs 邻接矩阵

邻接表

邻接表是一种用于表示图的数据结构，它通过为每个节点维护一个相邻节点的列表来描述图的结构。这种表示方式适合于稀疏图，它可以节省大量的内存空间，同时能够高效地遍历每个节点的相邻节点。

优点：

• 空间效率高，适合表示稀疏图。
• 高效地遍历每个节点的相邻节点。

缺点：

• 查找特定边的效率较低，需要遍历相邻节点列表。

邻接矩阵

邻接矩阵是另一种用于表示图的数据结构，它通过一个二维矩阵来描述节点之间的连接关系。这种表示方式适合于稠密图，它能够高效地查找特定边的存在与否。

优点：

• 高效地查找特定边的存在与否。
• 适合表示稠密图。

缺点：

• 空间效率较低，会消耗大量内存空间。

AdaptiveGraph 类的设计优势

AdaptiveGraph 类是一个根据节点数量和添加边的次数动态选择使用邻接矩阵或邻接表表示的图类。它充分利用了邻接表和邻接矩阵的优点，可以根据实际需求在两者之间进行动态切换。

优势

• 动态选择算法：根据节点数量和添加边的次数动态选择适当的表示方式，兼顾了空间和时间效率。

• 节省内存：在节点数量较少时，自动选择邻接矩阵表示，节省内存空间。当节点数量增加时，切换到邻接表表示，避免了内存浪费。

• 高效操作：根据当前的表示方式，在添加边和查找相邻节点等操作上保证了高效性。

示例代码

// 创建一个 AdaptiveGraph 对象
        AdaptiveGraph graph = new AdaptiveGraph(10);

        // 添加有向边
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);

        graph.addEdge(1, 2);
        graph.addEdge(1, 4);

        graph.addEdge(2, 5);

        graph.addEdge(4, 5);

        graph.addEdge(5, 4);
        graph.addEdge(5, 6);


        List<Integer> adjacentNodes = graph.getAdjacentNodes(0);

        // 获取所有不相邻的边
        List<Edge> nonAdjacentEdges = graph.getAllNonAdjacentEdges();

        // 打印所有不相邻的边
        System.out.println("所有非相邻边:");
        for (Edge edge : nonAdjacentEdges) {
            System.out.println(edge);
        }

        // 打印图的表示形式
        graph.printGraph();

        // 进行深度优先搜索
        List<List<Integer>> paths = graph.depthFirstSearch(0, 6);
        System.out.println("深度优先搜索路径从 0 到 6:");
        for (List<Integer> path : paths) {
            System.out.println(path);
        }


        for (Edge nonAdjacentEdge : nonAdjacentEdges) {
            List<List<Integer>> paths2 = graph.depthFirstSearch(nonAdjacentEdge.source, nonAdjacentEdge.destination);
            if (!paths2.isEmpty()) {
                System.out.println("深度优先搜索路径从 " + nonAdjacentEdge.source + " 到 " + nonAdjacentEdge.destination + ":");
                for (List<Integer> path : paths2) {
                    System.out.println(path);
                }
            }

        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

结论

AdaptiveGraph 类为表示和操作有向图提供了一种灵活而高效的解决方案，通过动态选择适当的数据结构，既节省了内存，又保证了操作的高效性。在实际应用中，可以根据具体的场景和需求来选择最合适的表示方式，以达到最佳的性能表现。

好的，以下是一个简单的文档示例，包括了类的介绍、构造函数、方法说明以及示例用法：

---

AdaptiveGraph 文档

AdaptiveGraph 是一个用于表示有向图的类，它根据节点数量和添加边的次数动态选择使用邻接矩阵或邻接表表示。这个类可以根据实际需求在两种表示方式之间动态切换，以保证内存和性能的最佳利用。

构造函数

public AdaptiveGraph(int initialCapacity)

• 描述：构造一个 AdaptiveGraph 对象。
• 参数：
  • initialCapacity：图的初始容量，用于初始化邻接矩阵或邻接表的大小。
• 示例：

  AdaptiveGraph graph = new AdaptiveGraph(10);
  1

方法

public void addEdge(int source, int destination)

• 描述：将有向边添加到图中。
• 参数：
  • source：边的起始节点。
  • destination：边的目标节点。
• 示例：

  graph.addEdge(0, 1);
  1

public List getAdjacentNodes(int node)

• 描述：获取指定节点的相邻节点列表。
• 参数：
  • node：节点索引。
• 返回值：相邻节点列表。
• 示例：

  List<Integer> adjacentNodes = graph.getAdjacentNodes(0);
  1

public void printGraph()

• 描述：打印图的表示形式，包括邻接矩阵或邻接表。
• 示例：

  graph.printGraph();
  1

示例用法

// 创建一个 AdaptiveGraph 对象
AdaptiveGraph graph = new AdaptiveGraph(10);

// 添加有向边
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);

// 获取相邻节点列表
List<Integer> adjacentNodes = graph.getAdjacentNodes(0);

// 打印图的表示形式
graph.printGraph();
1
2
3
4
5
6
7
8
9
10
11
12
13
14

---

完整代码

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

/**
 * 图的表示类，根据节点数量和添加边的次数动态选择使用邻接矩阵或邻接表表示。
 */
public class AdaptiveGraph {

    private final int numVertices; // 图中节点的数量
    private boolean useAdjacencyMatrix; // 标记是否使用邻接矩阵
    private int[][] adjacencyMatrix; // 邻接矩阵表示
    private List<List<Integer>> adjacencyList; // 邻接表表示
    private int edgeCount; // 添加边的次数计数器
    private final Set<Integer> vertices; // 保存图中的所有顶点

    /**
     * 构造函数，根据节点数量自动选择使用邻接矩阵或邻接表表示。
     *
     * @param numVertices 图中节点的数量
     */
    public AdaptiveGraph(int numVertices) {
        this.numVertices = numVertices;
        this.useAdjacencyMatrix = numVertices <= 10; // 默认使用邻接矩阵表示
        this.edgeCount = 0;
        this.vertices = new HashSet<>();

        if (useAdjacencyMatrix) {
            adjacencyMatrix = new int[numVertices][numVertices]; // 初始化邻接矩阵
        } else {
            adjacencyList = new ArrayList<>(numVertices); // 初始化邻接表
            for (int i = 0; i < numVertices; i++) {
                adjacencyList.add(new ArrayList<>());
            }
        }
    }

    /**
     * 添加有向边到图中。
     *
     * @param source      边的起始节点
     * @param destination 边的目标节点
     */
    public void addEdge(int source, int destination) {
        vertices.add(source);
        vertices.add(destination);

        if (edgeCount > 100 && useAdjacencyMatrix) {
            switchToAdjacencyList(); // 如果添加边的次数超过100次，且当前使用邻接矩阵，则切换到邻接表表示
        }

        if (useAdjacencyMatrix) {
            adjacencyMatrix[source][destination] = 1; // 在邻接矩阵中标记有向边
        } else {
            adjacencyList.get(source).add(destination); // 在邻接表中添加有向边
        }

        edgeCount++;
    }

    /**
     * 切换到邻接表表示。
     */
    private void switchToAdjacencyList() {
        useAdjacencyMatrix = false;
        adjacencyList = new ArrayList<>(numVertices);

        for (int i = 0; i < numVertices; i++) {
            adjacencyList.add(new ArrayList<>());
            for (int j = 0; j < numVertices; j++) {
                if (adjacencyMatrix[i][j] == 1) {
                    adjacencyList.get(i).add(j); // 将原始邻接矩阵中的边添加到邻接表中
                }
            }
        }

        adjacencyMatrix = null; // 释放邻接矩阵的内存
    }

    /**
     * 获取指定节点的相邻节点列表。
     *
     * @param node 节点索引
     * @return 相邻节点列表
     */
    public List<Integer> getAdjacentNodes(int node) {
        if (useAdjacencyMatrix) {
            List<Integer> adjacentNodes = new ArrayList<>();
            for (int i = 0; i < numVertices; i++) {
                if (adjacencyMatrix[node][i] == 1) {
                    adjacentNodes.add(i); // 在邻接矩阵中查找相邻节点
                }
            }
            return adjacentNodes;
        } else {
            return adjacencyList.get(node); // 返回邻接表中的相邻节点列表
        }
    }

    /**
     * 打印图的表示形式。
     */
    public void printGraph() {
        if (useAdjacencyMatrix) {
            System.out.println("Adjacency Matrix:");
            for (int[] row : adjacencyMatrix) {
                for (int value : row) {
                    System.out.print(value + " ");
                }
                System.out.println();
            }
        } else {
            System.out.println("Adjacency List:");
            for (int i = 0; i < adjacencyList.size(); i++) {
                System.out.print(i + " -> ");
                for (int neighbor : adjacencyList.get(i)) {
                    System.out.print(neighbor + " ");
                }
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        // 创建一个 AdaptiveGraph 对象
        AdaptiveGraph graph = new AdaptiveGraph(10);

        // 添加有向边
        graph.addEdge(0, 1);
        graph.addEdge(0, 3);

        graph.addEdge(1, 2);
        graph.addEdge(1, 4);

        graph.addEdge(2, 5);

        graph.addEdge(4, 5);

        graph.addEdge(5, 4);
        graph.addEdge(5, 6);


        List<Integer> adjacentNodes = graph.getAdjacentNodes(0);

        // 获取所有不相邻的边
        List<Edge> nonAdjacentEdges = graph.getAllNonAdjacentEdges();

        // 打印所有不相邻的边
        System.out.println("所有非相邻边:");
        for (Edge edge : nonAdjacentEdges) {
            System.out.println(edge);
        }

        // 打印图的表示形式
        graph.printGraph();

        // 进行深度优先搜索
        List<List<Integer>> paths = graph.depthFirstSearch(0, 6);
        System.out.println("深度优先搜索路径从 0 到 6:");
        for (List<Integer> path : paths) {
            System.out.println(path);
        }


        for (Edge nonAdjacentEdge : nonAdjacentEdges) {
            List<List<Integer>> paths2 = graph.depthFirstSearch(nonAdjacentEdge.source, nonAdjacentEdge.destination);
            if (!paths2.isEmpty()) {
                System.out.println("深度优先搜索路径从 " + nonAdjacentEdge.source + " 到 " + nonAdjacentEdge.destination + ":");
                for (List<Integer> path : paths2) {
                    System.out.println(path);
                }
            }
        }

    }

    /**
     * 获取所有不相邻的边。
     *
     * @return 不相邻的边列表
     */
    public List<Edge> getAllNonAdjacentEdges() {
        List<Edge> nonAdjacentEdges = new ArrayList<>();

        for (int i = 0; i < vertices.size() - 1; i++) {
            for (int j = i + 1; j < vertices.size(); j++) {
                // 检查源节点和目标节点是否存在于图中，并且它们不相邻
                if (areVerticesInGraph(i, j) && !areVerticesAdjacent(i, j)) {
                    nonAdjacentEdges.add(new Edge(i, j));
                }
            }
        }

        return nonAdjacentEdges;
    }

    private boolean areVerticesInGraph(int vertex1, int vertex2) {
        return vertex1 >= 0 && vertex1 < vertices.size() && vertex2 >= 0 && vertex2 < vertices.size();
    }

    private boolean areVerticesAdjacent(int vertex1, int vertex2) {
        if (useAdjacencyMatrix) {
            return adjacencyMatrix[vertex1][vertex2] == 1;
        } else {
            return adjacencyList.get(vertex1).contains(vertex2) || adjacencyList.get(vertex2).contains(vertex1);
        }
    }

    // 深度优先搜索
    public List<List<Integer>> depthFirstSearch(int start, int end) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> allPath = new ArrayList<>();
        // 哈希表，用于记录已被访问过的顶点
        Set<Integer> visited = new HashSet<>();
        dfs(start, end, visited, path, allPath);
        return allPath;
    }

    private void dfs(int start, int end, Set<Integer> visited, List<Integer> path, List<List<Integer>> allPath) {
        visited.add(start); // 将当前节点标记为已访问
        path.add(start); // 将当前节点添加到路径中

        // 如果当前节点是终点，则将路径添加到结果列表中
        if (start == end) {
            // 注意：这里需要创建一个新的 ArrayList 对象，否则后续递归调用中的 path 变量会被修改
            allPath.add(new ArrayList<>(path));
        } else {
            //获取当前节点的相邻节点
            List<Integer> adjacentNodes = getAdjacentNodes(start);
            for (Integer adjacentNode : adjacentNodes) {
                // 如果相邻节点没有被访问过，则递归调用 dfs
                if (!visited.contains(adjacentNode)) {
                    dfs(adjacentNode, end, visited, path, allPath);
                }
            }
        }
        // 在回溯的过程中，恢复当前节点的状态，以便正确回退到上一层
        // 如果不在回溯的过程中将节点的访问状态恢复，那么该节点将在后续的搜索中被视为已访问，导致无法再次访问该节点的邻居节点。
        visited.remove(start);
        path.remove(path.size() - 1);

    }

    /**
     * 边类，用于表示图中的边。
     */
    public static class Edge {
        int source;
        int destination;

        public Edge(int source, int destination) {
            this.source = source;
            this.destination = destination;
        }

        @Override
        public String toString() {
            return source + " - " + destination;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263