logo

TechCodeview

Algoritmos y estructura de datos gráficos

Estructura de datos del gráfico es una colección de nodos conectado por bordes . Se utiliza para representar relaciones entre diferentes entidades. Algoritmos gráficos son métodos utilizados para manipular y analizar gráficos, resolviendo diversos problemas como encontrar el camino más corto o detección de ciclos.

concatenar cadenas

Tabla de contenidos



Componentes de un gráfico:

  • Vértices: Los vértices son las unidades fundamentales del gráfico. A veces, los vértices también se conocen como vértices o nodos. Cada nodo/vértice se puede etiquetar o no etiquetar.
  • Bordes: Los bordes se dibujan o se utilizan para conectar dos nodos del gráfico. Se pueden ordenar pares de nodos en un gráfico dirigido. Los bordes pueden conectar dos nodos cualesquiera de cualquier forma posible. No hay reglas. A veces, los bordes también se conocen como arcos. Cada borde se puede etiquetar/desetiquetar.

Operaciones básicas en gráficos:

A continuación se muestran las operaciones básicas en el gráfico:

  • Inserción de nodos/bordes en el gráfico: inserte un nodo en el gráfico.
  • Eliminación de nodos/bordes en el gráfico: elimina un nodo del gráfico.
  • Búsqueda en gráficos: busque una entidad en el gráfico.
  • Recorrido de gráficos: atravesar todos los nodos del gráfico.

Aplicaciones de gráfico:

Las siguientes son las aplicaciones de la vida real:

  • Las estructuras de datos gráficos se pueden utilizar para representar las interacciones entre los jugadores de un equipo, como pases, tiros y tacleadas. El análisis de estas interacciones puede proporcionar información sobre la dinámica del equipo y las áreas de mejora.
  • Comúnmente utilizado para representar redes sociales, como redes de amigos en las redes sociales.
  • Los gráficos se pueden utilizar para representar la topología de las redes informáticas, como las conexiones entre enrutadores y conmutadores.
  • Los gráficos se utilizan para representar las conexiones entre diferentes lugares de una red de transporte, como carreteras y aeropuertos.
  • Los gráficos se utilizan en redes neuronales donde los vértices representan neuronas y los bordes representan las sinapsis entre ellas. Las redes neuronales se utilizan para comprender cómo funciona nuestro cerebro y cómo cambian las conexiones cuando aprendemos. El cerebro humano tiene alrededor de 10^11 neuronas y cerca de 10^15 sinapsis.

Conceptos básicos del gráfico:

BFS y DFS en gráfico:

  • Primer recorrido de amplitud de un gráfico
  • Primer recorrido en profundidad de un gráfico
  • Aplicaciones de la búsqueda en profundidad
  • Aplicaciones del primer recorrido en amplitud
  • Primera búsqueda iterativa en profundidad
  • BFS para gráfico desconectado
  • Cierre transitivo de un gráfico usando DFS
  • Diferencia entre BFS y DFS

