\u82e5\u6709 Alogorithm class \u662f\u5426\u5c31\u4e0d\u5fc5 graphEx\uff1f<\/p>\n
\u662f\u7684\uff0c\u5982\u679c\u4f60\u7684\u5c08\u6848\u4e2d\u5df2\u7d93\u6709\u5b98\u65b9\u8981\u6c42\u7684 \u6839\u64da MP2 \u6587\u4ef6\u8aaa\u660e\uff0c \u4f60\u53ef\u4ee5\u628a\u6240\u6709\u300c\u4e0d\u5c6c\u65bc\u5716\u672c\u8eab\u7d50\u69cb\u3001\u4f46\u8981\u64cd\u4f5c\u5716\u7684\u6f14\u7b97\u6cd5\u300d\u90fd\u96c6\u4e2d\u5230 \u82e5\u4f60\u7684 \u7bc4\u4f8b\uff1a<\/p>\n \u8cc7\u6599\u4f86\u6e90<\/p>\n \u6c92\u6709 add \u5982\u4f55\u5efa\u7acb AdjacencyMatrixGraph <\/p>\n \u6839\u64da MP2 \u4efb\u52d9\u6587\u4ef6\u7684\u8aaa\u660e\uff0cAdjacencyMatrixGraph<\/strong> \u88ab\u8a2d\u8a08\u6210\u300c\u4e0d\u53ef\u8b8a\u5716\uff08immutable graph\uff09\u300d\u2014\u2014\u4e5f\u5c31\u662f\u8aaa\u5b83\u6c92\u6709 \u5728\u6c92\u6709 \u5efa\u7acb\u77e9\u9663\u7d50\u69cb\u3002<\/p>\n \u7bc4\u4f8b\uff1a<\/p>\n \u82e5\u8981\u7522\u751f\u8a98\u5c0e\u5b50\u5716\uff08induced subgraph\uff09\uff0c\u53ef\u7528\u975c\u614b\u65b9\u6cd5\uff1a<\/p>\n \u5b83\u6703\u5f9e\u539f\u77e9\u9663\u4e2d\u62bd\u53d6\u5c0d\u61c9\u9802\u9ede\u8207\u908a\u751f\u6210\u65b0\u5716\u3002<\/p>\n<\/li>\n<\/ul>\n \u4e0d\u8981\u5617\u8a66\u8b93\u77e9\u9663\u7248\u5716\u652f\u63f4 \u82e5\u6c92\u6709 Algorithms<\/code> \u985e\u5225\uff08\u4f8b\u5982 Algorithms.partitionGraph(Graph g, int numberOfPartitions)<\/code>\uff09\uff0c\u90a3\u9ebc\u5c31\u4e0d\u4e00\u5b9a\u9700\u8981\u984d\u5916\u5efa\u7acb GraphEx<\/code><\/strong> \u985e\u5225\u3002<\/p>\nAlgorithms<\/code> \u985e\u662f\u5c08\u9580\u8a2d\u8a08\u4f86\u653e\u5404\u7a2e\u8207\u5716\u904b\u7b97\u6709\u95dc\u7684\u975c\u614b\u6f14\u7b97\u6cd5<\/strong>\u7684\u5730\u65b9\uff0c\u4f8b\u5982\uff1a<\/p>\n\n
partitionGraph<\/code> \u7528\u4f86\u6839\u64da\u8ddd\u96e2\u8207\u9130\u8fd1\u689d\u4ef6\u5206\u5272\u5716\uff1b<\/li>\n
\n\u2705 \u82e5\u5df2\u6709
Algorithms<\/code> \u985e\uff0c\u5efa\u8b70\u7684\u8a2d\u8a08\u7b56\u7565<\/h3>\nAlgorithms<\/code> \u985e\u4e2d\uff1a<\/p>\npublic final class Algorithms {\n\n private Algorithms() { }\n\n public static <V extends Vertex, E extends Edge<V>>\n List<V> minimumCostPath(Graph<V,E> g, V s, V t, PathCostType type) { ... }\n\n public static <V extends Vertex, E extends Edge<V>>\n double pathCost(Graph<V,E> g, List<V> path, PathCostType type) { ... }\n\n public static <V extends Vertex, E extends Edge<V>>\n double diameter(Graph<V,E> g, PathCostType type) { ... }\n\n public static <V extends Vertex, E extends Edge<V>>\n V center(Graph<V,E> g, PathCostType type) { ... }\n\n public static <V extends Vertex, E extends Edge<V>>\n List<Graph<V,E>> partitionGraph(Graph<V,E> g, int k) { ... }\n}<\/code><\/pre>\n
\n\ud83d\udcd8 \u4f55\u6642\u4ecd\u5efa\u8b70\u4fdd\u7559
GraphEx<\/code><\/h3>\nAlgorithms<\/code> \u985e\u5df2\u7d93\u5f88\u5927\u3001\u6216\u88ab\u898f\u7bc4\u70ba\u53ea\u5be6\u4f5c Task 5\uff08partitionGraph<\/code>\uff09\uff0c
\n\u800c\u4f60\u53c8\u60f3\u5c07 Task 3\u30014 \u7684\u8def\u5f91\u8207\u4e2d\u5fc3\u8a08\u7b97\u62bd\u96e2\u5171\u7528\u908f\u8f2f\uff0c
\n\u90a3\u9ebc\u53ef\u4ee5\u8b93 GraphEx<\/code> \u4f5c\u70ba\u5167\u90e8\u5de5\u5177\u5c64<\/strong>\uff1a<\/p>\n\n
GraphEx<\/code> \u5c08\u6ce8\u65bc\u300c\u6838\u5fc3\u6f14\u7b97\u6cd5\u300d\uff08Dijkstra\u3001BFS\u3001components\uff09\u3002<\/li>\nAlgorithms<\/code> \u53ea\u662f\u4e00\u500b\u516c\u958b API\uff0c\u5167\u90e8\u547c\u53eb GraphEx<\/code>\u3002<\/li>\n<\/ul>\npublic static <V extends Vertex, E extends Edge<V>>\nList<Graph<V,E>> partitionGraph(Graph<V,E> g, int k) {\n return GraphEx.inducedSubgraphs(g, GraphEx.computePartitions(g, k));\n}<\/code><\/pre>\n
\n\ud83e\udded \u7e3d\u7d50<\/h3>\n
\n
Algorithms<\/code> \u4e00\u500b\u985e\u5225\u4e5f\u53ef\u4ee5\u5b8c\u6210\u6240\u6709\u5de5\u4f5c<\/strong>\uff0c\u4e0d\u5fc5\u5f37\u5236\u518d\u5efa GraphEx<\/code>\u3002<\/li>\nminimumCostPath<\/code>\u3001getDiameter<\/code> \u6703\u88ab\u591a\u500b\u985e\u5171\u7528\uff09\uff0c
\n\u5c31\u53ef\u4fdd\u7559 GraphEx<\/code> \u4f5c\u70ba\u5167\u90e8\u8f14\u52a9\u985e\u3002<\/li>\n\u4f60\u8aaa\uff1a<\/h5>\n
ChatGPT \u8aaa\uff1a<\/h6>\n
addVertex()<\/code> \u6216 addEdge()<\/code> \u65b9\u6cd5<\/strong>\uff0c\u800c\u662f\u5fc5\u9808\u5728\u5efa\u69cb\u6642\uff08constructor\uff09\u4e00\u6b21\u6027\u5efa\u7acb\u597d\u6574\u5f35\u5716<\/strong>MP2-Operations and Applications\u2026\u3002<\/p>\n
\n\u2705 \u6b63\u78ba\u5efa\u7acb\u65b9\u5f0f<\/h3>\n
add<\/code> \u65b9\u6cd5\u7684\u60c5\u6cc1\u4e0b\uff0c\u6700\u5408\u7406\u7684\u505a\u6cd5\u662f\u8b93 AdjacencyMatrixGraph<\/code> \u5177\u5099\u4e00\u500b\u5efa\u69cb\u5b50\u6216\u975c\u614b\u5de5\u5ee0\u65b9\u6cd5<\/strong>\uff0c\u76f4\u63a5\u5f9e\uff1a<\/p>\n\n
public final class AdjacencyMatrixGraph<V extends Vertex, E extends Edge<V>>\n implements Graph<V, E> {\n\n private final List<V> vertices;\n private final double[][] matrix;\n\n \/** \u5efa\u69cb\u4e00\u500b\u4e0d\u53ef\u8b8a\u7684\u5716 *\/\n public AdjacencyMatrixGraph(Set<V> vertices, Set<E> edges) {\n this.vertices = List.copyOf(vertices);\n int n = this.vertices.size();\n this.matrix = new double[n][n];\n\n \/\/ \u521d\u59cb\u5316\u70ba\u7121\u9650\u8ddd\u96e2\n for (int i = 0; i < n; i++) {\n Arrays.fill(matrix[i], Double.POSITIVE_INFINITY);\n matrix[i][i] = 0;\n }\n\n \/\/ \u586b\u5165\u908a\u6b0a\u91cd\n for (E edge : edges) {\n int i = this.vertices.indexOf(edge.v1());\n int j = this.vertices.indexOf(edge.v2());\n double w = edge.length();\n matrix[i][j] = w;\n matrix[j][i] = w; \/\/ \u7121\u5411\u5716\n }\n }\n\n \/** \u5f9e\u53e6\u4e00\u500b Graph \u8907\u88fd\u70ba\u77e9\u9663\u578b *\/\n public static <V extends Vertex, E extends Edge<V>>\n AdjacencyMatrixGraph<V, E> fromGraph(Graph<V, E> g) {\n return new AdjacencyMatrixGraph<>(g.getVertices(), g.getEdges());\n }\n}<\/code><\/pre>\n
\n\ud83e\udde9 \u5be6\u4f5c\u8981\u9ede<\/h3>\n
\n
AdjacencyMatrixGraph<\/code> \u53ea\u9700\u63d0\u4f9b\u89c0\u5bdf\u65b9\u6cd5\uff08getEdge(v1, v2)<\/code>, hasVertex(v)<\/code>, edgeLength(v1, v2)<\/code> \u7b49\uff09\u3002<\/p>\n<\/li>\npublic AdjacencyMatrixGraph
\n\ud83d\udeab \u4e0d\u5efa\u8b70\u7684\u4f5c\u6cd5<\/h3>\n
add<\/code> \u6216 remove<\/code>\uff1a<\/p>\n\n
\n\ud83d\udd1a \u7e3d\u7d50<\/h3>\n
\n
addVertex<\/code>\/addEdge<\/code>\uff0c\u8acb\u5728\u5efa\u69cb\u5b50\u4e2d\u4e00\u6b21\u6027\u63a5\u6536 Set<V><\/code> \u548c Set<E><\/code> \u6216\u7528 fromGraph()<\/code> \u8f49\u63db\u65b9\u5f0f\u5efa\u7acb\u3002
\n\u9019\u6a23\u7b26\u5408 MP2 \u7684\u300cAdjacencyMatrixGraph \u70ba\u4e0d\u53ef\u8b8a\u5716\u300d\u898f\u7bc4\uff0c\u4e14\u80fd\u6b63\u78ba\u53c3\u8207 Task 3\u20135 \u7684\u6f14\u7b97\u6cd5\u904b\u7b97\u3002<\/p>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"