Estructuras de datos y algoritmos · Grafos

Recorrido de grafos (BFS y DFS)

Visitar cada vértice alcanzable, ya sea nivel por nivel (BFS) o profundizando primero (DFS).

Empezar una lección sobre Recorrido de grafos (BFS y DFS)

Aprende antes

• Representaciones de grafos: Almacenar los vértices y aristas de un grafo como una matriz de adyacencia o una lista de adyacencia.
• Pilas y colas: Dos ordenamientos de acceso restringido, último en entrar primero en salir y primero en entrar primero en salir.

Lleva a

• Ordenamiento topológico: Ordenar los vértices de un grafo dirigido acíclico para que cada arista apunte hacia adelante.
• Algoritmo de Dijkstra: Encontrar el camino más barato desde un vértice hacia todos los demás cuando ningún peso de arista es negativo.
• Algoritmo de Bellman-Ford: Encontrar caminos más cortos que sigue funcionando cuando algunos pesos de arista son negativos, a costa de la velocidad.

Temas relacionados

• Ordenamiento topológico: Ordenar los vértices de un grafo dirigido acíclico para que cada arista apunte hacia adelante.
• Backtracking: Probar una elección, recurrir, y deshacerla si no lleva a ningún lado, para explorar todas las posibilidades.