如何基于全图邻接矩阵提取奇度顶点对应的子图邻接矩阵

核心逻辑说明 #

仅通过两次遍历奇度顶点集合即可完成子图邻接矩阵构建，全程仅使用MyCustomVector允许的基础操作，不需要额外数据结构。

具体实现代码 #

// 前提：INF为已定义的无直连边常量，graph的索引与节点编号一一对应
int oddCnt = oddVertices.size();
MyCustomVector<MyCustomVector<int>> oddSubgraph;

// 遍历奇度顶点作为子图的行
for (int i = 0; i < oddCnt; i++) {
    MyCustomVector<int> curRow;
    int oldU = oddVertices[i];
    // 遍历奇度顶点作为子图的列
    for (int j = 0; j < oddCnt; j++) {
        int oldV = oddVertices[j];
        // 直接取原图中两个奇度顶点的对应边权
        curRow.push_back(graph[oldU][oldV]);
    }
    oddSubgraph.push_back(curRow);
}

结果说明 #

最终得到的oddSubgraph就是符合要求的子图邻接矩阵：

• 矩阵大小为oddCnt * oddCnt，其中oddCnt = oddVertices.size()
• oddSubgraph[i][j]对应原奇度顶点oddVertices[i]和oddVertices[j]在原图中的边权，无直接边时为INF，可直接作为Floyd-Warshall算法的输入使用

内容的提问来源于stack exchange，提问作者zzzzz