Grafos - Metodos de representación en computadora (Parte 2)

[vudduu]

Tal y como adelantamos en la Parte 1 ahora aprenderemos cómo representar los Grafos en código.

Matriz de Adyacencias

Con este método se tiene una matriz de tamaño $[n*n]$ donde n es el número de vértices o nodos en el Grafo.

Una forma simple de ver la información guardada en dicha matriz es que los renglones de las mismas representan el origen y las columnas el destino de cada arista o arco en el Grafo. Si el grafo es no ponderado se acostumbra poner un cero en la [fila $i$, columna $j$] de la matriz cuando no existe dicho arco y un uno cuando dicho arco existe en el Grafo. En el caso de grafos ponderados, se acostumbra poner una bandera (normalmente el valor de infinito) en las posiciones donde no existe un arco y el peso correspondiente en las posiciones donde sí existe.

Figura 1. Grafo No Ponderado y su Matriz de Adyacencias

---

Debe notarse que para un grafo no dirigido la Matriz de Adyacencia es simétrica y que la diagonal principal contiene ceros. Esto puede llegar a aprovecharse para ahorrar tiempo en algunos algoritmos. La representación por medio de matriz se prefiere para algoritmos donde el número de arcos es grande en proporción al número de vértices. Si sucediera lo contrario se prefiere la representación por medio de Listas de Adyacencia.

Figura 2. Digrafo Ponderado y su Matriz de Adyacencias

---

Codigo en C++ de la Figura 1

#include <iostream>
using namespace std;

int main() {
  int n = 5;
  int G[n][n];
  memset(G, 0, sizeof(G));
  G[0][1] = G[1][0] = 1;
  G[1][2] = G[2][1] = 1;
  G[3][2] = G[2][3] = 1;
  for (int i = 0; i < n ; i++) {
    for (int j = i + 1; j < n ; j++) {
      if (G[i][j]) {
        cout << i << " esta conectado con " << j << endl;
      }
    }
  }
}

Listas de Adyacencias

Para representar un Grafo mediante Listas de Adyacencias como su nombre lo indica se utiliza la estructura de datos de Listas enlazadas, para lo cual por cada vértice o nodo se crea una Lista donde se contiene a todos los vértices a los cuales podemos visitar a partir de este.

Figura 3. Digrafo y su Listas de Adyacencias

---

Codigo en C++ de la Figura 3

#include <iostream>
#include <vector>
#include <list>
using namespace std;

const int MAX_VERT = 5;
vector<list<int> > grafo(MAX_VERT);
bool visitado[MAX_VERT];

void inserta_arista(int i, int j){
  grafo[i].push_back(j);
}

void limpia_grafo() {
  for (int i = 0; i < MAX_VERT; i++) {
    visitado[i] = 0;
    grafo[i].clear();
  }
}

int main() {
  limpia_grafo();
  inserta_arista(0, 1);
  inserta_arista(0, 3);
  inserta_arista(1, 2);
  inserta_arista(1, 3);
  inserta_arista(2, 4);
  inserta_arista(3, 2);
  inserta_arista(3, 4);

  list<int>::iterator it;
  for (it = grafo[3].begin(); it != grafo[3].end() ;it++) {
    cout << "3 puede visitar a " << (*it) << endl;
  }
}

Si buscamos representar un Digrafo Ponderados utilizando Listas de Adyacencia sera necesario utilizar una lista de pares del tipo $G[v_i] = [(v_0, w_0), (v_1, w_1), ..., (v_j, w_j) ]$

En C++ esta lista se representaria con el siguiente código:

vector<list<pair<int, int> > > grafo(MAX_VERT);