Language: EN
LuisLlamas Logo
Search
⏲️ ~ 8 minutes Advanced
que-es-un-grafo

What are Graphs and How to Use Them

Un GRAPH is a mathematical data structure consisting of a set of vertices (also called nodes) and a set of edges (also called edges) that connect these vertices.

There are several ways to encode a GRAPH. But, conceptually, a graph is formed by a series of nodes.

Each of the nodes:

  • Has its own data “inside”
  • Has relationships with other nodes

The relationships between nodes are made by references. Together, that tangle of nodes and relationships form the GRAPH as a whole.

curso-programacion-grafo

Something like this, but not so crazy

The GRAPH are an elegant way to model relationships between objects. This structure is one of the most versatile and powerful. You’re going to find it everywhere.

For example, a graph could represent a social network, where the nodes are users and the edges denote friendships or connections. This way, you could recommend friends or content to users based on the graph.

Another example, a navigation system like Google Maps, where each node represents a location, and the possible relationships. path. You could find the shortest route using algorithms like Dijkstra.

Or, in a software development project, a graph could represent the dependencies between different modules or packages. This way you could find circular references, version conflicts, etc.

In summary, you’re going to find graphs everywhere, even in soup. In fact, other structures like trees or linked lists, are simplifications of graphs.

Components of a graph

  1. Nodes (vertices): They are individual elements in the graph. Each vertex can represent entities such as people, places, or any object we are modeling.

grafo-nodo

A node of a graph

  1. Relationships (edges): They are the connections between the vertices. These edges can be directional or non-directional, depending on the type of relationship we want to represent.

  2. Adjacent node: Nodes that share a relationship with the current node are called adjacent nodes.

  3. Parents and children: When the nodes are oriented, the nodes with incoming and outgoing relationships are called parents or children.

Types of Graphs

  1. Undirected Graph: In this type of graph, the edges have no direction. The relationship between two vertices is bidirectional. If A is connected to B, then B is also connected to A.

grafo-no-dirigido

  1. Directed Graph: In a directed graph, the edges have direction. The relationship between two vertices can be unidirectional. For example, in a road graph, a road can go from A to B but not necessarily from B to A.

grafo-dirigido

  1. Weighted Graph: In addition to having edges and vertices, a weighted graph assigns a numerical weight to each edge. These weights can represent the cost, distance, or any other metric relevant to the particular application.

Graph terminology

  • Degree of a node: The degree of a node in a graph is the number of edges incident on that node.

  • Path: A path in a graph is a sequence of nodes connected by edges, where each node in the sequence is connected to the next by an edge.

  • Cycle: A cycle in a graph is a path that starts and ends at the same node and does not repeat any intermediate node (except the starting/ending node).

grafo-ciclo

Cycle in a graph

  • Connected Graph: A graph is connected if there is a path between every pair of nodes in the graph. This means that you can reach from any node to any other node in the graph by a sequence of edges.

grafos-conexos

Non-connected graph

  • Acyclic Graph: An acyclic graph is a graph that contains no cycles. In other words, there are no closed paths in the graph.

  • Complete Graph: A complete graph is a graph in which each pair of nodes is connected by an edge. This means that there are no isolated nodes in the graph and that each node is directly connected to all other nodes in the graph.

Example of Graphs in Different Languages

Graphs are essential for solving a variety of problems in programming, such as finding the shortest path between two points, detecting cycles in a system, or modeling complex relationships.

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.")

On this page