24 de Março
Clonar grafo
Como fazer cópia profunda de um grafo com ciclos, mantendo um mapeamento claro entre nós antigos e novos.
Grafos Intermediario 20 min TypeScript
Dado um no de um grafo conexo e não direcionado, retorne uma copia profunda do grafo.
Cada no tem:
valneighbors
No problema original, a entrada costuma ser uma referência para o no 1.
Aqui no SeniorPath, para manter a comparação deterministica, use uma lista de adjacencia:
adjList[i]representa os vizinhos do noi + 1
E retorne uma nova lista de adjacencia com a mesma estrutura.
Exemplo:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
A saída parece igual, mas precisa ser uma copia independente.
O que perceber antes de codar
- O desafio e copiar estrutura com ciclos, não só valores.
- Se você não memorizar os nos já clonados, vai criar duplicatas ou entrar em loop.
- O mapa importante e do no antigo para o no novo.
Erros comuns
- reaproveitar vizinhos do grafo original dentro da copia
- criar uma copia nova toda vez que reencontra o mesmo no
Passo 1 - Entender o que copia profunda quer dizer aqui
Não basta devolver uma estrutura com os mesmos valores.
Copia profunda significa:
- cada no da copia e novo
- as conexões da copia apontam para nos da copia
- nada da copia aponta de volta para o grafo antigo
Passo 2 - Começar pela versão achatada usada aqui
Aqui no SeniorPath, a entrada já vem como lista de adjacencia.
Entao a copia mais direta e:
- criar um novo array
- copiar cada lista de vizinhos
Isso resolve o formato usado aqui.
Mas ainda não ensina o coracao do problema original.
Passo 3 - Ver por que o problema original e mais delicado
Quando a entrada e um no com referencias para vizinhos:
- o grafo pode ter ciclo
- você pode reencontrar o mesmo no várias vezes
Se cada reencontro criar um no novo, a copia quebra.
Passo 4 - Guardar quem já foi clonado
A regra forte e:
- se o no antigo já tem copia, reuse a copia
- se ainda não tem, crie e registre antes de explorar os vizinhos
Esse "registrar antes" e o que evita loop infinito na busca em profundidade (DFS).
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function cloneGraphFromAdjList(adjList: number[][]): number[][] {
// retorne uma copia profunda da lista de adjacencia
return []
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(V + E)
Espaço: O(V)
Solução 1 - Copiar a lista de adjacencia usada aqui
Boa versão inicial para a representação achatada e deterministica.
export function cloneGraphFromAdjList(adjList: number[][]): number[][] {
return adjList.map((neighbors) => [...neighbors])
}Funciona para o formato usado aqui.
Mas não e a ideia central do problema original, onde a entrada e um grafo de objetos conectados.
Solução 2 - Clonar o grafo de verdade com mapa antigo -> novo em mapa hash e DFS
Agora a versão fiel ao problema usa um grafo de nos e memoriza as copias.
type GraphNode = {
val: number
neighbors: GraphNode[]
}
function buildGraph(adjList: number[][]): GraphNode | null {
if (adjList.length === 0) {
return null
}
const nodes = adjList.map((_, index) => ({ val: index + 1, neighbors: [] as GraphNode[] }))
for (let index = 0; index < adjList.length; index += 1) {
nodes[index].neighbors = adjList[index].map((neighborValue) => nodes[neighborValue - 1])
}
return nodes[0]
}
function cloneGraph(node: GraphNode | null): GraphNode | null {
if (node === null) {
return null
}
const clones = new Map<GraphNode, GraphNode>()
function dfs(current: GraphNode): GraphNode {
const existing = clones.get(current)
if (existing) {
return existing
}
const copy: GraphNode = { val: current.val, neighbors: [] }
clones.set(current, copy)
for (const neighbor of current.neighbors) {
copy.neighbors.push(dfs(neighbor))
}
return copy
}
return dfs(node)
}
function toAdjList(node: GraphNode | null): number[][] {
if (node === null) {
return []
}
const result: number[][] = []
const queue: GraphNode[] = [node]
const seen = new Set<number>([node.val])
while (queue.length > 0) {
const current = queue.shift()!
result[current.val - 1] = current.neighbors.map((neighbor) => neighbor.val)
for (const neighbor of current.neighbors) {
if (!seen.has(neighbor.val)) {
seen.add(neighbor.val)
queue.push(neighbor)
}
}
}
return result
}
export function cloneGraphFromAdjList(adjList: number[][]): number[][] {
const root = buildGraph(adjList)
const clonedRoot = cloneGraph(root)
return toAdjList(clonedRoot)
}O insight forte aqui e que o mapa não e “valor para valor”.
O mapa e:
- no antigo para no novo
O que dizer na entrevista
Uma explicação curta e boa seria:
Copia profunda de grafo com ciclo pede um mapa dos nos já clonados. Eu uso um mapa do no original para o no clonado. Quando encontro um no pela primeira vez, crio a copia e registro imediatamente. Quando reencontro esse no, só reutilizo a copia já criada. Assim eu evito loop infinito e também evito duplicar nos.
Isso mostra que você:
- entendeu por que ciclo muda o problema
- separou bem identidade antiga e identidade nova
- justificou a necessidade do mapa
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- fazer copia profunda de estrutura com referencias
- percorrer grafo com ciclo
- usar
busca em profundidade (DFS)oubusca em largura (BFS)com mapa de nos já clonados - manter um mapa entre entidades antigas e novas durante migração ou transformação
O ponto não e decorar esse problema.
O ponto e aprender quando copiar sem memorizar quebra a identidade da estrutura.