package datastructure.graph; import java.util.Arrays; import matrix.IntMatrix; /** * Weighted graphs are called nets. * * @author Fan Min [email protected]. */ public class Net { /** * The maximal distance. Do not use Integer.MAX_VALUE. */ public static final int MAX_DISTANCE = 10000; /** * The number of nodes. */ int numNodes; /** * The weight matrix. We use int to represent weight for simplicity. */ IntMatrix weightMatrix; /** ********************* * The first constructor. * * @param paraNumNodes * The number of nodes in the graph. ********************* */ public Net(int paraNumNodes) { numNodes = paraNumNodes; weightMatrix = new IntMatrix(numNodes, numNodes); for (int i = 0; i < numNodes; i++) { // For better readability, you may need to write fill() in class // IntMatrix. Arrays.fill(weightMatrix.getData()[i], MAX_DISTANCE); } // Of for i }// Of the first constructor /** ********************* * The se

### 加权图（`Net` 类）的实现细节和构造函数说明 在 Java 中，加权图可以通过邻接表来表示。对于 `Net` 类的实现，通常会涉及以下几个核心部分： #### 1. 数据结构设计 `Net` 类可以基于邻接表实现，其中每个顶点存储其相邻节点以及对应的权重。以下是可能的数据结构定义[^3]: ```java import java.util.ArrayList; import java.util.List; public class Net { private final int V; // 图中的顶点数 private final List<List<Edge>> adj; // 邻接表 public static class Edge { int destination; // 边的目标顶点 double weight; // 边的权重 public Edge(int destination, double weight) { this.destination = destination; this.weight = weight; } } public Net(int V) { // 构造函数 this.V = V; adj = new ArrayList<>(V); for (int i = 0; i < V; i++) { adj.add(new ArrayList<>()); } } public void addEdge(int src, int dest, double weight) { adj.get(src).add(new Edge(dest, weight)); // 添加有向边 } public Iterable<Edge> getAdj(int v) { return adj.get(v); // 返回与顶点v相连的所有边 } } ``` 上述代码展示了如何通过嵌套列表构建加权图的邻接表表示法。每一项是一个包含目标顶点及其对应权重的对象。 --- #### 2. 使用整数矩阵 (`IntMatrix`) 初始化加权图 如果要从一个二维整数矩阵初始化加权图，则可以在构造函数中解析该矩阵并填充到邻接表中。假设输入矩阵的形式如下： - 如果 `matrix[i][j] != 0`，则存在一条从顶点 `i` 到顶点 `j` 的边，权重为 `matrix[i][j]`； - 否则不存在这样的边。 下面是改进后的构造函数实现[^4]: ```java public Net(IntMatrix matrix) { if (matrix == null || matrix.rows() <= 0 || matrix.cols() <= 0) { throw new IllegalArgumentException("Invalid input matrix"); } this.V = matrix.rows(); adj = new ArrayList<>(this.V); for (int i = 0; i < this.V; i++) { adj.add(new ArrayList<>()); // 初始化邻接表 } for (int i = 0; i < this.V; i++) { for (int j = 0; j < this.V; j++) { if (matrix.getValue(i, j) != 0) { // 存在边 adj.get(i).add(new Edge(j, matrix.getValue(i, j))); // 添加带权重的边 } } } } ``` 在此版本中，`IntMatrix` 是一个假定存在的类，用于封装二维数组的操作。它提供了方法如 `rows()` 和 `cols()` 来获取行列数量，并提供了一个 `getValue(row, col)` 方法访问具体位置上的值。 --- #### 3. 关键功能解释 - **邻接表**：相比于邻接矩阵，邻接表更适合稀疏图，因为它只保存实际存在的边。 - **动态扩展能力**：由于使用了 `ArrayList` 结构，因此能够方便地增加新的边或修改现有边的信息。 - **时间复杂度优化**：遍历某一点的所有邻居时只需线性扫描它的邻接链表即可完成操作，效率较高。 --- ### 示例应用 下面展示如何创建一个简单的加权图实例并通过打印验证其内容: ```java public static void main(String[] args) { IntMatrix matrix = new IntMatrix(3, 3); // 假设有一个支持设置值的方法 set() matrix.set(0, 1, 5); // 设置从0->1的一条边，权重为5 matrix.set(1, 2, 7); // 设置从1->2的一条边，权重为7 Net net = new Net(matrix); System.out.println("Edges from vertex 0:"); for (Net.Edge e : net.getAdj(0)) { System.out.printf("To %d with weight %.1f%n", e.destination, e.weight); } } ``` 运行此程序将输出类似于以下的结果: ``` Edges from vertex 0: To 1 with weight 5.0 ``` ---