Graficar estructura de datos y Algorithms (Ejemplo)
sarah chen
¿Qué es un gráfico en la estructura de datos?
Un gráfico es una estructura de datos no lineal que consta de vértices y aristas, donde los vértices contienen la información o los datos, y los bordes funcionan como un vínculo entre un par de vértices.
Se utiliza para resolver problemas reales como encontrar la mejor ruta a la ubicación de destino y la ruta para telecomunicaciones y redes sociales. Los usuarios se consideran un nodo en Graph y los cables son los bordes que conectan a los usuarios.
Si las aristas se representan como E y los vértices se representan como V, entonces el gráfico G se puede escribir como el conjunto de vértices y aristas, como G (V, E)
Ejemplo de gráfico en estructura de datos
Aquí hay un ejemplo simple de estructura de datos de gráficos:
Es un gráfico simple no dirigido (un tipo de gráfico). Aquí el conjunto de vértices es: {A, B, C,D,E,F}. Dos vértices crean un borde. Por ejemplo, A y B están unidos por una arista. Sin embargo, A y F no están vinculados con ninguna arista.
Terminologías de gráficos en la estructura de datos
Los siguientes son algunos términos importantes utilizados en la estructura de datos del gráfico:
| Término | DESCRIPCIÓN |
|---|---|
| Vértice | Todo elemento de datos se llama vértice o nodo. En la imagen de arriba, A, B, C, D y E son los vértices. |
| Borde (Arco) | Los enlaces de conexión entre dos nodos o vértices se denominan aristas (arco). Tiene dos extremos y se representa como (inicioVértice, finalizandoVértice). |
| Borde no dirigido | Es un borde bidireccional. |
| Borde dirigido | Es un borde unidireccional. |
| Borde ponderado | Una ventaja con valor. |
| Grado | En Graph, el número de aristas conectadas a un vértice se llama grado. |
| grado | El número total de aristas entrantes conectadas a un vértice. |
| Grado superior | El número total de aristas salientes conectadas a un vértice. |
| Auto-bucle | Una arista se denomina autobucle si sus dos extremos coinciden. |
| Proximidad | Se dice que los vértices son adyacentes si una arista está conectada. |
Tipos de gráficos en estructura de datos
Aquí está la lista de los más comunes. tipos de gráficos en la estructura de datos:
- Gráfico dirigido
- Gráfico no dirigido
- Gráfico ponderado
- Gráfico bidireccional
- Gráfico infinito
- Gráfico nulo
- Gráfico trivial
- Gráfico múltiple
- Gráfico completo
- Gráfico conectado
- Gráfico cíclico
- Gráfico acíclico dirigido (DAG)
- Gráfico de ciclo
- Gráfica bipartita
- Gráfico de Euler
- Gráfico de Hamilton
Aplicaciones de la estructura de datos gráficos
Un gráfico tiene muchos casos de uso. Hay muchos algoritmos que utilizan mucho los gráficos. Estas son algunas de las aplicaciones del gráfico:
- Google Maps utiliza gráficos para encontrar la intersección de dos carreteras y calcular la distancia entre dos ubicaciones.
Por ejemplo, Dijkstra, para encontrar la distancia más corta entre la ubicación de origen y destino. - Facebook utiliza Graphs para encontrar amigos mutuos de los usuarios. Su algoritmo considera a cada usuario como un nodo de un gráfico.
- Para la asignación de recursos, se utiliza DAG (Gráfico acíclico directo). Comprueba la dependencia de los recursos.
- El motor de búsqueda de Google utiliza gráficos para crear la clasificación de los sitios web.
- Un dispositivo de mapeo utiliza la estructura de datos del gráfico.
- Router y el protocolo de t utiliza Graph para conocer la ruta de la ruta de destino.
