GRAFOS2

Vista previa del material en texto

GRAFOS 
TERMINOLOGÍA
EN GRAFO NO DIRIGIDO:
Incidencia: La arista (u,v) es incidente con los vértices u y con v. De forma que:
Aristas a, d, y b son incidentes en V
Adyacencia: Dos vértices u y v son adyacentes si existe la arista (u, v) o (v, u).
Grado de un vértice: Determinado por el número de vértices adyacentes al nodo. 
Grado de X = 3
EN GRAFO DIRIGIDO:
Grado de salida: número de vértices adyacentes desde el nodo.
Grado de salida de W = 0
Grado de salida de Y = 2
Grado de entrada: número de vértices adyacentes al nodo.
Grado de entrada de W = 4
Grado de entrada de Y = 0
X
U
V
W
Y
a
c
b
e
d
f
g
X
U
V
W
Y
a
c
b
e
d
f
g
TERMINOLOGÍA
<a,b,e,d,c>: camino simple de longitud 4.
<a,c,d,a,b,e>: camino de longitud 5.
<a,e>: no es un camino.
<e,e>: camino, bucle y ciclo
a
b
c
d
e
Grafo no dirigido
a
b
c
d
e
Grafo dirigido
<a,b>: camino simple de longitud 1.
<e,d,a,b>: camino de longitud 3.
<a,c,d>: no es un camino.
<e,e>: camino, bucle y ciclo
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);
 // Recorre lista de vecinos 
 q=p.vec;
 while(q!=null) { 
 System.out.println("dato de vecino= "+q.dato);
 q=q.sig;
 }
 p=p.sigx;
 }
 }
}
PROBLEMAS
RESUMEN DE LAS DIAPOSITIVAS DE GRAFO1 (MAX 4 PAG.)
PROBAR EL EJEMPLO
RESOLVER EL EJEMPLO, COMO UN GRAFO NO DIRIGIDO
(OPCIONAL CON 2) DEFINIR UN GRAFO CON DATO STRING, SEGÚN LA FIGURA SIGUIENTE. INSERTAR N NODOS Y MOSTRAR.
Ciudad B
Ciudad C
Ciudad F
Ciudad D
Ciudad E
Ciudad A