Estructura de datos: Grafos
El objetivo de este articulo es el de saber que son los “Grafos” en las estructuras de datos, sus formas de expresión, como buscar en un grafo y los algoritmos que se usan en ellos.
Los grafos son una estructura de datos no lineal parecida a la de los arboles, pero este seria un árbol sin las leyes de acomodo que rigen a un árbol normal.
Los grafos están conformados de nodos o también nombrados vértices los cuales son registros con datos y al menos un apuntador a otro nodo, y de aristas, las cuales son las conexiones que existen de un nodo a otro.
Existen dos tipo de grafos, los grafos dirigidos y los grafos no dirigidos.
Los grafos no dirigidos son como los que se muestran en la imagen anterior, son grafos que no cuentan con una dirección establecida de en que orden van las conexiones de un nodo a otro en los grafos, a su vez están los no dirigidos pero ponderados, que en estos se agrega un valor a las aristas y esto afecta al momento de conocer cual seria la ruta mas corta de un nodo a otro.
Mientra que los grafos dirigidos son los que se muestran en la primera imagen, son grafos en cuyas aristas se muestra la dirección en la que van las conexiones de los nodos, e igual que los no dirigidos, hay grafos dirigidos y ponderados, los cuales aparte de tener unas dirección las aristas también cuentan con un valor definido.
Los grafos se pueden representar de diferentes formas, una de ellas es en forma de matriz adyacente, en esta se asocian las filas y columnas a los nodos del grafo, mostrando en los elementos de la matriz si existe conexión del nodo con los demás, si es este el caso se pone 1 y si no existe conexión con ese nodo se pone 0.
int V,A;
int a[maxV][maxV];
void inicializar()
{
int i,x,y,p;
char v1,v2;
// Leer V y A
memset(a,0,sizeof(a));
for (i=1; i<=A; i++)
{
scanf("%c %c %d\n",&v1,&v2,&p);
x=v1-'A'; y=v2-'A';
a[x][y]=p; a[y][x]=p;
}
}La otra forma de representar un grafo es con una lista de adyacencia, en la cual se asocian los nodos del grafo a una lista, la cual contiene todos los nodos con los que es adyacente.
struct nodo
{
int v;
int p;
nodo *sig;
};
int V,A; // vértices y aristas del grafo
struct nodo *a[maxV], *z;
void inicializar()
{
int i,x,y,peso;
char v1,v2;
struct nodo *t;
z=(struct nodo *)malloc(sizeof(struct nodo));
z->sig=z;
for (i=0; i<V; i++)
a[i]=z;
for (i=0; i<A; i++)
{
scanf("%c %c %d\n",&v1,&v2,&peso);
x=v1-'A'; y=v2-'A';
t=(struct nodo *)malloc(sizeof(struct nodo));
t->v=y; t->p=peso; t->sig=a[x]; a[x]=t;
t=(struct nodo *)malloc(sizeof(struct nodo));
t->v=x; t->p=peso; t->sig=a[y]; a[y]=t;
}
}Para explorar los grafos se puede realizar con dos métodos, la búsqueda en profundidad y la búsqueda en amplitud.
La búsqueda por profundidad, se realiza mediante una función recursiva o con una pila, en la cual va recorriendo por completo toda una rama del árbol formado, y hasta terminar con esa recorre la siguiente.
int id=0;
int val[V];
void buscar()
{
int k;
for (k=1; k<=V; k++)
val[k]=0;
for (k=1; k<=V; k++)
if (val[k]==0) visitar(k);
}
void visitar(int k) // matriz de adyacencia
{
int t;
val[k]=++id;
for (t=1; t<=V; t++)
if (a[k][t] && val[t]==0) visitar(t);
}
void visitar(int k) // listas de adyacencia
{
struct nodo *t;
val[k]=++id;
for (t=a[k]; t!=z; t=t->sig)
if (val[t->v]==0) visitar(t->v);
}En la búsqueda por amplitud en vez de usar una pila se usa una cola, y esta va recorriendo por niveles el árbol.
struct tcola *cola;
void visitar(int k) // listas de adyacencia
{
struct nodo *t;
encolar(&cola,k);
while (!vacia(cola))
{
desencolar(&cola,&k);
val[k]=++id;
for (t=a[k]; t!=z; t=t->sig)
{
if (val[t->v]==0)
{
encolar(&cola,t->v);
val[t->v]=-1;
}
}
}
}En los grafos se utilizan algoritmos para lograr encontrar en ellos un árbol recubridror mínimo, y estos son los algoritmos de Prim y Kruskal.
El algoritmo Kruskal crea un conjunto de arboles, donde cada vértice es un árbol separado, se crea un conjunto con todas las aristas del grafo y mientras que ese conjunto no este vació se elimina la arista con menor peso, y si dicha arista conecta con dos arboles, estos se combinan en un solo árbol, y en caso contrario se elimina la arista.
#include <vector>
using namespace std;
class Grafo
{
public:
Grafo();
Grafo(int nodos);
vector<vector<int>> kruskal();
private:
const int INF = numeric_limits<int>::max();
int cn; //cantidad de nodos
vector<vector<int>> ady; //matriz de adyacencia
};
//**** Finaliza Archivo grafo.h *****//
//**** Comienza Archivo grafo.cpp *****//
Grafo::Grafo()
{
}
Grafo::Grafo(int nodos)
{
this->cn = nodos;
this->ady = vector<vector<int>>(cn);
for (int i = 0; i < cn; i++)
ady[i] = vector<int>(cn, INF);
}
// Declaraciones en el archivo .h
int cn; //cantidad de nodos
vector< vector<int> > ady; //matriz de adyacencia
// Devuelve la matriz de adyacencia del árbol mínimo.
vector< vector<int> > Grafo :: kruskal(){
vector< vector<int> > adyacencia = this->ady;
vector< vector<int> > arbol(cn);
vector<int> pertenece(cn); // indica a que árbol pertenece el nodo
for(int i = 0; i < cn; i++){
arbol[i] = vector<int> (cn, 0);
pertenece[i] = i;
}
int nodoA;
int nodoB;
int arcos = 1;
while(arcos < cn){
// Encontrar el arco mínimo que no forma ciclo y guardar los nodos y la distancia.
int min = INF;
for(int i = 0; i < cn; i++)
for(int j = 0; j < cn; j++)
if(min > adyacencia[i][j] && adyacencia[i][j]!=0 && pertenece[i] != pertenece[j]){
min = adyacencia[i][j];
nodoA = i;
nodoB = j;
}
// Si los nodos no pertenecen al mismo árbol agrego el arco al árbol mínimo.
if(pertenece[nodoA] != pertenece[nodoB]){
arbol[nodoA][nodoB] = min;
arbol[nodoB][nodoA] = min;
// Todos los nodos del árbol del nodoB ahora pertenecen al árbol del nodoA.
int temp = pertenece[nodoB];
pertenece[nodoB] = pertenece[nodoA];
for(int k = 0; k < cn; k++)
if(pertenece[k] == temp)
pertenece[k] = pertenece[nodoA];
arcos++;
}
}
return arbol;
}Y el algoritmo de Prim lo que hace es inicializa un árbol con un único vértice, se aumenta el árbol hacia solo un lado, que es la unión de dos vértices, se busca el lado con menor distancia y une los arboles, y esto se repite hasta que todos los vértices pertenezcan al árbol.
#include <vector>
using namespace std;
class Grafo
{
public:
Grafo();
Grafo(int nodos);
vector< vector<int> > prim();
private:
const int INF = numeric_limits<int>::max();
int cantidadNodos; //cantidad de nodos
vector< vector<int> > adyacencia; //matriz de adyacencia
};
//**** Finaliza Archivo grafo.h *****//
//**** Comienza Archivo grafo.cpp *****//
Grafo::Grafo()
{
}
Grafo::Grafo(int nodos)
{
this->cantidadNodos = nodos;
this->adyacencia = vector< vector<int> > (cantidadNodos);
for(int i = 0; i < cantidadNodos; i++)
adyacencia[i] = vector<int> (cantidadNodos, INF);
}
vector< vector<int> > Grafo :: prim(){
// uso una copia de adyacencia porque necesito eliminar columnas
vector< vector<int> > adyacencia = this->adyacencia;
vector< vector<int> > arbol(cantidadNodos);
vector<int> markedLines;
vector<int> :: iterator vectorIterator;
// Inicializo las distancias del arbol en INF.
for(int i = 0; i < cantidadNodos; i++)
arbol[i] = vector<int> (cantidadNodos, INF);
int padre = 0;
int hijo = 0;
while(markedLines.size() + 1 < cantidadNodos){
padre = hijo;
// Marco la fila y elimino la columna del nodo padre.
markedLines.push_back(padre);
for(int i = 0; i < cantidadNodos; i++)
adyacencia[i][padre] = INF;
// Encuentro la menor distancia entre las filas marcadas.
// El nodo padre es la linea marcada y el nodo hijo es la columna del minimo.
int min = INF;
for(vectorIterator = markedLines.begin(); vectorIterator != markedLines.end(); vectorIterator++)
for(int i = 0; i < cantidadNodos; i++)
if(min > adyacencia[*vectorIterator][i]){
min = adyacencia[*vectorIterator][i];
padre = *vectorIterator;
hijo = i;
}
arbol[padre][hijo] = min;
arbol[hijo][padre] = min;
}
return arbol;
}Referencias
ALGORITMIA ALGO+ — Algoritmos y Estructuras de Datos. (2020). Retrieved 22 November 2020, from http://www.algoritmia.net/articles.php?id=18
Algoritmo de Kruskal. (2020). Retrieved 22 November 2020, from https://es.wikipedia.org/wiki/Algoritmo_de_Kruskal
Algoritmo de Prim. (2020). Retrieved 22 November 2020, from https://es.wikipedia.org/wiki/Algoritmo_de_Prim#Código_en_C++
Estructuras de datos para la representación de grafos. (2020). Retrieved 22 November 2020, from http://programacion-estructuras-datos.blogspot.com/2010/12/estructuras-de-datos-para-la.html
Grafo (tipo de dato abstracto). (2020). Retrieved 22 November 2020, from https://es.wikipedia.org/wiki/Grafo_(tipo_de_dato_abstracto)
Grafos | Qué son, tipos, orden y herramientas de visualización. (2020). Retrieved 22 November 2020, from https://www.grapheverywhere.com/grafos-que-son-tipos-orden-y-herramientas-de-visualizacion/
