#javascript #algorithm #graph-algorithm
Вопрос:
Я работаю над литкодом 133. График клонирования:
Дана ссылка на узел в связанном неориентированном графе.
Верните глубокую копию (клон) графика.
Каждый узел в графике содержит значение (
int
) и список (List[Node]
) его соседей.class Node { public int val; public List<Node> neighbors; }
Формат тестового набора:
Для простоты значение каждого узла совпадает с индексом узла (1-индексированный). Например, первый узел с
val == 1
, второй узел сval == 2
и так далее. График представлен в тестовом случае с помощью списка смежности.
Я довольно долго боролся с этим. Мое решение:
/**
* // Definition for a Node.
* function Node(val, neighbors) {
* this.val = val === undefined ? 0 : val;
* this.neighbors = neighbors === undefined ? [] : neighbors;
* };
*/
/**
* @param {Node} node
* @return {Node}
*/
var cloneGraph = function (node) {
if (!node) {
return node;
}
const nodeCopy = new Node(node.val);
let stack = [node];
let nodeMap = {};
nodeMap[node.val] = nodeCopy;
while (stack.length > 0) {
const currentNode = stack.shift();
const currentNodeCopy = nodeMap[currentNode.val];
let nodeNeighbors = currentNode.neighbors;
while (nodeNeighbors.length > 0) {
const currentNeighbor = nodeNeighbors.shift();
let existingNeighborCopy = nodeMap[currentNeighbor.val];
// console.log(existingNeighborCopy);
if (!existingNeighborCopy) {
stack.push(currentNeighbor);
nodeMap[currentNeighbor.val] = new Node(currentNeighbor.val);
}
// console.log('Existing Neighbor');
// Already Visited;
currentNodeCopy.neighbors.push(nodeMap[currentNeighbor.val]);
}
}
console.log(nodeCopy);
console.log(nodeCopy.neighbors[0]);
return nodeMap[node.val];
};
Он выполняет DFS итерационно. Но для базового тестового случая, приведенного:
[[2,4],[1,3],[2,4],[1,3]]
Он выдает вывод:
Узел со значением 2 не существует в исходном графике.
Что кажется совершенно неправильным, так как существует узел со значением 2. В чем может быть проблема в приведенном выше коде?
Ответ №1:
Это происходит потому, что вы изменяете входной график, делая:
nodeNeighbors.shift();
По-видимому, тестовый код LeetCode не поддерживает свою собственную копию входного графика, поэтому, когда он запускает ваш код и пытается сравнить входной график с возвращенным графиком, он обнаруживает, что во входном графике узел 1 не имеет соседей и, следовательно, говорит, что узла 2 нет.
Поэтому не изменяйте входной график и измените следующие две строки:
while (nodeNeighbors.length > 0) {
const currentNeighbor = nodeNeighbors.shift();
…чтобы:
for (const currentNeighbor of nodeNeighbors) {
Еще одна реализация
Вы могли бы рассмотреть возможность использования рекурсии вместо использования явного стека.
var cloneGraph = function(node) {
if (!node) return null;
const nodeMap = [0];
const dfs = ({ val, neighbors }) =>
Object.assign(nodeMap[val] = new Node(val), {
neighbors: neighbors.map(neighbor =>
nodeMap[neighbor.val] ?? dfs(neighbor)
)
});
return dfs(node);
};