如何正確實作將關聯矩陣轉換為鄰接矩陣演算法？
圖將是無向的
3 - 向量
2 - 邊緣
輸入：3 2
1 0
1 1
0 1
輸出：
0 1 0
1 0 1
0 1 0
不幸的是，我試圖做的演算法不起作用
const readline = require('readline')
const rl = readline.createInterface({input: process.stdin, output: process.stdout})
let arr = []
rl.question('Matrix N and M: ', async (userInput) => {
const input = await userInput.split(' ')
const arrayLength = input[0]
const maxWidth = input[1]
matrix(arrayLength, maxWidth)
})
const matrix = (arrayLength, maxWidth) => {
if(arrayLength === 0){
convert(maxWidth)
}
if(arrayLength > 0){
rl.question(`Row: ${arrayLength}, enter numbers separated by spaces: `, async (userInput) => {
const subArray = await userInput.split(' ')
subArray.length = maxWidth
await arr.push(subArray)
matrix(arrayLength - 1, maxWidth)
})
}
}
const convert = (maxWidth) => {
let matrix = []
let subArray = []
for (let i = 0; i < arr.length; i ) {
for (let j = 0; j < maxWidth; j ) {
}
}
}
uj5u.com熱心網友回復：
這不會嘗試進行任何輸入決議，但它確實接受關聯矩陣（作為陣列的陣列，在 JS 中很典型）并以相同的方式回傳鄰接矩陣。它不進行錯誤檢查以確保您提供的實際上是一個關聯矩陣（其中每列恰好有兩個1s 和0s 其他地方。）這并不難添加，
它使用一個range輔助函式，該函式回傳一個介于低值（包含）和高值（不包含）之間的整數陣列。例如，range (3, 12)回傳[3, 4, 5, 6, 7, 8, 9, 10, 11]。
main 函式對輸入中的行數進行雙回圈，迭代值代表行和列。對于每一個，我們檢查輸入中是否有任何列作為兩個索引都有值1（在排除兩個索引相同的那些之后。）
它看起來像這樣：
const range = (lo, hi) =>
Array.from ({length: hi - lo}, (_, i) => i lo)
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
)
)
const incidents = [
[1, 0],
[1, 1],
[0, 1]
]
console .log (inci2adj (incidents)).as-console-wrapper {max-height: 100% !important; top: 0}請注意，盡管圖有明確的鄰接矩陣，但關聯矩陣有多種表示形式，因為列的重新排列仍將表示相同的圖。
這意味著如果我們從一個鄰接矩陣開始，然后adj2inci從一個相關的答案1開始運行，然后運行inci2adj結果，我們將得到與我們開始時相同的矩陣。但是如果我們從一個關聯矩陣開始，運行inci2adj它，adj2inci根據結果??，我們不一定會得到原始矩陣。
1代碼如下：
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})] : [])
)
)
uj5u.com熱心網友回復：
所以有一些事情（缺乏問題根源）。但是，這是您可以使用的一種方法。在這里，使用地圖來存盤邊和頂點之間的關系。使用它，我們能夠通過它們的分組來構建頂點之間的關系。
為了方便使用，我們首先使用一個promise-based問題函式。這可以使用以下方法完成
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// Convert question function from cb to promise.
const question = (query) =>
new Promise((resolve, _) => {
rl.question(query, (input) => resolve(input));
});
接下來，我們創建一個main函式來封裝我們的邏輯。
async function main() {}
現在，讓我們創建一個為我們提取維數的函式
async function getDimensions() {
// # of Vertices x # of Edges
return (await question("Matrix N and M: ")).split(" ").map(x => x)
}
完成后，我們可以創建兩個輔助函式。第一個，它接收預期頂點的數量。第二個，它需要結果的發生映射和預期頂點的數量（所以我們不必計算它）。
async function createIncidenceMap(N) { }
async function convertToAdjacencyMatrix(incidenceMap, N) { }
為了實作createIncidentMap，我們可以使用以下
// Create an Incidence Map for Quick Look Up
async function createIncidenceMap(N) {
const incidentMatrix = [];
// Read in the relationships between edges (columns) and vertices (rows).
for (let i = 0; i < N; i ) {
const result = (
await question(`Row: ${i}, enter numbers separated by spaces: `)
)
.split(" ")
.map((x) => x);
incidentMatrix.push(result);
}
// Group vertices by edges.
return incidentMatrix.reduce((incidentMap, incidentPair, M) => {
const incidentSubset = incidentPair.reduce(
(subsetMap, connected, N) => (
{
...subsetMap,
[N]: [
...(subsetMap[N]?.length ? subsetMap[N] : []),
...(connected ? [M] : []),
],
}
),
{}
);
// Join previous vertices connected to the same edge.
return Object.keys(incidentSubset).reduce((map, edge, index) => ({
...map,
[edge]: new Set([
...(incidentMap[edge] ?? []),
...incidentSubset[edge]
]).values(),
}), {});
}, {});
};
這將減少作業 convertToAdjacencyMatrix
function convertToAdjacencyMatrix(incidenceMap, M) {
const connectedPairs = Object.values(incidenceMap).map(x => [...x])
// (M x M)
const adjacencyMatrix = new Array(M)
.fill(0).map(_ => new Array(M).fill(0));
connectedPairs.forEach(pair => {
const [n1, n2] = pair
// A vertice always has a relationship with itself.
adjacencyMatrix[n1][n1] = 1
adjacencyMatrix[n2][n2] = 1
// Mark the relationship between the vertices sharing the same edge.
adjacencyMatrix[n1][n2] = 1
adjacencyMatrix[n2][n1] = 1
})
return adjacencyMatrix
};
最后我們結合邏輯main得到
async function main() {
try {
const[N,M] = await getDimensions()
// Create incidentMatrix for faster conversion.
const incidenceMap = await createIncidenceMap(N);
// Convert.
const adjacencyMatrix = convertToAdjacencyMatrix(incidenceMap, N)
console.log(adjacencyMatrix)
rl.close();
} catch (err) {
console.log(`Error found when reading ${err}`);
}
}
main使用您提供的輸入進行呼叫將產生
// [ [ 1, 1, 0 ], [ 1, 1, 1 ], [ 0, 1, 1 ] ]
main()
正如預期的那樣。
一個完整的例子可以在這個演示中找到
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/364328.html
標籤：javascript 节点.js 算法 图形