Ernesto Carrión

Hoy les voy a hablar un poco sobre la Teoría de Grafos, en esta pequeña introducción veremos básicamente 2 formas para representar grafos. Como ya sabemos un grafo se define como un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden poseer una dirección o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

No me detendré a explicar a fondo los tipos de grafos y todo lo que esto implica, supondré que todo esto ya lo sabes o puedes leerlo de wikipedia.

Matrices

Esta es la forma mas directa de representar un árbol siendo la fila (Nodo fuente) y la columna (Nodo destino). Es decir si tenemos una matriz 4×3 lo siguiente: grafo[2][1] = 3; significa que de el nodo 2 al nodo 1 puedo ir y esa arista posee un valor de 3.

Las ventajas de trabajar con matrices son muchas entre las cuales se destacan, la rapidez y la flexibilidad que tienen, se puede acceder, modificar, borrar muy fácilmente; pero su problema es el espacio, es la estructura que más espacio ocupa.

Arreglos de Vectores

Esta forma es un poco mas específica para un grafo (lo representa más claramente), principalmente se tiene un arreglo de tamaño N, siendo N el numero de nodos del grafo y en cada espacio del arreglo se tiene un vector que almacenara los nodos que puede alcanzar el nodo especificado por el arreglo.

Las ventajas son: Conceptualmente más claro, rapido acceso, y modificación, el vector hace todo el trabajo de la memoria dinámica (lo cual puede ser un fastidio en lenguajes como C/C++).

Las desventajas son: Inserción un poco mas lenta, borrado algo engorroso (C++), se hace obligatorio el uso de estructuras cuando trabajamos con grafos con peso (weighted graphs).

Ahora un pequeño código escrito en C++ que ejemplifica estos 2 metodos de representar grafos.

#include <iostream>
#include <vector>
#include <list>
#include <cstring>

#define MAXN 100  //Maximun numbers of nodes

//Matrix
int graph1[MAXN][MAXN];

//Array Vector
vector graph2[MAXN];

void fillMatrix(){

  //Initializate(Fill it with 0's)
  memset(graph1, 0, sizeof(int));

  //Direct Asignation
  //(Valid path from Node 2 to Node 3 with weight 5)
  graph1[2][3] = 5;

  //Direct Access
  cout << graph1[2][3] << endl;

}

void fillVector(){

  //Slower Asignation, no weight.
  //For weight push_back a custome struct
  graph2[2].push_back(3);

  //Direct Access
  cout << graph2[2][0] << endl;

}

int main(){

  fillMatrix();
  fillVector();

  return 0;
}

Disculpen si me he saltado muchas cosas, pero no estoy acostumbrado a hacer tutoriales, espero aprender en el camino