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.
Teniendo un ejemplo base podemos tener un grafo G con 3 nodos y 2 aristas:
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:
Podemos establecer una matriz de adyacencia, donde cada fila de la fila representa la conexión del grafo en la columna [b].
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.
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.
Ahora que entendemos la lógica podemos seguir rellenando la fila.
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.
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.
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);
}
}
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] << " ";
}
}
}
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.
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:
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;
}
}
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";
}
}
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)