DEV Community

Greedyboy
Greedyboy

Posted on

¿Cómo implementar grafos en C++?

Hola, tiempo sin pasar por acá, en este post te enseñaré como representar un grafo en el lenguaje de programación de C++.

Para empezar, necesitamos saber que es un grafo.

¿Qué es un grafo?

Un grafo, es una estructura matemática que permite modelar problemas de la vida cotidiana, mediante, como hemos visto, una representación gráfica formada por nodos o vértices.

Fuente : https://www.inesem.es/revistadigital/informatica-y-tics/teoria-grafos/#:~:text=Un%20grafo,%20es%20una%20estructura,o%20relaciones%20entre%20los%20actores.

Teniendo un ejemplo base podemos tener un grafo G con 3 nodos y 2 aristas:

Image description

En este tenemos los nodos 1, 2 y 3. Y las aristas que conectan el nodo 1 con el nodo 2, y la arista que conecta el nodo 2 con el nodo 3.

Bueno, ahora que tenemos una noción básica de qué es un grafo, veremos como implementar uno en el lenguaje de programación de C++. Para ello, tenemos que conocer dos de sus representaciones.

Todos los ejemplos para este artículo serán basados en un grafo bidireccional

Matriz de Adyacencia

Una matriz de adyacencia es una estructura matemática utilizada para representar un grafo. Es una cuadrícula sencilla cuyos índices siempre son 0, o 1. Esto dependerá si es que el nodo en la posición [a] de la matriz, tiene una conexión con [b].

Siguiendo el ejemplo del grafo anterior:

Image description

Podemos establecer una matriz de adyacencia, donde cada fila de la fila representa la conexión del grafo en la columna [b].

Image description

En este caso, rellenaremos la matriz. Para ende debemos seguir la siguiente lógica, debemos revisar si es que hay una conexión entre el nodo de la fila actual y el nodo de la columna actual.
Por ejemplo, podemos partir con la primera posición de la matriz. El nodo 1.

Image description

En este caso, partiendo en la primera posición, revisamos en el grafo si es que el nodo 1 tiene una conexión con el nodo 1. En este caso no es así, ya que el nodo 1 no se conecta con sí mismo. Por ende ponemos un 0.

Image description

Ahora que entendemos la lógica podemos seguir rellenando la fila.

Image description

En este caso, en la fila del nodo 1 y la columna del nodo 2, hay un número 1. Porque el grafo tiene una conexión efectivamente con el nodo 2.

Image description

Y en este caso en la fila del nodo 1 y la columna del nodo 3 hay un número 0, porque el nodo 1 no tiene conexión con el nodo 3.

Siguiendo esta lógica podemos rellenar la matriz.

Image description

Una vez llenada la matriz, podemos hacer comprobaciones, por ejemplo si nos preguntan si es que el nodo 1 tiene una conexión con el 3, simplemente hay que acceder a la posición matriz[1][3], y si esa posición es un 1, es porque hay una conexión.

Ahora que ya vimos como funciona y la parte teórica, pasaremos a la explicación con código.

Implementación con Código

La implementación base de una matriz de adyacencia es la siguiente:



#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>matriz //Definimos la matriz

//Creamos una función que inicialize la matriz con n nodos.
void crearMatriz(int n){
   for(int i = 0; i < n; i++){
      vector<vector<int>>row(n, 0);
      matriz.push_back(row);
   }
}

//Creamos una función que agregue una conexión entre nodos.
void anadirConexion(int a, int b){
   matriz[a][b] = 1;
   matriz[b][a] = 1;
}

int main(){
   int n; // Cantidad de nodos del grafo
   cin >> n;
   crearMatriz(n); // Se llama a la función crear matriz con n
   int q; // Cantidad de aristas
   while(q--){ // Se ingresas las q aristas entre un nodo a y b
      int a, b;
      cin >> a >> b;
      anadirConexion(a, b);
   }
}


Enter fullscreen mode Exit fullscreen mode

Si quisieramos ver como queda la matriz podríamos añadir esta pequeña función al programa



void imprimirMatriz(vector<vector<int>>matriz){
   for(int i = 0; i < matriz.size(); i++){
      for(int j = 0; j < matriz.size(); j++){
         cout << matriz[i][j] << " ";
      }
   }
}


Enter fullscreen mode Exit fullscreen mode

Ahora que ya hemos visto como funciona la matriz de adyacencia, pasaremos a la otra implementación para un grafo.

Lista de Adyacencia

Una lista de adjacencia es un tipo de estructura de datos que se usaría para representar un grafo. Consiste en una lista de vértices adyacentes para cada vértice en cuestión.

Image description

Para este ejemplo seguiremos usando el grafo G de los ejemplos anteriores.

En palabras sencillas, una lista de adyacencia, es una lista interna para cada nodo n del grafo, y en dicha lista estarán los nodos con los que n tiene una conexión.

Por ejemplo:

Image description

En esta imagen vemos que el nodo 1, 2 y 3, tienen una lista respectiva. Tomemos como ejemplo el nodo 2, este nodo, posee una lista con los valores [1 y 3] esto quiere decir que el nodo 2 posee una conexión con el nodo 1 y el nodo 3, ésta afirmación es cierta si es que lo revisamos en el grafo.

Ahora pasaremos a su implementación en C++.

Implementacion Lista de Adyancencia C++

Para implementar una lista de adyacencia, utilizaremos el siguiente código:



#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>adjList; // Definición de la lista

void crearLista(int n){ // Se crea una lista de adyacencia con n nodos
    for(int i = 0; i < n; i++){
        vector<int>nodo = {};
        adjList.push_back(nodo);
    }
}

void agregarVecino(int a, int b){ // Función usada para agregar un vecino
    adjList[a].push_back(b);
    adjList[b].push_back(a);
}

int main(){
    int n; 
    cin >> n; // Se ingresa la cantidad de nodos del grafo
    crearLista(n);  // Se crea la lista de adyacencia
    int q;
    cin >> q; // Cantidad de conexiones 
    while(q--){
        int a, b;
        cin >> a >> b;
        agregarVecino(a, b); // Se agrega una conexión entre a y b;
    }
}



Enter fullscreen mode Exit fullscreen mode

Y si queremos mostrar la lista y las conexiones de cada nodo, debemos utilizar la siguiente función:



void imprimirLista(){
    for(int i = 0; i < adjList.size(); i++){
        cout << "Nodo " << i << ": ";
        for(int j = 0; i < adjList[i].size(); j++){
            cout << adjList[i][j] << " ";
        }
        cout << "\n";
    }
}


Enter fullscreen mode Exit fullscreen mode

Eso es!, Con eso ya podemos implementar un grafo en C++.

Espero que este post le sea de utilidad a una persona al menos, muchas gracias por leer si es que llegaste hasta acá.

Prontamente más artículos!

Top comments (0)