### 将0-1关系矩阵转换为带权重的邻接表 为了将一个0-1的关系矩阵（即二进制邻接矩阵）转换为带权重的邻接表，可以按照以下逻辑操作： 1. 遍历给定的二维数组表示的邻接矩阵。 2. 对于每一个非零元素 \( A[i][j] \)，将其视为一条边，并赋予一定的权重。如果原始矩阵已经是加权矩阵，则可以直接提取权重；如果是二进制矩阵，则可以根据特定规则分配权重[^1]。 3. 构建邻接表结构，其中每个节点对应一个列表，存储与其相连的所有其他节点及其对应的权重。 以下是基于Python的一个具体实现示例： ```python def binary_matrix_to_weighted_adjacency_list(matrix, weight_func=None): """ Convert a binary adjacency matrix into a weighted adjacency list. :param matrix: List[List[int]], the input binary adjacency matrix. :param weight_func: Callable[[int, int], float], optional function to assign weights based on node indices. If None, default weight of 1 is assigned. :return: Dict[int, List[Tuple[int, float]]], the resulting weighted adjacency list. """ n = len(matrix) adj_list = {i: [] for i in range(n)} if not callable(weight_func): # 如果未提供权重函数，默认赋值为1 weight_func = lambda u, v: 1 for i in range(n): for j in range(i + 1, n): # 只需遍历上三角部分即可 if matrix[i][j]: weight = weight_func(i, j) # 使用自定义权重函数计算权重 adj_list[i].append((j, weight)) adj_list[j].append((i, weight)) # 图是无向图，所以双向添加 return adj_list # Example usage: binary_matrix = [ [0, 1, 1], [1, 0, 0], [1, 0, 0] ] # 自定义权重函数：简单地设置固定权重 custom_weight_function = lambda u, v: (u + v) / 2 weighted_adj_list = binary_matrix_to_weighted_adjacency_list(binary_matrix, custom_weight_function) for key, value in weighted_adj_list.items(): print(f"{key}: {value}") ``` #### 输出解释 假设我们有一个简单的二进制邻接矩阵 `binary_matrix` 和一个自定义权重函数 `custom_weight_function(u, v)` 来决定每条边的具体权重。运行以上代码会得到如下形式的结果： ``` 0: [(1, 0.5), (2, 1.0)] 1: [(0, 0.5)] 2: [(0, 1.0)] ``` 这表明节点0连接到节点1和2，分别具有权重0.5和1.0；同样适用于其余节点。 --- ### 关键点说明 1. **权重函数的选择** 用户可以通过传递不同的权重函数来自定义每条边的权重。如果没有指定任何函数，则默认所有边都具有单位权重1[^2]。 2. **稀疏性优化** 当处理大规模稀疏矩阵时，建议仅记录非零项以节省内存空间并提高效率。上述算法已经隐含了这一点，因为它只关注那些存在连接的位置。 3. **拉普拉斯正则化因子的应用** 若希望进一步引入更复杂的权重调整机制，比如应用拉普拉斯正则化因子 \( \frac{2}{d_i + d_j} \)[^3] ，可以在 `weight_func` 中嵌入此类逻辑。 ---