Semanas 11 y 12 Grafos

Semanas 11 y 12: Grafos

Objetivo

Reconocer representaciones de grafos, elegir entre DFS/BFS, detectar ciclos y modelar componentes conectados con seguridad.

Problemas Completados

Problema	Patrón	Función	Tests
Number of Islands	DFS en matriz	number_of_islands	2
Max Area of Island	DFS en matriz	max_area_of_island	2
Pacific Atlantic Water Flow	BFS inverso desde bordes	pacific_atlantic	2
Rotting Oranges	BFS multisource	oranges_rotting	2
Walls and Gates	BFS multisource	walls_and_gates	2
Course Schedule	Ordenamiento topológico	can_finish	2
Course Schedule II	Ordenamiento topológico	find_course_order	2
Redundant Connection	Union Find	redundant_connection	2
Number of Connected Components	Union Find	count_connected_components	2
Graph Valid Tree	Union Find	graph_valid_tree	2
Is Graph Bipartite	BFS con coloreo	is_bipartite	2
Number of Provinces	Union Find en matriz	find_circle_num	2
Possible Bipartition	BFS con coloreo 1-indexado	possible_bipartition	2
Evaluate Division	Grafo ponderado multiplicativo	evaluate_division	2
Alien Dictionary	Ordenamiento topológico de caracteres	alien_order	2
Accounts Merge	Componentes conectados	accounts_merge	2
Clone Graph	BFS en lista de adyacencia	clone_graph	2

Ideas Clave

DFS en Matriz

Se usa para consumir componentes conectados celda por celda.

Invariante:

• Solo se visita una celda si está dentro de límites, no ha sido visitada y cumple la condición del problema.

BFS Multisource

Se usa cuando varios puntos iniciales se expanden al mismo tiempo.

Ejemplos:

• Naranjas podridas.
• Habitaciones y puertas.

Invariante:

• La primera vez que una celda se visita, ya se encontró su distancia mínima desde alguna fuente.

BFS Inverso desde Bordes

En Pacific Atlantic, buscar desde cada celda hacia océanos es costoso. La inversión útil es iniciar desde los bordes y moverse hacia alturas mayores o iguales.

Invariante:

• Si desde un borde puedo subir hasta una celda, entonces desde esa celda se puede bajar hasta ese borde.

Ordenamiento Topológico

Kahn usa indegrees:

• Cursos con indegree 0 no tienen prerequisitos pendientes.
• Al tomar un curso, se reduce el indegree de sus vecinos.
• Si no se procesan todos los cursos, existe un ciclo.

Union Find

Se usa para conectar componentes y detectar si una arista une nodos que ya estaban conectados.

Invariante:

• find(x) devuelve el representante actual de la componente.
• union(a, b) devuelve falso cuando a y b ya comparten representante.
• Para contar componentes, cada unión exitosa reduce el total de grupos en uno.
• Para validar un árbol, deben cumplirse dos condiciones: n - 1 aristas y ninguna unión redundante.
• Para provincias, la matriz de adyacencia se recorre como grafo no dirigido.

BFS con Coloreo

Se usa para verificar si un grafo puede separarse en dos grupos sin que una arista conecte nodos del mismo grupo.

Invariante:

• Cada vecino debe tener el color opuesto al nodo actual.
• Si aparece una arista entre nodos del mismo color, el grafo no es bipartito.
• En possible_bipartition, los nodos vienen 1-indexados y deben normalizarse con cuidado.

Grafos Ponderados Multiplicativos

En evaluate_division, cada ecuación crea dos aristas dirigidas: una con el valor dado y otra con su recíproco.

Invariante:

• El producto acumulado en BFS representa la razón desde el origen hasta el nodo actual.
• Si una variable no existe en el grafo, la consulta no tiene respuesta.

Ordenamiento Topológico de Caracteres

En alien_order, la primera diferencia entre dos palabras adyacentes define una relación de precedencia.

Invariante:

• Si una palabra larga aparece antes que su prefijo exacto, el orden es inválido.
• Si no se procesan todos los caracteres, existe un ciclo.

Representación en Rust

Matrices:

Vec<Vec<i32>>

Listas de adyacencia:

Vec<Vec<usize>>

Grafos etiquetados:

HashMap<String, Vec<String>>

Errores Comunes

• Marcar visitado demasiado tarde y meter la misma celda varias veces a la cola.
• Confundir BFS multisource con correr BFS desde cada fuente.
• En Pacific Atlantic, moverse en la dirección equivocada al invertir la búsqueda.
• Olvidar que un ciclo en prerequisitos deja nodos sin procesar.
• En Union Find, no comprimir caminos y degradar rendimiento en casos grandes.
• En grafos bipartitos, olvidar reiniciar BFS desde componentes desconectadas.
• En Evaluate Division, olvidar agregar la arista recíproca.
• En Alien Dictionary, no detectar el caso de prefijo inválido.

Verificación

cargo test

Resultado al cerrar el bloque:

373 passed; 0 failed

Siguiente Bloque

El siguiente bloque recomendado es:

• Montículos.
• Intervalos.
• Greedy.

Primeros problemas sugeridos:

• Kth Largest Element in an Array.
• Find Median from Data Stream.
• Merge Intervals.
• Insert Interval.
• Meeting Rooms II.