无向图中关联矩阵转邻接矩阵的算法如何正确实现

基础定义 #

• 关联矩阵维度为N × M：N为顶点总数，M为边总数
• 关联矩阵元素inc[i][k] = 1代表第i个顶点属于第k条边
• 无向图的普通边对应列恰好有2个值为1的元素，自环边对应列只有1个值为1的元素
• 邻接矩阵维度为N × N，元素adj[i][j]代表顶点i与顶点j之间的边数

转换算法步骤 #

1. 初始化N行N列的邻接矩阵，所有元素初始值设为0
2. 遍历关联矩阵的每一列（每一列对应一条边）
3. 收集当前列中所有值为1的顶点索引：
   • 若收集到2个索引u、v：将adj[u][v]和adj[v][u]各加1（无向图邻接矩阵对称）
   • 若收集到1个索引u：将adj[u][u]加1（自环场景处理）
4. 遍历完成后得到最终邻接矩阵

修复后的完整代码 #

const readline = require('readline')
        
const rl = readline.createInterface({input: process.stdin, output: process.stdout})
let incMatrix = []

rl.question('Matrix N and M: ', (userInput) => {
    const input = userInput.split(' ').map(Number)
    const vertexCount = input[0]
    const edgeCount = input[1]
    inputMatrix(vertexCount, edgeCount)
})

const inputMatrix = (vertexLeft, edgeCount) => { 
    if(vertexLeft === 0){
        convertToAdj(edgeCount)
        rl.close()
        return
    }
    rl.question(`Row: ${vertexLeft}, enter numbers separated by spaces: `, (userInput) => {
        const row = userInput.split(' ').map(Number)
        row.length = edgeCount
        incMatrix.push(row)
        inputMatrix(vertexLeft - 1, edgeCount)
    })
}

const convertToAdj = (edgeCount) => {
    const vertexCount = incMatrix.length
    // 初始化邻接矩阵
    const adjMatrix = Array.from({length: vertexCount}, () => Array(vertexCount).fill(0))
    // 遍历每一条边（关联矩阵的列）
    for (let edgeIdx = 0; edgeIdx < edgeCount; edgeIdx++) {
        const connectedVertex = []
        for (let vertexIdx = 0; vertexIdx < vertexCount; vertexIdx++) {
            if (incMatrix[vertexIdx][edgeIdx] === 1) {
                connectedVertex.push(vertexIdx)
            }
        }
        // 处理普通边
        if (connectedVertex.length === 2) {
            const u = connectedVertex[0]
            const v = connectedVertex[1]
            adjMatrix[u][v] += 1
            adjMatrix[v][u] += 1
        }
        // 处理自环
        if (connectedVertex.length === 1) {
            const u = connectedVertex[0]
            adjMatrix[u][u] += 1
        }
    }
    // 输出结果
    console.log('转换后的邻接矩阵：')
    adjMatrix.forEach(row => console.log(row.join(' ')))
}

输入输出示例 #

输入：

Matrix N and M: 3 2
Row: 3, enter numbers separated by spaces: 1 0
Row: 2, enter numbers separated by spaces: 1 1
Row: 1, enter numbers separated by spaces: 0 1

输出：

转换后的邻接矩阵：
0 1 0
1 0 1
0 1 0

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