Un Grafo es una estructura matemática que representa un conjunto de objetos (llamados vértices o nodos) y las conexiones o relaciones entre ellos (llamados aristas o enlaces).
En un grafo, los vértices pueden estar conectados con otros vértices mediante aristas, que pueden ser dirigidas (la arista solo se puede recorrer en una dirección) o no dirigidas (se puede recorrer e ambas direcciones)
Tipos de grafos:
Grafo no dirigido: Un grafo no dirigido es aquel en el que las aristas no tienen una dirección definida. Es decir, la relación entre dos vértices es bidireccional. Por ejemplo, si el vértice A está conectado al vértice B, entonces también se puede decir que el vértice B está conectado al vértice A.
Grafo dirigido: Un grafo dirigido es aquel en el que las aristas tienen una dirección definida. Es decir, la relación entre dos vértices es unidireccional. Por ejemplo, si el vértice A está conectado al vértice B, entonces no necesariamente se puede decir que el vértice B esté conectado al vértice A.
Grafo ponderado: Un grafo ponderado es aquel en el que las aristas tienen un peso o valor asignado. Este peso puede representar una distancia, costo o cualquier otra medida que se quiera modelar.
Grafo completo: Un grafo completo es aquel en el que todos los vértices están conectados con todos los demás vértices. Es decir, no hay vértices aislados en el grafo.
Grafo bipartito: Un grafo bipartito es aquel que se puede dividir en dos conjuntos de vértices disjuntos, de tal manera que todas las aristas conectan vértices de distintos conjuntos.
Representación
Representación estática
ℹ️
En la representacion estática el grafo se representa con una matriz en la que cada posición representa una arista, en un grafo no dirigido esta matriz es simétrica respecto de la diagonal principal. El elemento de dicha matriz puede ser un boolean para un grafo estatico o un integer / real para un grafo ponderado
⚠️
Hay que tener en cuenta que a la hora de construir el grafo, dicho grafo está contenido en en campo .info de in record el cual se base en otro campo .n para determinar cuantos nodos de la matriz están en uso y definir así una sub-matriz restringiendo el acceso a coordenadas fuera de los límites de la misma
Representación dinámica
Para representar un grafo mediante una estructura dinámica, cunstruiremos una lista de nodos los cuales representarán a los vértices del grafo (esta lista no representa ningún orden en sí) dichos nodos contendrá la información del elemento y una lista dinámica representando las aristas salientes de es nodo. En el elemento de dichas aristas contendrá información acerca de el nodo de destino y la ponderación de la misma
Recorridos
Recorrido en anchura
Recorrido en profundidad
Algoritmo para realizar un recorrido
📖
Para realizar un recorrido contaremos con las siguientes estructuras:
El grafo el cual vamos a recorrer
Una estructura lineal dependiendo de si lo vamos a recorrer en profundidad o anchura usaremos una pila o una cola respectivamente
Pila → Profundidad
Cola → Anchura
Un conjunto para llevar la cuenta de los nodo ya visitado
Una lista que será donde leeremos finalmente el resultado
Algoritmo
Añadimos el vertice de inicio a la estructura lineal (pila o cola)
Repetir hasta que la estructura lineal esté vacia
Sacamos un elemento de la estructura lineal
Comprobamos si está en el conjunto de vertices visitados
Si ya está, no hacemos nada
Si no está:
Lo añadimos al conjunto
Lo añadimos a la lista
Añadimos a la estructura lineal todos los vertices de sus aristas salientes según el criterio que se pida
