Сложность: 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): извлеките узел из начала очереди, посетите всех соседей этого узла. Если какой-либо сосед уже был посещен, получите его клон из хеш-таблицы посещенных; если нет, создайте клон и добавьте его в хеш-таблицу. Добавьте клоны соседей в список соседей клонированного узла.
😎 Решение:
function cloneGraph($node) {
if ($node === null) return $node;
$visited = new SplObjectStorage();
$queue = [$node];
$visited[$node] = (object) ['val' => $node->val, 'neighbors' => []];
while (!empty($queue)) {
$n = array_shift($queue);
foreach ($n->neighbors as $neighbor) {
if (!$visited->contains($neighbor)) {
$visited[$neighbor] = (object) ['val' => $neighbor->val, 'neighbors' => []];
array_push($queue, $neighbor);
}
array_push($visited[$n]->neighbors, $visited[$neighbor]);
}
}
return $visited[$node];
}Ставь 👍 и забирай 📚 Базу знаний