Una guía para la estructura de datos del gráfico

Un programador efectivo necesita una sólida comprensión de las estructuras de datos y los algoritmos. Las entrevistas técnicas a menudo pondrán a prueba sus habilidades de resolución de problemas y pensamiento crítico.

Los gráficos son una de las muchas estructuras de datos importantes en la programación. En la mayoría de los casos, comprender gráficos y resolver problemas basados en gráficos no es fácil.

MAKEUSEOF VÍDEO DEL DÍA

¿Qué es un gráfico y qué necesitas saber sobre él?

cosas productivas para hacer en Internet

¿Qué es un gráfico?

Un gráfico es una estructura de datos no lineal que tiene nodos (o vértices) con bordes que los conectan. Todos los árboles son subtipos de gráficos, pero no todos los gráficos son árboles, y el gráfico es la estructura de datos a partir de la cual se originaron los árboles.

Aunque puedes construir estructuras de datos en JavaScript y otros lenguajes, puede implementar un gráfico de varias maneras. Los enfoques más populares son listas de borde , listas de adyacencia , y matrices de adyacencia .

los Guía de Khan Academy para representar gráficas es un gran recurso para aprender a representar un gráfico.

Hay muchos tipos diferentes de gráficos. Una distinción común es entre dirigido y no dirigido gráficos; estos surgen mucho en los desafíos de codificación y los usos de la vida real.

Tipos de gráficos

Gráfico dirigido: Un gráfico en el que todos los bordes tienen una dirección, también conocido como dígrafo.
Gráfico no dirigido: Un gráfico no dirigido también se conoce como gráfico de dos vías. En gráficos no dirigidos, la dirección de los bordes no importa y el recorrido puede ir en cualquier dirección.
Gráfico ponderado: Un grafo ponderado es un grafo cuyos nodos y aristas tienen un valor asociado. En la mayoría de los casos, este valor representa el costo de explorar ese nodo o borde.
Gráfico finito: Un gráfico que tiene un número finito de nodos y aristas.
Gráfico infinito: Un gráfico que tiene una cantidad infinita de nodos y aristas.
Gráfico trivial: Un gráfico que tiene un solo nodo y ningún borde.
gráfico sencillo: Cuando solo un borde conecta cada par de nodos de un gráfico, se llama un gráfico simple.
Gráfico nulo: Un gráfico nulo es un gráfico que no tiene bordes que conecten sus nodos.
Multigrafo: En un multigrafo, al menos un par de nodos tienen más de un borde que los conecta. En los multigrafos, no hay bucles automáticos.
Gráfico completo: Un gráfico completo es un gráfico en el que cada nodo se conecta con todos los demás nodos del gráfico. También es conocido como un gráfico completo .
Pseudográfico: Un gráfico que tiene un bucle propio aparte de otros bordes del gráfico se denomina pseudográfico.
Gráfico regular: Un gráfico regular es un gráfico donde todos los nodos tienen grados iguales; es decir, cada nodo tiene el mismo número de vecinos.
Gráfico conectado: Un gráfico conexo es simplemente cualquier gráfico en el que dos nodos se conectan; es decir, un gráfico con al menos un camino entre cada dos nodos del gráfico.
Gráfico desconectado: Un gráfico desconectado es el opuesto directo de un gráfico conectado. En un gráfico desconectado, no hay bordes que unen los nodos del gráfico, como en un nulo grafico.
Gráfico cíclico: Un gráfico cíclico es un gráfico que contiene al menos un ciclo de gráfico (un camino que termina donde comenzó).
Gráfico acíclico: Un gráfico acíclico es un gráfico sin ciclos en absoluto. Puede ser dirigido o no dirigido.
Subgrafo: Un subgrafo es un grafo derivado. Es un grafo formado por nodos y aristas que son subconjuntos de otro grafo.