GRAFO LISTA ADYACENCIAS 312

Vista previa del material en texto

GRAFOS 
IMPLEMENTACIÓN DE GRAFOS: 
LISTA DE ADYACENCIAS
LISTA DE ADYACENCIAS
En una lista de adyacencias, a cada vértice i se le asocia una lista enlazada con todos los vértices j adyacentes a i.
El grafo se representa por medio de una lista enlazada de n componentes, (n = número de vértices del grafo) donde cada componente constituye la lista de adyacencias correspondiente a cada vértice del grafo. 
Cada nodo de la lista consta de un campo indicando el vértice adyacente.
Si el grafo fuese etiquetado o valorado, habría que añadir un segundo campo para mostrar el valor de la etiqueta o el peso de la arista. 
Ejemplo
Ejemplo
2
3
2
NULL
4
1
2
3
4
graf
1
NULL
NULL
NULL
NULL
Clase Nodo de vértices de la Lista de Adyascencias
class NodoG{
 int datox;
 NodoG sigx;
 Nodo vec;
public NodoG()
 { datox=0; sigx=null; vec=null; }
public NodoG(int d)
 { datox=d; sigx=null; vec=null; }
 }
10
NULL
 vec datox sigx
NULL
Clase Nodo de la Lista de vecinos
class Nodo{
 int dato;
 Nodo sig;
public Nodo()
 { dato=0; sig=null; }
public Nodo(int d)
 { dato=d; sig=null; }
 }
 10
 dato sig
NULL
Clase Grafo
 Grafo
 graf
 constructor
 grafoVacio()
 insertar(x)
 insertarVec(qv,int)
 localiza(db)
Clase Grafo
// CLASE GRAFO
class GrafoL {
// CAMPOS
 NodoG graf;
// CONSTRUCTOR
 public GrafoL()
 { graf=null;}
// VERIFICA SI EL GRAFO ESTA VACIO
 public boolean grafoVacio()
 { return graf==null;}
Clase Grafo
// INSERTAR UN VERTICE A LA LISTA DE ADYACENCIAS
 public void insertar(int x)
 { NodoG nuevo=new NodoG(x);
 if(grafoVacio()) graf=nuevo;
	 else { // inserta al final
 NodoG p=graf;
 while(p.sigx!=null) { p=p.sigx; }
	 p.sigx=nuevo;
 }
 int dt;
 System.out.print("No. vecinos=");
 int mv=Leer.datoInt(); 
 for(int i=1; i<=mv;++i)
 { System.out.print("dato de vecino "+i+"=");
 dt=Leer.datoInt();
 nuevo.vec=insertarVec(nuevo.vec,dt);
 }
}
Clase Grafo
// INSERTAR LA LISTA DE VECINOS DEL VERTICE
public Nodo insertarVec(Nodo qv,int y)
{ Nodo novo=new Nodo(y);
 if(qv==null) qv=novo;
 else { // inserta al final
	 Nodo p=qv;
 	 while(p.sig!=null) { p=p.sig; } 
	 p.sig=novo;
	 }
 return qv;
}
// LOCALIZAR UN NODO EN EL GRAFO
public NodoG localiza(int db)
{ NodoG p=graf;
 while(p!=null && p.datox!=db) { p=p.sigx; } 
 return p;
} }
Clase Operaciones
class Operaciones {
// INSERTAR N NODOS A LA LISTA DE ADYACENCIAS
public GrafoL insertarN(GrafoL g)
{ System.out.print("No. vertices=");
 int n=Leer.datoInt();
 int dt;
 for(int i=1; i<=n;++i)
 { System.out.print("dato "+i+"=");
 dt=Leer.datoInt();
 g.insertar(dt);
 }
 return g;
 }
Clase Operaciones
// MOSTRAR LA LISTA DE ADYACENCIA
public void mostrarListaAdy(GrafoL g)
{ NodoG p=g.graf;
 Nodo q;
 while(p!=null) { // Recorre la lista de adyacencia
 System.out.println("dato= "+p.datox);
 q=p.vec;
 while(q!=null) { // Recorre lista de vecinos
 System.out.println("dato de vecino= "+q.dato);
 q=q.sig;
 }
 p=p.sigx;
 }
 }
}
RECORRIDO DE GRAFOS
Los recorridos que se utilizan con mayor frecuencia son:
Recorrido por niveles, horizontal o en anchura
Recorrido en profundidad o vertical
En ambos casos se parte de un vértice o nodo inicial y se visitan todos los vértices o nodos del grafo, una sola vez cada uno, siguiendo una secuencia predeterminada: por niveles o en profundidad.
Se debe representar el grafo por niveles:
En el nivel 0 vértice o nodo inicial
En el nivel 1 los vecinos del vértice inicial
En el nivel 2 los vecinos de los vértices del nivel 1
Y sucesivamente
RECORRIDO DE GRAFOS
Tomamos como ejemplo el problema del Laberinto.
Desde la entrada (vértice inicial) hay que recorrer el grafo hasta llegar a la salida (vértice objetivo)
RECORRIDO DE GRAFOS
Ordenamos el grafo, colocando la entrada (vértice inicial) en el nivel 0, su vecino en el nivel 1 y sucesivamente.
RECORRIDO DE GRAFOS
Denominamos a cada nodo con una letra y obtenemos:
 nivel 0
 nivel 1
 nivel 2
 nivel 3
 nivel 4
