4.2. Representación de grafos.
Representación mediante matrices de adyacencia.
- El conjunto de aristas es representado mediante una matriz M[nodo, nodo] de booleanos, donde M[v, w]= 1 sí y sólo si (v, w) ? A.
- Si el grafo está etiquetado, la matriz será de elementos de ese tipo, por ejemplo, caracteres o enteros. Tomará un valor nulo si no existe ese arco.
- Si el grafo es no dirigido, M[v, w] = M[w, v]. La matriz es simétrica.
- Problemas.
- Si el número de nodos es muy grande y hay poca conectividad (pocos arcos, en relación al máximo posible) se desperdicia memoria.
- Debemos conocer los tamaños aproximados que van a tener los grafos.
- ¿Cómo se calcularía el grado de entrada o de salida de un nodo?