Ciclos en gráfico:

  • Detectar ciclo en un gráfico dirigido
  • Detectar ciclo en un gráfico no dirigido
  • Detectar ciclo en un gráfico directo usando colores.
  • Detectar un ciclo negativo en un Gráfico | (Botones Ford)
  • Ciclos de longitud n en un gráfico no dirigido y conectado
  • Detectando ciclo negativo usando Floyd Warshall
  • Clonar un gráfico acíclico dirigido
  • Unión por rango y compresión de ruta en el algoritmo de búsqueda de unión
  • Ruta más corta en el gráfico:
    • El algoritmo del camino más corto de Dijkstra
    • Algoritmo de Bellman-Ford
    • Algoritmo de Floyd Warshall
    • Algoritmo de Johnson para caminos más cortos de todos los pares
    • Ruta más corta en gráfico acíclico dirigido
    • Algoritmo de dial
    • Gráfico de varias etapas (ruta más corta)
    • Ruta más corta en un gráfico no ponderado
    • Algoritmo de ciclo de peso medio (o promedio) mínimo de Karp
    • 0-1 BFS (ruta más corta en un gráfico de peso binario)
    • Encuentre el ciclo de peso mínimo en un gráfico no dirigido

    Árbol de expansión mínimo:

    • Árbol de expansión mínima de Prim (MST)
    • Algoritmo de árbol de expansión mínimo de Kruskal
    • Diferencia entre el algoritmo de Prim y Kruskal para MST
    • Aplicaciones del problema del árbol de expansión mínima
    • Costo mínimo para conectar todas las ciudades.
    • Número total de árboles de expansión en un gráfico
    • Árbol de expansión de producto mínimo
    • Algoritmo de eliminación inversa para árbol de expansión mínimo
    • Algoritmo de Boruvka para el árbol de expansión mínimo

    Clasificación topológica:

    • Clasificación topológica
    • Todos los tipos topológicos de un gráfico acíclico dirigido
    • Algoritmo de Kahn para clasificación topológica
    • Bordes máximos que se pueden agregar a DAG para que siga siendo DAG
    • Camino más largo en un gráfico acíclico dirigido
    • Tipo topológico de un gráfico utilizando el tiempo de salida del vértice

    Conectividad en gráfico:

    • Puntos de articulación (o vértices cortados) en un gráfico
    • Componentes biconectados
    • Puentes en un gráfico
    • Camino y circuito euleriano
    • Algoritmo de Fleury para imprimir caminos o circuitos eulerianos
    • Componentes fuertemente conectados
    • Cuente todos los paseos posibles desde un origen hasta un destino con exactamente k aristas
    • Circuito de Euler en un gráfico dirigido
    • Longitud de la cadena más corta para llegar a la palabra objetivo
    • Encuentre si se puede encadenar una serie de cuerdas para formar un círculo
    • Algoritmo de Tarjan para encontrar componentes fuertemente conectados
    • Caminos para recorrer cada nodo utilizando cada arista (Siete Puentes de Königsberg)
    • Conectividad dinámica | Conjunto 1 (incremental)

    Flujo máximo en gráfico:

    • Introducción al problema de flujo máximo
    • Algoritmo Ford-Fulkerson para el problema de flujo máximo
    • Encuentre el número máximo de caminos disjuntos de bordes entre dos vértices
    • Encuentre el corte s-t mínimo en una red de flujo
    • Emparejamiento bipartito máximo
    • Problema de asignación de canales
    • Introducción al algoritmo Push Relabel
    • Algoritmo de Karger: Conjunto 1: Introducción e implementación
    • Algoritmo de Dinic para Flujo Máximo

    Algunos deben resolver problemas en gráficos:

    • Encuentre la longitud de la región más grande en la matriz booleana
    • Contar el número de árboles en un bosque.
    • Un problema del gráfico de Peterson
    • Clonar un gráfico no dirigido
    • Coloración de gráficos (introducción y aplicaciones)
    • Implementación del problema del viajante (TSP)
    • Problema de cobertura de vértices | Conjunto 1 (Introducción y algoritmo aproximado)
    • Problema de los centros K | Conjunto 1 (algoritmo aproximado codicioso)
    • Modelo Erdos Renyl (para generar gráficos aleatorios)
    • Cartero chino o inspección de ruta | Conjunto 1 (introducción)
    • Algoritmo de Hierholzer para grafo dirigido
    • Comprobar si un gráfico determinado es bipartito o no
    • Problema de la serpiente y la escalera
    • Boggle (Encuentra todas las palabras posibles en un tablero de personajes)
    • Algoritmo Hopcroft Karp para máxima coincidencia: introducción
    • Tiempo mínimo para pudrir todas las naranjas.
    • Construya una gráfica a partir de grados dados de todos los vértices.
    • Determinar si existe un sumidero universal en un gráfico dirigido
    • Número de nodos receptores en un gráfico
    • Problema de dos camarillas (compruebe si Graph se puede dividir en dos camarillas)

    Algunas pruebas:

    • Cuestionarios sobre recorrido de gráficos
    • Cuestionarios sobre el camino más corto del gráfico
    • Cuestionarios sobre el árbol de expansión mínima del gráfico
    • Cuestionarios sobre gráficos

    Enlaces rápidos :

    • Las 10 preguntas principales de la entrevista sobre búsqueda en profundidad (DFS)
    • Algunas preguntas interesantes sobre el camino más corto
    • Vídeos sobre gráficos

    Recomendado:

    • Aprenda la estructura de datos y los algoritmos | Tutorial de DSA