S
B
D
E
I
C
G
F
J
A
RECORRIDO DE GRAFOS
Para cada vértice obtenemos sus vecinos (partiendo del predecesor más a la izquierda y continuando en sentido contrario al giro de las agujas del reloj.
	NODO	ESTADO	VECINOS
	S	[1 , 1]	[ A ]
	A	[2 , 3]	[ S , B , C ]
	B	[2 , 4]	[ A , D , E ]
	C	[2 , 2]	[ A , F , I ]
	D	[1 , 4]	[ B ]
	J	[3 , 4]	[ E , I , F ]
	E	[3 , 2]	[ B , G , J ]
	F	[3 , 1]	[ C , J , I ]
	G	[4 , 4]	[ E ]
	I	[3 , 3]	[ C , F , J ]
RECORRIDO HORIZONTAL O POR NIVELES
Se visita el nivel 0 (vértice inicial). 
Luego se visita el nivel 1(de izquierda a derecha). 
Se continúa nivel por nivel (en cada nivel de izquierda a derecha) hasta visitar vértices los nodos o llegar al objetivo.
En el algoritmo:
N es el vértice que está siendo visitado
ABIERTOS es la lista de vértices habilitados para ser visitados
CERRADOS es la lista de vértices ya visitados
RECORRIDO HORIZONTAL O POR NIVELES
ALGORITMO
1. Hacer ABIERTOS una lista inicial que contiene al nodo inicial 
2. Hacer CERRADOS una lista vacía
3. WHILE ABIERTOS no es vacía DO
4. Hacer N igual al primero de ABIERTOS
5. Insertar N al final de Cerrados
6. WHEN N es el nodo objetivo RETURN CERRADOS
7. Eliminar N de ABIERTOS
8. EXPANDIR (N); obtener la lista de nodos vecinos de N
Los nodos vecinos de N que previamente no estén en abiertos ni cerrados se insertan al final de ABIERTOS
END-WHILE
mostrar CERRADOS
END
RECORRIDO HORIZONTAL O POR NIVELES
Seguimiento al recorrido horizontal aplicado al grafo del Laberinto
	N	ABIERTOS	CERRADOS	EXPANDIR (N)
	 	(S)	()	 
	S	()	(S)	( A )
	 	(A)	 	 
	A	()	( S A )	( S B C )
	 	(B C)	 	 
	B	( C)	(S A B )	( A D E )
	 	( C D E )	 	 
	C	( D E )	( S A B C )	( A F I )
	 	( D E F I )	 	 
	D	( E F I )	(S A B C D )	( B )
	 	( E F I )	 	 
	E	( F I ) 	( S A B C D E)	( B G J ) 
		( F I G J )		
	F	( I G J )	( S A B C D E)	( C J I )
		( I G J )		
	I	( G J )	( S A B C D E I)	( C F J )
		( G J )		
	G	( J ) 	( S A B C D E I G)	
RECORRIDO DE GRAFOS
Gráficamente el recorrido por niveles o en anchura:
 nivel 0
 nivel 1
 nivel 2
 nivel 3
 nivel 4
S
B
D
E
I
C
G
F
J
A
RECORRIDO HORIZONTAL
En la clase Operaciones se incluye el método para recorrido horizontal.
Requiere utilizar la clase Cola, para implementar las listas ABIERTOS Y CERRADOS.
Para el paso 9 del algoritmo: 
Los nodos vecinos de N que previamente no estén en abiertos ni cerrados se insertan al final de ABIERTOS
Se incluye un método pertenece en la cola, que devuelve verdadero si un elemento pertenece a la cola y falso en caso contrario.
Se implementa para el grafo con vértices con dato int, visto anteriormente.
RECORRIDO HORIZONTAL
// BUSQUEDA HORIZONTAL EN EL GRAFO
public void horizontal(GrafoL g, int vin) {
NodoG r;
Nodo p = null;
int N;
OperCola opc = new OperCola();
Cola CERR = new Cola();
Cola ABI = new Cola();
ABI.insertar(vin);
while (!ABI.colaVacia()) { N = ABI.ver();
			 CERR.insertar(N);
			 ABI.eliminar();
			 r = g.localiza(N);
			 if (r != null) { p = r.vec; }
			while (p != null) {
		if (!opc.pertenece(ABI, p.dato) && !opc.pertenece(CERR, p.dato))
					 ABI.insertar(p.dato);
				 p = p.sig;
			 }
		 }
		opc.mostrar(CERR);
}
RECORRIDO VERTICAL O EN PROFUNDIDAD
Partiendo del vértice inicial, se visita la rama más a la izquierda, hasta llegar al vértice hoja.
Luego se visitan las ramas una por una, de izquierda a derecha.
Cada vértice se visita una sola vez.
RECORRIDO VERTICAL O EN PROFUNDIDADALGORITMO
1. Hacer ABIERTOS una lista inicial que contiene al nodo inicial 
2. Hacer CERRADOS una lista vacía
3. WHILE ABIERTOS no es vacía DO
4. Hacer N igual al primero de ABIERTOS
5. Insertar N al final de Cerrados
6. WHEN N es el nodo objetivo RETURN CERRADOS
7. Eliminar N de ABIERTOS
8. EXPANDIR (N); obtener la lista de nodos vecinos de N
Los nodos vecinos de N que previamente no estén en abiertos ni cerrados se insertan al principio de ABIERTOS
END-WHILE
mostrar CERRADOS
END
RECORRIDO DE GRAFOS
Denominamos a cada nodo con una letra y obtenemos:
 nivel 0
 nivel 1
 nivel 2
 nivel 3
 nivel 4
S
B
D
E
I
C
G
F
J
A
RECORRIDO DE GRAFOS
Para cada vértice obtenemos sus vecinos (partiendo del predecesor más a la izquierda y continuando en sentido contrario al giro de las agujas del reloj.
	NODO	ESTADO	VECINOS
	S	[1 , 1]	[ A ]
	A	[2 , 3]	[ S , B , C ]
	B	[2 , 4]	[ A , D , E ]
	C	[2 , 2]	[ A , F , I ]
	D	[1 , 4]	[ B ]
	J	[3 , 4]	[ E , I , F ]
	E	[3 , 2]	[ B , G , J ]
	F	[3 , 1]	[ C , J , I ]
	G	[4 , 4]	[ E ]
	I	[3 , 3]	[ C , F , J ]
RECORRIDO VERTICAL O EN PROFUNDIDAD
Seguimiento al recorrido vertical en el grafo del Laberinto
	N	ABIERTOS	CERRADOS	EXPANDIR (N)
	 	(S)	()	 
	S	()	(S)	( A )
	 	(A)	 	 
	A	()	( S A )	( S B C )
	 	(B C)	 	 
	B	( C)	(S A B )	( A D E )
	 	( D E C )	 	 
	D	( E C )	( S A B D )	( B )
	 	( E C )	 	 
	E	( C )	(S A B D E )	( B G I )
	 	( G I C )	 	 
	G	 	( S A B D E G)	 
RECORRIDO DE GRAFOS
Gráficamente el recorrido en profundidad o vertical:
 nivel 0
 nivel 1
 nivel 2
 nivel 3
 nivel 4
S
B
D
J
F
C
G
E
I
A
RECORRIDO VERTICAL
En la clase Operaciones se incluye el método para recorrido vertical.
Requiere utilizar la clase Cola, para implementar las listas ABIERTOS, CERRADOS y VECINOS.
Para el paso 9 del algoritmo: Los nodos vecinos de N que previamente no estén en abiertos ni cerrados se insertan al principio de ABIERTOS
Se incluye un método pertenece en la clase operaciones de la cola, que devuelve verdadero si un elemento pertenece a la cola y falso en caso contrario.
Se incluye el métodos concatenar en la clase operaciones de cola, que concatena VECINOS con ABIERTOS
Se implementa para el grafo con vértices con dato int, visto anteriormente.
RECORRIDO EN PROFUNDIDAD O VERTICAL
// RECORRIDO VERTICAL EN EL GRAFO
public void vertical(GrafoL g, int vin) {
NodoG r;
Nodo p = null;
int N;
OperCola opc = new OperCola();
Cola CERR = new Cola();
Cola ABI = new Cola();
Cola VECINOS = new Cola();
ABI.insertar(vin);
while (!ABI.colaVacia()) { N = ABI.ver();
			 CERR.insertar(N);
			 ABI.eliminar();
			 r = g.localiza(N);
			 if (r != null) { p = r.vec; }
			while (p != null) {
		if (!opc.pertenece(ABI, p.dato) && !opc.pertenece(CERR, p.dato))
					 VECINOS.insertar(p.dato);
				 p = p.sig; }
			 ABI= opc.concatenar(ABI,VECINOS)
 }
		opc.mostrar(CERR);
}
CLASE COLA
La cola se implementa con una lista doblemente enlazada:
// CLASE NODO, DE LISTA DOBLE ENLAZADA
class NodoD{
int dato;
NodoD sig,ant;
public NodoD()
{ dato=0;
 sig=ant=null;
}
public NodoD(int d)
{ dato=d;
 sig=ant=null;
}
}
CLASE COLA
// CLASE COLA, CON UNA LISTA ENLAZADA
public class Cola {
NodoD frente, fin;
// CONSTRUCTOR
public Cola()
{ frente = fin = null;	}
// VERIFICA SI LA COLA ESTA VACIA
public boolean colaVacia() 
{ return frente == null; }
// VER EL ELEMENTO DEL FRENTE
public int ver() 
{ return frente.dato;	}
CLASE COLA
// INSERTAR POR EL FIN
public void insertar(int x) {
NodoD nuevo = new NodoD(x);
if (colaVacia()) { frente = fin = nuevo; }
		else { fin.sig = nuevo;
			 nuevo.ant = fin;
			 fin = nuevo;
		}
	}
// ELIMINAR POR EL FRENTE
public void eliminar() 
{ if (!colaVacia()) { if (fin == frente) {	fin = frente = null; }
 else { frente = frente.sig;
				frente.ant = null; }
		}
	}
}
CLASE OPERACIONES COLA
// CLASE OPERACIONES DE LA COLA
class OperCola {
// INSERTAR N ELEMENTOS
public Cola insertarN(Cola p) 
{ System.out.print("No. elementos=");
 int n = Leer.datoInt();
 int dt;
 for (int i = 1; i <= n; ++i) {System.out.print("dato " + i + "=");
			 dt = Leer.datoInt();
			 p.insertar(dt);
		 }
 return p;
}
CLASE OPERACIONES COLA
// MOSTRAR
public void mostrar(Cola p) 
{ Cola aux = new Cola();
 int d;
 while (!p.colaVacia()) {	d = p.ver();
			 System.out.println(d);
			 p.eliminar();
			 aux.insertar(d);
		 }
 while (!aux.colaVacia()) { d = aux.ver();
			 aux.eliminar();
			 p.insertar(d);
		 }
}
CLASE OPERACIONES COLA
// VER SI UN ELEMENTO PERTENECE A LA COLA
public boolean pertenece(Cola p, int x) 
{Cola aux = new Cola();
 boolean sw = false;
 int d;
 while (!p.colaVacia()) { d = p.ver();
			 p.eliminar();
			 if (d == x) { sw = true; }
			 aux.insertar(d);
		 }
 while (!aux.colaVacia()) { d = aux.ver();
			 aux.eliminar();
			 p.insertar(d);
		 }
 return sw;
	}
CLASE OPERACIONES COLA
// CONCATENAR DOS COLAS (VECINOS Y ABIERTOS)
public Cola concatenar(Cola ab, Cola ve) 
{Cola aux = new Cola();
 int d;
 while (!ve.colaVacia()) { d = ve.ver();
			 ve.eliminar();
			 aux.insertar(d);
		 }
 while (!ab.colaVacia()) { d = ab.ver();
			 ab.eliminar();
			 aux.insertar(d);
		 }
 return aux;
	}
}
PROBLEMAS
PROBAR EL EJEMPLO DEL GRAFO DEL LABERINTO, CON RECORRIDO HORIZONTAL Y VERTICAL