¿Qué algoritmos gráficos (10-15, tal vez) sugeriría que hicieran bien en la programación competitiva?

Existen los algoritmos más utilizados que debe conocer:

Más comúnmente utilizado y debe estar en propinas.

1) BFS, la ruta más corta en un gráfico no pesado

2) DFS: detección de ciclo, componentes conectados, relleno de inundación, detección de clúster

3) Dijkstra y aplicaciones

4) Bellman Ford

5) Floyd Warshall

6) Unión – Buscar (aprender sobre la compresión de ruta)

7) MST – Prim y Kruksal

Menos frecuente pero aún común

1) Problema de vendedor ambulante (TSP con Bitmasking) – Ciclo Hamiltoniano

2) Max-flow / Min-flow es menos frecuente pero se le puede preguntar si se está preparando para ACM-ICPC o competencias de codificación en línea.

Espero que esto ayude.

Prateek Bhayia

(Miembro fundador, bloques de codificación)

Los algoritmos gráficos más utilizados, beneficiosos en CP son:

1. Breadth First Search (BFS)
2. Profundidad de la primera búsqueda (DFS)
3. El camino más corto desde la fuente a todos los vértices ** Dijkstra **
4. El camino más corto desde cada vértice a cualquier otro vértice ** Floyd Warshall **
5. Árbol de expansión mínimo ** Prim **
6. Árbol de expansión mínimo ** Kruskal **
7. Clasificación topológica
8. Algoritmo de Johnson
9. Puntos de articulación (o vértices de corte) en un gráfico
10. Puentes en un gráfico

También eche un vistazo a los siguientes algoritmos que se usan con frecuencia en CP para problemas de medios a difíciles:

1. Árbol de segmentos (con propagación diferida)
2. Árbol de intervalo
3. Árbol indexado binario
4. Multiplicación rápida de módulos (cuadratura exponencial)
5. Algoritmos Heurísticos
6. Búsqueda de cadenas KMP
7. Algoritmo de Manacher
8. Conjunto de búsqueda / disjunto de unión
9. Trie
10. Primer Miller Rabin
11. Recurrencia matricial + multiplicación rápida de módulos para contar
12. Problema de matrimonio estable
13. Algoritmo de Euclides extendido
14. Búsqueda ternaria
15. Transformada rápida de Fourier para una multiplicación polinómica rápida
16. Algoritmo de Djikstra, algoritmo de Bellman-Ford, algoritmo de Floyd-Warshall
17. Algoritmo de Prim, Algoritmo de Kruskal
18. RMQ, LCA
19. Algoritmos relacionados con el flujo, problema de asignación, algoritmo húngaro
20. Algoritmos de coincidencia bipartitos
21. Descomposición de luz pesada
22. Algoritmo de línea de barrido
23. Algoritmo Z
24. Casco convexo
25. Matrices de sufijos
26. LCP
27. Árbol de sufijo
28. Eliminación gaussiana
29. Integración / diferenciación numérica
30. Recorte de línea
31. Problemas avanzados de matemáticas ad-hoc
32. Algoritmo de coincidencia de cadenas Aho-Corasick;
33. Calcule nCr% M Teorema de Lucas
34. Descomposición ligera pesada en árboles
35. Operaciones de modulo inverso
36. Factorización de Rho Pollard Integer
37. Números catalanes

Sí, creo que vale la pena saber Ford-Fulkerson.

Pero también quizás algunos algoritmos de vendedores ambulantes, como Cristofides.

El algoritmo para encontrar incrustaciones planas en tiempo lineal.

Conoces Dijkstra, así que supongo que también conoces A * bidireccional.

¿Conoces DFS iterado con poda alfa-beta?

Posiblemente algún algoritmo de búsqueda de 1 factor, como Edmonds ‘Blossom.

Definitivamente un algoritmo, como el de Wilson, para construir árboles aleatorios con cierta propiedad. Es tan importante saber por qué funciona matemáticamente como conocer el algoritmo.

¿Sabía que puede construir gráficos conectados al azar con una secuencia de grados especificada? ¡Hay un algoritmo para eso! Sin embargo, no estoy seguro de lo útil que sería en una competencia de codificación …

Sin embargo, sospecho que algunos algoritmos espectrales podrían ser útiles.

Los que mencionó generalmente son la clave, uno que definitivamente echo de menos en esta lista, ya que es bastante común son los Componentes fuertemente conectados (y luego, por lo general, la clasificación topológica en ellos, pero ya lo mencionó).

Maxflow (Edmonds-Karp) es definitivamente muy importante en concursos / tareas más difíciles. Apenas verá tareas fáciles para él, pero las tareas difíciles de usar son realmente comunes, al menos en los concursos de estilo ACM. También es importante a este respecto que, a diferencia de la mayoría de los otros mencionados aquí, los flujos suelen ser útiles en las tareas que pueden no parecerse a las tareas de teoría de grafos a primera vista, pero solo después de ver cómo podría traducir la tarea en un flujo de grafos problema, entonces puedes resolverlo aplicando Edmonds-Karp.

Las coincidencias también son útiles en los concursos, son solo una versión más fácil de maxflows, pero dado que el algoritmo es un poco diferente, podría ser útil pensar en ellas por separado.

Prateek mencionó Find-Union, también es bastante útil en concursos.

Entre otros algoritmos que no son demasiado comunes, pero que pueden suceder en concursos de vez en cuando, se me ocurren Componentes Biconnectados y algoritmos para encontrar los ciclos de Euler y Hamilton.

Los problemas más difíciles de resolver en HackerRank son la categoría NP Complete y, por lo general, son el último problema que se lanza durante un maratón de código.

Para la teoría de grafos se aplican los sospechosos habituales:

DFS, nodos conectados, grupos, etc.

BFS

Árbol de expansión mínimo de Kruskals (o algoritmo de Prim)

De Dijkstra

Floyd Warshall

Llenado de inundación

Tipo topológico

Verificación de gráfico bipartito

Método de Ford Fulkerson

Método de Edmonds Karp

Estos métodos pueden ayudarlo y analizar la resolución de problemas de archivo que requieren los algoritmos gráficos anteriores. Espero que esta respuesta ayude.