一個簡單的無向圖由鄰接矩陣給出
一個簡單的無向圖由鄰接矩陣定義。有必要推匯出關聯矩陣
輸入：
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()
如何正確實作從一種型別的矩陣到另一種型別的轉換？
uj5u.com熱心網友回復：
這不會嘗試進行任何輸入決議，但它確實接受鄰接矩陣（作為陣列的陣列，這是 JS 中的典型做法）并以相同的方式回傳關聯矩陣。它不進行錯誤檢查以確保您提供的實際上是一個鄰接矩陣（其中每個值都是0or 1，主對角線都是0s 并且它關于該主??對角線對稱。）這并不難添加，
它使用一個range輔助函式，該函式回傳一個介于低值（包含）和高值（不包含）之間的整數陣列。例如，range (3, 12)回傳[3, 4, 5, 6, 7, 8, 9, 10, 11]。它使用一個transpose輔助函式在其主對角線上翻轉矩陣，為列切換行，反之亦然。
main 函式在矩陣的下對角線上執行雙回圈。對于每個具有 a 的坐標對1，我們創建一行0s 除了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從結果上的相關答案1開始運行，我們將得到與我們開始時相同的矩陣。但是如果我們從一個關聯矩陣開始，運行inci2adj它，adj2inci根據結果??，我們不一定會得到原始矩陣。
1代碼如下：
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
)
)
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/364327.html
標籤：javascript 节点.js 算法 图形
上一篇：查找整數排序串列更改的索引
下一篇：將關聯矩陣轉換為鄰接矩陣