Сложность: medium
Дана ссылка на узел в связанном неориентированном графе.
Верните глубокую копию (клон) графа.
Каждый узел в графе содержит значение (целое число) и список (List[Node]) своих соседей.
Пример:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
👨💻 Алгоритм:
1️⃣Используйте хеш-таблицу для хранения ссылок на копии всех уже посещенных и скопированных узлов. Ключом будет узел оригинального графа, а значением — соответствующий клонированный узел клонированного графа. Хеш-таблица посещенных узлов также используется для предотвращения циклов.
2️⃣Добавьте первый узел в очередь, клонируйте его и добавьте в хеш-таблицу посещенных.
3️⃣Выполните обход в ширину (BFS): извлеките узел из начала очереди, посетите всех соседей этого узла. Если какой-либо сосед уже был посещен, получите его клон из хеш-таблицы посещенных; если нет, создайте клон и добавьте его в хеш-таблицу. Добавьте клоны соседей в список соседей клонированного узла.
😎 Решение:
var cloneGraph = function (node) {
if (node === null) return node;
const visited = new Map();
const queue = [node];
visited.set(node, { val: node.val, neighbors: [] });
while (queue.length > 0) {
const n = queue.shift();
n.neighbors.forEach((neighbor) => {
if (!visited.has(neighbor)) {
visited.set(neighbor, { val: neighbor.val, neighbors: [] });
queue.push(neighbor);
}
visited.get(n).neighbors.push(visited.get(neighbor));
});
}
return visited.get(node);
};Ставь 👍 и забирай 📚 Базу знаний