¿Cuáles son algunos de los algoritmos gráficos que se suelen pedir en las ubicaciones de los campus?

Algoritmos Gráficos:

Introducción, DFS y BFS: (importante para entrevistas en el campus)

  1. Gráfica y sus representaciones
  2. Amplitud del primer recorrido para un gráfico
  3. Profundidad del primer recorrido para un gráfico
  4. Aplicaciones de Profund First Search
  5. Detectar ciclo en un gráfico dirigido
  6. Detectar ciclo en un gráfico no dirigido
  7. Detectar ciclo en un gráfico no dirigido
  8. Trayectoria más larga en un gráfico acíclico dirigido
  9. Clasificación topológica
  10. Compruebe si un gráfico dado es bipartito o no
  11. Problema de serpiente y escalera
  12. Componentes Biconnectados
  13. Compruebe si un gráfico dado es árbol o no

Caminos más cortos: (importante para entrevistas en el campus)

  1. El algoritmo de ruta más corta de Dijkstra
  2. Algoritmo de Dijkstra para la representación de la lista de adyacencia
  3. Algoritmo de Bellman-Ford
  4. Algoritmo de Floyd Warshall
  5. El algoritmo de Johnson para los caminos más cortos de todos los pares
  6. Ruta más corta en el gráfico acíclico dirigido
  7. Algunas preguntas interesantes sobre el camino más corto
  8. Trayectoria más corta con exactamente k aristas en un gráfico dirigido y ponderado

Para obtener más información, puede consultar las preguntas que se detallan a continuación.

Árbol de expansión mínima:

  1. Árbol de expansión mínima de Prim (MST))
  2. Aplicaciones del problema del árbol de expansión mínimo
  3. MST de Prim para la representación de la lista de adyacencia
  4. Algoritmo de árbol de expansión mínimo de Kruskal
  5. Algoritmo de Boruvka para árbol de expansión mínima

Conectividad:

  1. Encuentre si hay un camino entre dos vértices en un gráfico dirigido
  2. Conectividad en un gráfico dirigido
  3. Puntos de articulación (o vértices de corte) en un gráfico
  4. Gráfico biconnectado
  5. Puentes en un gráfico
  6. Camino y circuito euleriano
  7. Algoritmo de Fleury para imprimir Ruta o Circuito Euleriano
  8. Componentes fuertemente conectados
  9. Cierre transitivo de un gráfico.
  10. Encuentra el número de islas
  11. Cuente todas las caminatas posibles desde una fuente a un destino con exactamente k bordes
  12. Circuito de Euler en un gráfico dirigido
  13. Componentes Biconnectados
  14. Algoritmo de Tarjan para encontrar componentes fuertemente conectados

Problemas difíciles

  1. Colorear Gráficos (Introducción y Aplicaciones)
  2. Algoritmo codicioso para colorear gráficos
  3. Problema de vendedor ambulante (programación ingenua y dinámica)
  4. Problema de vendedor ambulante (aproximado usando MST)
  5. Ciclo Hamiltoniano
  6. Problema de cubierta de vértice (Introducción y algoritmo aproximado)
  7. Problema de K Centres (Algoritmo aproximado codicioso)

Flujo máximo:

  1. Algoritmo Ford-Fulkerson para el problema de flujo máximo
  2. Encuentra el número máximo de caminos disjuntos de borde entre dos vértices
  3. Encuentre el corte st mínimo en una red de flujo
  4. Máxima coincidencia bipartita
  5. Problema de asignación de canales

Misceláneo:

  1. Averigua si las cadenas se pueden encadenar para formar un círculo.
  2. Dado un diccionario ordenado de un idioma extranjero, encuentre el orden de los caracteres
  3. Algoritmo de Karger para corte mínimo
  4. Algoritmo de Karger para corte mínimo | Conjunto 2 (Análisis y Aplicaciones)
  5. Hopcroft-Karp Algorithm for Maximum Matching | Conjunto 1 (Introducción)
  6. Hopcroft-Karp Algorithm for Maximum Matching | Conjunto 2 (Implementación)
  7. Longitud de la cadena más corta para alcanzar una palabra objetivo
  8. Encuentra los mismos contactos en una lista de contactos

Algoritmos gráficos que se solicitan en entrevistas

1. Básico

a. BFS (iterativo y recursivo)

si. DFS (iterativo y recursivo)

C. Detección de ciclos

re. Clasificación topológica

mi. Componentes fuertemente conectados de Kosaraju

2. Algorims de árbol de expansión mínimo

a. Prints MST

si. Krushkals MST

3. Algoritmos de ruta más corta

a. Ruta más corta de una sola fuente

– Dijkstra camino más corto

– Bellman-Ford

– Floyd Warshall

si. Todos los pares de ruta más corta (tema avanzado)

– El camino más corto de todos los pares de Johnsons Algo

4. Problemas diversos

a. Gráfica bipartita

si. Problema de vendedor ambulante (tema avanzado, solo teoría requerida)

C. Ciclo hamiltoniano (avance, solo teoría)

re. Algoritmos de flujo máximo

– Varios algoritmos bajo esto, puedes preparar unos fáciles

Recomiendo utilizar la preparación de la entrevista de codificación de manera fácil

o Conceptos básicos de algoritmos de gráficos que puede consultar

1. Princeton University Algo y DS parte 2 en Courseera

2. Stanford Univerity Algo y DS parte 2 en Courseera

De lo contrario, mi blog también tiene algoritmos gráficos.

A continuación se presentan algunas preguntas de la entrevista en gráficos:

Terminología y representaciones de gráficos
Implementación de gráficos usando STL
Implementación de gráficos en C ++ sin usar STL
Breadth First Search (BFS) | Implementación iterativa y recursiva
Profundidad primera búsqueda (DFS) | Implementación iterativa y recursiva
Hora de llegada y salida de vértices en DFS
Tipos de aristas involucradas en DFS y relación entre ellas
Gráfica bipartita
Número mínimo de lanzamientos necesarios para ganar el juego de serpiente y escalera
Clasificación topológica en un DAG
Cierre transitivo de un gráfico
Compruebe si un gráfico no dirigido contiene ciclo o no
Número total de rutas en un dígrafo dado desde el origen hasta el destino que tienen exactamente m bordes
Determine si un gráfico no dirigido es un árbol (gráfico conectado acíclico)
Conectividad de 2 bordes en el gráfico
2-Vertex Connectivity en el gráfico
Compruebe si el dígrafo dado es un DAG (Gráfico Acíclico Dirigido) o no
Estructura de datos de conjunto disjunto (Algoritmo de búsqueda de unión)
Problema de Chess Knight: encuentra el camino más corto desde el origen hasta el destino
Verifique si el gráfico dado está fuertemente conectado o no
Verifique si el gráfico dado está fuertemente conectado o no utiliza un recorrido transversal DFS
Algoritmo Union-Find para detección de ciclo en gráfico no dirigido
Algoritmo de Kruskal para encontrar el árbol de expansión mínimo
Senderos más cortos de una sola fuente – Algoritmo de Dijkstra
Senderos más cortos de una sola fuente: algoritmo Bellman Ford
Caminos más cortos de todos los pares – Algoritmo de Floyd Warshall

Imprima todas las configuraciones k-colorables del gráfico (coloración de vértice del gráfico)
Imprima todo el Camino Hamiltoniano presente en un gráfico
Coloración codiciosa del gráfico