Aquí hay algunos fuera de mi cabeza:
- DFS / BFS
- Algoritmos de ruta más corta (algoritmo de Dijkstra, algoritmo de Floyd, Bellman – Ford, algoritmo de Johnson)
- MST (algoritmo de Prim, algoritmo de Kruskal; no necesariamente necesita saber ambos)
- Un algoritmo de flujo máximo (algoritmo Edmonds-Karp, o un método de flujo previo; este último tiende a ser más rápido en el peor de los casos; para ICPC querrá el algoritmo de Dinić en su libro de códigos, ya que aún es más rápido) y la aplicación reducirá al mínimo y coincidencia bipartita, y, a través del teorema de König, para cubrir el vértice mínimo en un gráfico bipartito
- Un algoritmo de flujo mínimo de costo mínimo
- Camino euleriano (algoritmo de Hierholzer)
- Un algoritmo de componentes fuertemente conectados
- Tipo topológico
- Los algoritmos de Tarjan para encontrar puentes y puntos de articulación
- La descomposición de luz pesada para los árboles.