Anteriormente mencionamos que existen dos maneras de represetar un grafo, en esta seccion vamos a agregar un poco mas de información acerca de sus tipos de representaciones, y dando un ejemplo.
MATRIZ DE ADYACENCIA
La matriz de adyacencia M es un array de dos dimensiones que representa las conexiones entre pares de vertices. Sea un grafo G con un conjunto de nodos V y de aristas A. Supongamos que el grafo es de orden N, en donde N > = 1. La matriz de adyacencia M se representa por un Array N, X > N donde:
1 si existe una arista (Vi, Vj) en Ao, Vi es adyacente a VjM(i,j) = 0, en caso contrario
Las columnas y las filas de la matriz representan los vertices del grafo . Si existe una arista desde i a j (esto es, el vertice i es adyacente a j), el peso de la arista de i a j se introduce: si no exite la arista , se introduce un 0; logicamente , los elementos de la diagonal principal son todos ceros , ya que el costo de la arista i a i es 0.
Si G es un grafo no dirigido , la matriz es simetrica M(i,j) = M(j,i).LISTA DE ADYACENCIA
El segundo metodo utilizado para representar un grafo es util cuando un grafo tiene muchos vertices y pocas aristas ; es la lista de adyacencia. En esta representacion se utiliza una lista enlazada por cada vertice V del grafo que tenga vertices adyacentes desde él.
El grafo completo incluye dos partes: un directorio y un conjunto de listas enlazadas . Hay una entrada en el directorio por cada nodo del grafo. La entrada en el directorio del nodo i apunta a una lista enlazada que representa los nodos que son conectados a i . Cada registro de la lista enlazada tiene dos campos : un identificador del nodo, otro es un enlace al siguiente elemento de la lista ; la lista enlazada representa arcos.
Un Ejemplo
Analisis del problema:
Se trata de una función recursiva que compara nodo a nodo la informacion almacenada en ambos árboles. Las condiciones de salida del proceso recursivo seran :
*Que se termine de recorrer uno de los dos arboles.
*Que terminen de recorrer ambos.
*Que encontremos diferente informacion en los nodos comparados.
Si los arboles terminaron de recorrerse simultaneamente es que ambos tienen el mismo número de nodos y nunca ha sido diferente la informacion comparada; por lo tanto, la funcion devolvera verdad ; en otro caso devolvera falso.
funcion iguales (E:punt; raiz1; raiz2)
inicio
si (raiz1 = nulo) Entonces
si (raiz2 = nulo) Entonces
devolver (verdad)
fin-si
si-no
si (raiz2 = nulo) Entonces
devolver (Falso)
si-no
si (raiz1----.elemento <> raiz2 ----.elemento) Entonces
devolver (Falso)
si-no
devolver (iguales (raiz1----.Izquierdo, raiz2----.Izquierdo))
(iguales (raiz1.----Derecho, raiz2------.Derecho))
fin-si
fin-si
fin.
No hay comentarios:
Publicar un comentario