Graficar estructura de datos y Algorithms (Ejemplo)
sarah chen
⚡ Resumen inteligente
La estructura de datos de grafos es una colección no lineal de vértices y aristas, donde cada arista conecta un par de vértices. Los grafos modelan redes del mundo real, como mapas, conexiones sociales y páginas web, y admiten numerosos algoritmos potentes.
¿Qué es un gráfico en la estructura de datos?
Un grafo 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 las aristas funcionan como un enlace entre un par de vértices.
Se utiliza para resolver problemas del mundo real, como encontrar la mejor ruta hacia el destino y la ruta para telecomunicaciones y redes sociales. Los usuarios se consideran nodos en el grafo, y los cables son las aristas que los conectan.
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í tienes un ejemplo sencillo de una estructura de datos de grafo:
Se trata de un grafo simple no dirigido (un tipo de grafo). El conjunto de vértices es: {A, B, C, D, E, F}. Dos vértices forman una arista. Por ejemplo, A y B están conectados por una arista. Sin embargo, A y F no están conectados por ninguna arista.
Terminologías de gráficos en la estructura de datos
A continuación se presentan algunos términos importantes utilizados en la estructura de datos de grafos:
| Término | Mareas Ideales para Lecciones |
|---|---|
| Vértice | Cada elemento de datos se denomina vértice o nodo. En la imagen anterior, A, B, C, D y E son los vértices. |
| Borde (Arco) | Los enlaces que conectan dos nodos o vértices se denominan aristas (arcos). Tienen dos extremos y se representan como (vérticeInicial, vérticeFinal). |
| Borde no dirigido | Es un borde bidireccional. |
| Borde dirigido | Es un borde unidireccional. |
| Borde ponderado | Una arista con un valor. |
| Grado | En un grafo, el número de aristas conectadas a un vértice se denomina 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 dos vértices son adyacentes si existe una arista que los conecta. |
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
¿Cómo representar un grafo en una estructura de datos?
Un grafo se suele almacenar en memoria utilizando una de dos representaciones. La elección de la representación influye en la cantidad de memoria que utiliza el grafo y en la velocidad de ejecución de las operaciones habituales.
- Matriz de adyacencia: Una matriz bidimensional V × V donde la celda [i][j] es 1 (o el peso de la arista) si existe una arista entre el vértice i y el vértice j, y 0 en caso contrario. Permite una búsqueda de aristas de O(1), pero utiliza un espacio de O(V²), lo que la hace ideal para grafos densos.
- Lista de adyacencia: Se trata de una matriz de listas donde cada vértice almacena una lista de sus vértices vecinos. Utiliza un espacio de O(V + E) y es eficiente para grafos dispersos, razón por la cual la mayoría de los grafos del mundo real la utilizan.
Puedes leer más sobre esto en el Lista de adyacencia y representación matricial de un grafo tutorial.
Aplicaciones de la estructura de datos gráficos
Un grafo tiene muchos casos de uso. Existen muchos algoritmos que utilizan grafos. Estas son algunas de las aplicaciones de los grafos:
- Google Los mapas utilizan 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 el origen y el destino.
- Facebook utiliza grafos para encontrar los amigos en común de los usuarios. Su algoritmo considera a cada usuario como un nodo de un grafo.
- Para la asignación de recursos se utiliza un DAG (Grafo Acíclico Dirigido). Este verifica la dependencia entre los recursos.
- El Google Los motores de búsqueda utilizan gráficos para crear la clasificación de los sitios web.
- Un mapaping El dispositivo utiliza la estructura de datos de grafo.
- A Router y su protocolo utiliza el grafo para aprender la ruta hacia el destino.
