如何在JavaScript中将邻接矩阵转换为邻接表？
如何在JavaScript中将邻接矩阵转换为邻接表？
提问于 2019-03-12 06:07:10
我正在尝试实现一种将邻接矩阵转换为邻接列表的方法。我的实现不能正确地从矩阵转换为列表。这是我第一次尝试，
//Adjacency Matrix to Adjc list
function convertToAdjList(adjMatrix) {
var adjList = new Array(adjMatrix.length - 1);
for (var i = 0; i < adjMatrix.length; i++) {
if (adjMatrix[i] == 1) {
//I think i have to do something here.
}
for (var j = 0; j < adjMatrix.length - 1; j++) {
if (adjMatrix[i][j] == 1) {
adjList[i] = i;//not sure if this is quite right.
}
}
}
return adjList;
}
var testMatrix = [
[0, 1, 1, 1],
[1, 0, 0, 0],
[1, 0, 0, 0],
[1, 0, 0, 0]
];
console.log(convertToAdjList(testMatrix)); //[[1,2,3],[0],[0],[0];
输出只是我期望代码输出的4个数组中的一个，在索引0处加上一个零。有没有人有办法解决这个问题？
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-03-12 06:19:21
您可以将索引或-1映射为不需要的值，然后过滤此值。
function convertToAdjList(adjMatrix) {
return adjMatrix.map(a => a.map((v, i) => v ? i : -1).filter(v => v !== -1))
}
var testMatrix = [ [0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]];
console.log(convertToAdjList(testMatrix)); // [[1, 2, 3], [0], [0], [0]].as-console-wrapper { max-height: 100% !important; top: 0; }
Stack Overflow用户
发布于 2019-11-02 12:15:49
另一种不使用'map‘的方法是像下面这样编写，这可能不是很好，但仍然可以完成工作。
function convertToAdjList(adjMatrix) {
var adjList = [];
for (var i = 0; i < adjMatrix.length; i++) {
var array=[];
for (var j = 0; j < adjMatrix.length; j++) {
if (adjMatrix[i][j] == 1) {
array.push(j);
}
}
adjList[i]=array;
}
return adjList;
}
值得一提的是，时间复杂度类似于O(V^2)。然而，我猜如果我们想把邻接表转换成邻接矩阵，时间复杂度将是O(V*E)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55111120
复制相关文章
相似问题
腾讯云开发者
