转换图。从一种矩阵到另一种矩阵（之前的答案不正确）

Question

一个简单的无向图由邻接矩阵给出

一个简单的无向图由邻接矩阵定义。需要推导关联矩阵

输入：

3

0 1 0

1 0 1

0 1 0

输出：

1 0

1 1

0 1

输入：

5

0 0 1 1 0

0 0 1 0 0

1 1 0 0 1

1 0 0 0 1

0 0 1 1 0

输出：

1 0 1 0 0

0 1 0 0 0

1 1 0 1 0

0 0 1 0 1

0 0 0 1 1

    const convert = () => {
    let arr = [
        [0,0,1,1,0],
        [0,0,1,0,0],
        [1,1,0,0,1],
        [1,0,0,0,1],
        [0,0,1,1,0]
    ]
    let matrix = []
    let subArray = []
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            subArray.push(0)
        }
        matrix.push(subArray)
        subArray = []
    }
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if(arr[j][i] == 1){
                subArray.push(j)
                
            }
        }
        console.log(subArray)
        subArray = []
    }
    console.log(matrix)
}
convert()

如何正确实现从一种矩阵到另一种矩阵的转换？

Answer 1

这不会尝试进行任何输入解析，但它会以相同的方式接受邻接矩阵（作为数组的数组，这在 JS 中很典型）和 returns 关联矩阵。它不进行错误检查以确保您提供的实际上是一个邻接矩阵（其中每个值都是 0 或 1，主对角线都是 0 并且它关于对称那个主对角线。）这不难添加，

它使用了一个 range 辅助函数，它 returns 一个介于低值（含）和高值（不含）之间的整数数组。例如，range (3, 12) returns [3, 4, 5, 6, 7, 8, 9, 10, 11]。它使用 transpose 辅助函数在其主对角线上翻转矩阵，将行换成列，反之亦然。

main函数在矩阵的下对角线上做了一个双循环。对于每个具有 1 的坐标对，我们在该对的每个索引处创建一行 0，但 1 除外，代表图中的一条边。完成后，我们转置矩阵，使我们的边变成列。

看起来像这样：

const range = (lo, hi) => 
  Array.from ({length: hi - lo}, (_, i) => i + lo)

const transpose = (xs) => 
  xs [0] .map ((_, i) => xs .map (r => r[i]))

const adj2inci = (m) => 
  transpose (range (0, m .length) 
    .flatMap (j => range (0, j + 1) .flatMap (
      i => m[j][i] == 1 ? [Object .assign (Array (m .length) .fill (0), {[i]: 1}, {[j]: 1})] : [])
    )
  )

const incidents = [[0, 0, 1, 1, 0], [0, 0, 1, 0, 0], [1, 1, 0, 0, 1], [1, 0, 0, 0, 1], [0, 0, 1, 1, 0]]

console .log (adj2inci (incidents))

.as-console-wrapper {max-height: 100% !important; top: 0}

请注意，虽然图有明确的邻接矩阵，但关联矩阵有多种表示形式，因为列的重新排列仍将表示同一个图。

这意味着如果我们从邻接矩阵开始，然后运行 adj2inci 反对它，那么运行 inci2adj 来自 ¹ 结果，我们将得到与我们开始时相同的矩阵。但是如果我们从一个关联矩阵开始，运行 inci2adj 反对它，并且 adj2inci 结果，我们不一定会得到原始矩阵。

¹代码如下所示：

const inci2adj = (m) => 
  range (0, m .length) .map (
    j => range (0, m .length) .map (i => m [0] .some (
      (_, e) => i !== j &&  m [i] [e] == 1 && m [j] [e] == 1) ? 1 : 0
    )
  )

转换图。从一种矩阵到另一种矩阵（之前的答案不正确）

converting graph. from one type of matrix to another (previous answer is incorrect)

javascript

algorithm

graph

node.js