Un GRAFO es una estructura de datos matemática que consta de un conjunto de vértices (también llamados nodos) y un conjunto de aristas (también llamadas bordes) que conectan estos vértices.
Existen varias formas de codificar un GRAFO. Pero, conceptualmente, un grafo está formado por una serie de nodos.
Cada uno de los nodos:
- Tiene “dentro” sus propios datos
- Tiene relaciones con otros nodos
Las relaciones entre nodos se realizan entre mediante referencias. Juntos, esa maraña de nodos y relaciones, forman el GRAFO en su conjunto.
Los GRAFO son una forma elegante de modelar relaciones entre objetos. Esta estructura es una de las más versátil y potente. La vais a encontrar en todos los lados.
Por ejemplo, un grafo podría representar una red social, donde los nodos son usuarios y las aristas denotan amistades o conexiones. De esta forma, podrías recomendar amigos o contenido a los usuarios basados en el grafo.
Otro ejemplo, un sistema de navegación como Google Maps, donde cada nodo representa una ubicación, y las relaciones posibles. camino. Podrías encontrar la ruta más corta utilizando algoritmos como Dijkstra.
O, en un proyecto de desarrollo de software, un grafo podría representar las dependencias entre diferentes módulos o paquetes. De esta forma podrías encontrar referencias circulares, conflictos de versiones, etc.
En resumen, que los grafos los vais a encontrar hasta en la sopa. De hecho, otras estructuras como los árboles o las linkedlist, son simplificaciones de los grafos.
Componentes de un grafo
- Nodos (vértices): Son elementos individuales en el grafo. Cada vértice puede representar entidades como personas, lugares, o cualquier objeto que estemos modelando.
Relaciones (aristas): Son las conexiones entre los vértices. Estas aristas pueden ser direccionales o no direccionales, dependiendo del tipo de relación que queremos representar.
Nodo adyacente: A los nodos que comparten una relación con el nodo actual se les denomina nodos adyacentes.
Padres e hijos: Cunando los nodos son orientados, a los nodos con relaciones entrantes y salientes se les denomina padres, o hijos.
Tipos de Grafos
- Grafo No Dirigido: En este tipo de grafo, las aristas no tienen dirección. La relación entre dos vértices es bidireccional. Si A está conectado con B, entonces B también está conectado con A.
- Grafo Dirigido: En un grafo dirigido, las aristas tienen dirección. La relación entre dos vértices puede ser unidireccional. Por ejemplo, en un grafo de rutas, una carretera puede ir de A a B pero no necesariamente de B a A.
- Grafo Ponderado: Además de tener aristas y vértices, un grafo ponderado asigna un peso numérico a cada arista. Estos pesos pueden representar el costo, distancia, o cualquier otra métrica relevante para la aplicación en particular.
Terminología de grafos
Grado de un nodo: El grado de un nodo en un grafo es el número de aristas incidentes en ese nodo.
Camino: Un camino en un grafo es una secuencia de nodos conectados por aristas, donde cada nodo en la secuencia está conectado al siguiente mediante una arista.
Ciclo: Un ciclo en un grafo es un camino que comienza y termina en el mismo nodo, y que no repite ningún nodo intermedio (excepto el nodo de inicio/final).
- Grafo conexo: Un grafo es conexo si existe un camino entre cada par de nodos en el grafo. Esto significa que se puede llegar desde cualquier nodo a cualquier otro nodo del grafo mediante una secuencia de aristas.
Grafo acíclico: Un grafo acíclico es un grafo que no contiene ningún ciclo. En otras palabras, no hay ningún camino cerrado en el grafo.
Grafo completo: Un grafo completo es un grafo en el que cada par de nodos está conectado por una arista. Esto significa que no hay nodos aislados en el grafo y que cada nodo está conectado directamente a todos los demás nodos del grafo.
Ejemplo de Grafos en diferentes lenguajes
Los grafos son esenciales para resolver una variedad de problemas en programación, como encontrar la ruta más corta entre dos puntos, detectar ciclos en un sistema, o modelar relaciones complejas.
using System;
using System.Collections.Generic;
public class Nodo
{
public string Valor { get; set; }
public List<Nodo> Padres { get; set; }
public List<Nodo> Hijos { get; set; }
public Nodo(string valor)
{
Valor = valor;
Padres = new List<Nodo>();
Hijos = new List<Nodo>();
}
public void AgregarPadre(Nodo padre)
{
Padres.Add(padre);
}
public void AgregarHijo(Nodo hijo)
{
Hijos.Add(hijo);
}
}
public class Grafo
{
private Dictionary<string, Nodo> Nodos { get; set; }
public Grafo()
{
Nodos = new Dictionary<string, Nodo>();
}
public void AgregarNodo(string valor)
{
if (!Nodos.ContainsKey(valor))
{
Nodos[valor] = new Nodo(valor);
}
}
public void AgregarArista(string padreValor, string hijoValor)
{
AgregarNodo(padreValor);
AgregarNodo(hijoValor);
Nodo padre = Nodos[padreValor];
Nodo hijo = Nodos[hijoValor];
padre.AgregarHijo(hijo);
hijo.AgregarPadre(padre);
}
public Nodo ObtenerNodo(string valor)
{
if (Nodos.ContainsKey(valor))
{
return Nodos[valor];
}
else
{
return null;
}
}
public void ImprimirGrafo()
{
foreach (var kvp in Nodos)
{
Nodo nodo = kvp.Value;
string padres = string.Join(", ", nodo.Padres.ConvertAll(n => n.Valor));
string hijos = string.Join(", ", nodo.Hijos.ConvertAll(n => n.Valor));
Console.WriteLine($"Nodo: {nodo.Valor}, Padres: [{padres}], Hijos: [{hijos}]");
}
}
}
class Program
{
static void Main(string[] args)
{
Grafo miGrafo = new Grafo();
miGrafo.AgregarArista("A", "B");
miGrafo.AgregarArista("A", "C");
miGrafo.AgregarArista("B", "D");
miGrafo.AgregarArista("C", "D");
miGrafo.AgregarArista("D", "E");
miGrafo.AgregarArista("E", "F");
miGrafo.AgregarArista("F", "G");
Console.WriteLine("Grafo:");
miGrafo.ImprimirGrafo();
Nodo nodoC = miGrafo.ObtenerNodo("C");
if (nodoC != null)
{
Console.WriteLine($"\nNodo 'C' tiene como padres: {string.Join(", ", nodoC.Padres.ConvertAll(n => n.Valor))}");
Console.WriteLine($"Nodo 'C' tiene como hijos: {string.Join(", ", nodoC.Hijos.ConvertAll(n => n.Valor))}");
}
else
{
Console.WriteLine("\nEl nodo 'C' no existe en el grafo.");
}
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
class Nodo {
public:
std::string valor;
std::vector<Nodo*> padres;
std::vector<Nodo*> hijos;
Nodo(std::string val) : valor(val) {}
void agregarPadre(Nodo* padre) {
padres.push_back(padre);
}
void agregarHijo(Nodo* hijo) {
hijos.push_back(hijo);
}
};
class Grafo {
private:
std::unordered_map<std::string, Nodo*> nodos;
public:
void agregarNodo(std::string valor) {
if (nodos.find(valor) == nodos.end()) {
nodos[valor] = new Nodo(valor);
}
}
void agregarArista(std::string padreValor, std::string hijoValor) {
agregarNodo(padreValor);
agregarNodo(hijoValor);
Nodo* padre = nodos[padreValor];
Nodo* hijo = nodos[hijoValor];
padre->agregarHijo(hijo);
hijo->agregarPadre(padre);
}
Nodo* obtenerNodo(std::string valor) {
if (nodos.find(valor) != nodos.end()) {
return nodos[valor];
}
return nullptr;
}
void imprimirGrafo() {
for (auto& kvp : nodos) {
Nodo* nodo = kvp.second;
std::cout << "Nodo: " << nodo->valor << ", Padres: [";
for (auto& padre : nodo->padres) {
std::cout << padre->valor << " ";
}
std::cout << "], Hijos: [";
for (auto& hijo : nodo->hijos) {
std::cout << hijo->valor << " ";
}
std::cout << "]" << std::endl;
}
}
~Grafo() {
for (auto& kvp : nodos) {
delete kvp.second;
}
}
};
int main() {
Grafo miGrafo;
miGrafo.agregarArista("A", "B");
miGrafo.agregarArista("A", "C");
miGrafo.agregarArista("B", "D");
miGrafo.agregarArista("C", "D");
miGrafo.agregarArista("D", "E");
miGrafo.agregarArista("E", "F");
miGrafo.agregarArista("F", "G");
std::cout << "Grafo:" << std::endl;
miGrafo.imprimirGrafo();
Nodo* nodoC = miGrafo.obtenerNodo("C");
if (nodoC != nullptr) {
std::cout << "\nNodo 'C' tiene como padres: ";
for (auto& padre : nodoC->padres) {
std::cout << padre->valor << " ";
}
std::cout << "\nNodo 'C' tiene como hijos: ";
for (auto& hijo : nodoC->hijos) {
std::cout << hijo->valor << " ";
}
std::cout << std::endl;
} else {
std::cout << "\nEl nodo 'C' no existe en el grafo." << std::endl;
}
return 0;
}class Nodo {
constructor(valor) {
this.valor = valor;
this.padres = [];
this.hijos = [];
}
agregarPadre(padre) {
this.padres.push(padre);
}
agregarHijo(hijo) {
this.hijos.push(hijo);
}
}
class Grafo {
constructor() {
this.nodos = {};
}
agregarNodo(valor) {
if (!this.nodos[valor]) {
this.nodos[valor] = new Nodo(valor);
}
}
agregarArista(padreValor, hijoValor) {
this.agregarNodo(padreValor);
this.agregarNodo(hijoValor);
const padre = this.nodos[padreValor];
const hijo = this.nodos[hijoValor];
padre.agregarHijo(hijo);
hijo.agregarPadre(padre);
}
obtenerNodo(valor) {
return this.nodos[valor] || null;
}
imprimirGrafo() {
for (const valor in this.nodos) {
const nodo = this.nodos[valor];
const padres = nodo.padres.map(padre => padre.valor).join(", ");
const hijos = nodo.hijos.map(hijo => hijo.valor).join(", ");
console.log(`Nodo: ${nodo.valor}, Padres: [${padres}], Hijos: [${hijos}]`);
}
}
}
// Creando un grafo y agregando nodos y aristas
const miGrafo = new Grafo();
miGrafo.agregarArista("A", "B");
miGrafo.agregarArista("A", "C");
miGrafo.agregarArista("B", "D");
miGrafo.agregarArista("C", "D");
miGrafo.agregarArista("D", "E");
miGrafo.agregarArista("E", "F");
miGrafo.agregarArista("F", "G");
console.log("Grafo:");
miGrafo.imprimirGrafo();
const nodoC = miGrafo.obtenerNodo("C");
if (nodoC) {
console.log(`\nNodo 'C' tiene como padres: ${nodoC.padres.map(padre => padre.valor).join(", ")}`);
console.log(`Nodo 'C' tiene como hijos: ${nodoC.hijos.map(hijo => hijo.valor).join(", ")}`);
} else {
console.log("\nEl nodo 'C' no existe en el grafo.");
}
class Nodo:
def __init__(self, valor):
self.valor = valor
self.padres = []
self.hijos = []
def agregar_padre(self, padre):
self.padres.append(padre)
def agregar_hijo(self, hijo):
self.hijos.append(hijo)
class Grafo:
def __init__(self):
self.nodos = {}
def agregar_nodo(self, valor):
nuevo_nodo = Nodo(valor)
self.nodos[valor] = nuevo_nodo
return nuevo_nodo
def agregar_arista(self, padre, hijo):
if padre not in self.nodos:
self.agregar_nodo(padre)
if hijo not in self.nodos:
self.agregar_nodo(hijo)
self.nodos[padre].agregar_hijo(hijo)
self.nodos[hijo].agregar_padre(padre)
def obtener_nodo(self, valor):
if valor in self.nodos:
return self.nodos[valor]
else:
return None
def imprimir_grafo(self):
for valor, nodo in self.nodos.items():
padres = ', '.join(nodo.padres)
hijos = ', '.join(nodo.hijos)
print(f"Nodo: {valor}, Padres: [{padres}], Hijos: [{hijos}]")
# Creando un grafo y agregando nodos y aristas
mi_grafo = Grafo()
mi_grafo.agregar_arista('A', 'B')
mi_grafo.agregar_arista('A', 'C')
mi_grafo.agregar_arista('B', 'D')
mi_grafo.agregar_arista('C', 'D')
mi_grafo.agregar_arista('D', 'E')
mi_grafo.agregar_arista('E', 'F')
mi_grafo.agregar_arista('F', 'G')
# Imprimiendo el grafo
print("Grafo:")
mi_grafo.imprimir_grafo()
# Accediendo a un nodo específico
nodo_c = mi_grafo.obtener_nodo('C')
if nodo_c:
print("\nNodo 'C' tiene como padres:", nodo_c.padres)
print("Nodo 'C' tiene como hijos:", nodo_c.hijos)
else:
print("\nEl nodo 'C' no existe en el grafo.")