Estructuras de Datos Generales - SergioRiosC/Datos-1 GitHub Wiki
Los grafos son estructuras de datos generales aplicables en muchas areas como
-Sociologia
-Quimica
-Geografia
-Criminologia
Un grafo G agrupa entidades que representan conceptos
Se compone de vertices/Nodos que representan cada entidad
Y de artista/arcos que representan relaciones entre nodos
G={v,a}
v={1,2,6}
A={(1,2),(2,1),(2,6)}
Un grupopuede ser dirigido o no dirigido. El ejemplo anterior es un grafo no dirigido. el siguiente es un grafo dirigido
G={V,A}
V={1,2,6}
A={(1,2),(1,6),(2,6),(6,2)}
Los arcos pueden tener magnitud creando un arbol con peso
El grado de un nodo es la cantidad de conexiones que participa Cartago:5
En un grafo dirigido, hay un grafo saliente y otro entrante
Un camino P={V0,V1,V2...,Vn} es el conjunto de vertices que conectan V0->Vn
Un ciclo es un grafo que comienza y termina en el mismo nudo
Un grafo es aciclico si no tiene ciclos
Un DAG(directed acyclic graph) es un nodo dirigido sin ciclos
Como se implementa un grafo?
Hay dos formas:
Matriz de adyacencia
Listas de adyacencia
Matriz de adyacincia:
Dado un grafo de h vertices, se costruye una matriz hxh donde cada elemento
A[i][j]
tiene uno de los siguientes valores
a[i][j]: 1 si hay arco de Vi-Vj, 0 si no
Una lista de adyacencia es una lista enlazada donde cada elemento es un nodo de grafo. Cada elemento tiene una lista con sus conecciones
Elegir entre una u otra forma depende de:
-Algoritmos por aplicar
-Densidad del grafo
alta-Matriz
baja=lista
Como se recorre un grafo?
Se reconoce desde un nodo especifico y hasta recorrrer todos los nodos alcanzables
La ruta mas corta entre un nodo y el resto:
-Es uno de los problemas mascomunes de los grafos
-Edgar Dijsktra propone un algoritmo que calcula la ruta mas corta (grafo con peso, grafo dirijido)
Pasos:
1-Asignar a todos los nodos infinito menos al inicial
2-Calcular el valor a todos los nodos a partir del inicial
3-Seleccionar el nodo menor y nos movemos a este, se recalculan las distancias usando el nuevo nodo como"puente"
4-Se sigue seleccionando el menor no visitado y se recalcula