无向图中邻接矩阵转关联矩阵的实现问题排查

问题背景 #

我正在尝试将无向图的邻接矩阵转换为关联矩阵，图的边列表为：(1, 2), (1,5), (1,6), (2,3), (2,5), (3,4), (3,5), (4,5), (5,6)。

正确的邻接矩阵 #

0 1 0 0 1 1
1 0 1 0 1 0
0 1 0 1 1 0
0 0 1 0 1 0
1 1 1 1 0 1
1 0 0 0 1 0

期望的关联矩阵 #

0 1 0 0 1 1 0 0 0
1 0 1 0 1 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 1 0 1 0 0 0 0
1 1 1 1 0 1 0 0 0
1 0 0 0 1 0 0 0 0

程序实际输出的关联矩阵 #

1 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0
0 0 0 1 0 1 0 0 0
1 0 1 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0

源代码 #

图构造函数 #

Graph(int vertices, int edges)
{
    this->vertices = vertices;
    this->edges = edges;
    edge = std::vector<Graph::Edge*>(edges);
    for (int i = 0; i < edges; i++)
    {
        edge[i] = new Edge(this);
    }
}

图初始化代码 #

Graph* g = new Graph(numberOfVertices, numberOfEdges);
g->edge[0]->src = 1;
g->edge[0]->dest = 2;

g->edge[1]->src = 1;
g->edge[1]->dest = 5;

g->edge[2]->src = 1;
g->edge[2]->dest = 6;

g->edge[3]->src = 2;
g->edge[3]->dest = 3;

g->edge[4]->src = 2;
g->edge[4]->dest = 5;

g->edge[5]->src = 3;
g->edge[5]->dest = 4;

g->edge[6]->src = 3;
g->edge[6]->dest = 5;

g->edge[7]->src = 4;
g->edge[7]->dest = 5;

g->edge[8]->src = 5;
g->edge[8]->dest = 6;

邻接矩阵生成代码 #

for (i = 0; i < numberOfEdges; i++)
{
        adjacency_matrix[g->edge[i]->src][g->edge[i]->dest] = 1;
        adjacency_matrix[g->edge[i]->dest][g->edge[i]->src] = 1;

}

std::cout << "Adjacency matrix : " << std::endl;
for (i = 1; i <= numberOfVertices; i++)
{
    for (j = 1; j <= numberOfVertices; j++)
    {
        std::cout<<adjacency_matrix[i][j]<<" ";
    }
    std::cout << std::endl;
}

关联矩阵生成与输出代码 #

// Incidence Matrix

int counter = 0;
for( int i = 1; i <= numberOfEdges; i++){
    for(int j = i + 1; j < numberOfVertices; j++ ){
        if(adjacency_matrix[i][j] == 1){
            incidence_matrix[i][counter] = 1;
            incidence_matrix[j][counter] = 1;
            ++counter;
        }

    }
}
for( int i = 1; i <= numberOfVertices; i++){
    for(int j = 1; j <= numberOfEdges; j++){
        std::cout<<incidence_matrix[i][j]<<" ";
    }
    std::cout<<std::endl;
}

错误排查与修复 #

关联矩阵生成的代码存在多处逻辑错误，导致输出结果不符合预期：

1. 外层循环遍历对象错误
   原代码外层循环for( int i = 1; i <= numberOfEdges; i++)中，i遍历的是边数而非顶点数。邻接矩阵的行对应顶点，因此外层循环应该遍历所有顶点，改为：

   for( int i = 1; i <= numberOfVertices; i++)
   

2. 内层循环边界错误
   原代码内层循环for(int j = i + 1; j < numberOfVertices; j++ )中，j < numberOfVertices会漏掉编号等于顶点总数的顶点（比如本题中的顶点6），导致无法处理涉及该顶点的边。应修改为：

   for(int j = i + 1; j <= numberOfVertices; j++ )
   

3. 关联矩阵输出的索引错误
   关联矩阵的列是从0开始计数（counter从0开始累加，共9列对应9条边），但原输出循环for(int j = 1; j <= numberOfEdges; j++)从j=1开始遍历到j=9，会跳过第0列，同时访问超出初始化范围的索引。正确的输出循环应该遍历0到8的列索引：

   for(int j = 0; j < numberOfEdges; j++)
   

4. 可选：关联矩阵初始化
   确保incidence_matrix在使用前已初始化为全0，避免出现垃圾值影响输出结果。

修复后的关联矩阵代码 #

// Incidence Matrix
// 先初始化关联矩阵为全0
for (int i = 1; i <= numberOfVertices; i++) {
    for (int j = 0; j < numberOfEdges; j++) {
        incidence_matrix[i][j] = 0;
    }
}

int counter = 0;
for( int i = 1; i <= numberOfVertices; i++){
    for(int j = i + 1; j <= numberOfVertices; j++ ){
        if(adjacency_matrix[i][j] == 1){
            incidence_matrix[i][counter] = 1;
            incidence_matrix[j][counter] = 1;
            ++counter;
        }
    }
}

// 输出关联矩阵
for( int i = 1; i <= numberOfVertices; i++){
    for(int j = 0; j < numberOfEdges; j++){
        std::cout<<incidence_matrix[i][j]<<" ";
    }
    std::cout<<std::endl;
}

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