4.2. Representación de grafos.
Suponer que tenemos n nodos y a aristas.
- ¿Que implementación será mejor para las operaciones: calcular el grado de entrada o de salida, contar el número de aristas, insertar una arista?
- Si cada puntero ocupa k1 bytes y cada etiqueta de arista k2 bytes, ¿qué representación ocupará menos memoria?
Operaciones típicas sobre grafos:
- Crear un grafo vacío.
- Añadir, modificar o borrar un nodo o una arista de un grafo.
- Combinar dos grafos en uno nuevo.
- Construir un grafo a partir de otra estructura, p. ej. a partir de una expresión regular, o de una lista de carreteras entre ciudades.
- Consultar si entre dos nodos existe un arco, y la etiqueta asociada.
- Obtener el conjunto de nodos a los cuales se llega desde un nodo dado (o bien los nodos que llegan al nodo dado).
- Recorrer los nodos del grafo siguiendo las aristas en determinado orden.
- Comprobar si existen ciclos en el grafo, si existen caminos entre determinados nodos. Si el grafo tiene pesos calcular cuales son los caminos de menor costo total.
- Comprobar si dos grafos son iguales (isomorfos), o uno es subgrafo del otro.