GRAFO MATRIZ ADYACENCIAS 4

Vista previa del material en texto

GRAFO CON MATRIZ DE ADYACENCIAS
GRAFO CON MATRIZ DE ADYACENCIA
Cada vértice se nombra con un número entero: 1, 2, 3, ….
En la matriz de adyacencia (mady), en la fila está el número del vértice origen y en la columna el número del vértice destino de cada arista.
Entonces si hay una arista entre dos vértices se coloca un 1 en la matriz y si no hay se coloca un 0.
El dato de cada vértice se representa en un vector (dato), en el que el índice es el número de vértice y el elemento es el dato.
dato[1]=20, significa que en el vértice 1 se tiene el dato 20.
GRAFO DIRIGIDO
Matriz no simétrica dato
	mady	1	2	3	4	5
	1	0	1	1	0	0
	2	0	0	1	0	1
	3	1	0	0	1	1
	4	0	0	0	0	0
	5	0	0	0	1	0
1
2
5
4
3
	1	20
	2	-5
	3	50
	4	10
	5	8
GRAFO NO DIRIGIDO
Matriz simétrica M[i, j] = M[j, i] dato
1
2
5
4
3
	mady	1	2	3	4	5
	1	0	1	0	1	0
	2	1	0	1	0	1
	3	0	1	0	1	0
	4	1	0	1	0	1
	5	0	1	0	1	0
	1	20
	2	-5
	3	50
	4	10
	5	8
VENTAJAS Y DESVENTAJAS
Ventajas
Representación y operaciones muy sencillas.
Eficiente para el acceso a una arista dada.
Desventajas
El número de nodos del grafo no puede cambiar.
Si hay muchos nodos y pocas aristas (a<<n2) se desperdicia mucha memoria (matriz escasa).
Clase Grafo
 Grafo
 mady, dato
 constructor
 asignaV()
 grafoVacio()
 insertarArista()
 insertarVertice()
 verticeDeDato(d)
 class Grafo{ // CLASE Grafo
 int[ ][ ] mady;
 int[ ] dato;
 int nv;
 final int nel=20;
 public Grafo() // Constructor por defecto
 { nv=0;
 mady=new int[nel][nel];
 dato=new int[nel]; }
 // Asigna a nv el número de vértices del grafo
 public void asignaV(int ne)
 {nv=ne;}
 // Verifica si el grafo está vacío
 public boolean grafoVacio()
 { return nv==0;}
CLASE Grafo
 public void insertarArista() // Inserta una arista en la matriz de adyacencias 
 { System.out.print("Vertice origen=");
	 int vo=Leer.datoInt();
	 System.out.print("Vertice destino=");
	 int vd=Leer.datoInt();
	 mady[vo][vd]=1;
 }
 public void insertarVertice() // Inserta un vértice en el vector de datos
 { System.out.print("No. vertice=");
	 int v= Leer.datoInt();
	 System.out.print("Dato del Vertice=");
	 int dt=Leer.datoInt(); 
	 dato[v]=dt;
 }
CLASE Grafo
// Retorna el vértice de un dato del vector de datos
public int verticeDeDato(int d)
 { int v=0; 
 for(int i=1;i<=nv;++i )
 if(dato[i]==d ) v=i;
 }
 return v;
 }
}
class Operaciones { // CLASE Operaciones
public GrafoL insertarN(GrafoL g)
{ System.out.print("No. vertices=");
 int n=Leer.datoInt();
 g.asignaV(n);
// INSERTAR N VÉRTICES AL VECTOR DE DATOS dato
	 for(int i=1; i<=n;++i) {
 g.insertarVertice(); }
// INSERTAR N ARISTAS A LA MATRIZ DE ADYACENCIAS mady
	 System.out.print("No. de aristas=");
	 int na= Leer.datoInt();
	 for(int i=1; i<=na;++i) { 
 g.insertarArista(); }
 return g;
 }
Clase Operaciones
public void horizontal(Grafo g, int vin) // RECORRIDO HORIZONTAL
{ OperCola opc=new OperCola();
 Cola CERR=new Cola();
 Cola ABI=new Cola();
 ABI.insertar(vin);
 int N,d; int v;
 while(!ABI.colaVacia() ) { N=ABI.ver();
	 CERR.insertar(N);
	 ABI.eliminar();
 for(int c=1;c<=g.nv;++c) { v=g.verticeDeDato(N); //VERTICE DEL DATO N
 if(g.mady[v][c]==1) {d=dato[c]; // DATO DEL VERTICE c
	 if(!opc.pertenece(ABI,d)&&!opc.pertenece(CERR,d)) ABI.insertar(d); }
 } }
	 opc.mostrar(CERR); } 
public void vertical(Grafo g, int vin) // RECORRIDO VERTICAL EN EL GRAFO
{ int N,d; int v;
 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();
 for(int c=1;c<=g.nv;++c) { v=g.verticeDeDato(N); // VERTICE DEL DATO N
	 if(g.mady[v][c]==1) { d=dato[c]; // DATO DEL VERTICE c
	 if(!opc.pertenece(ABI,d)&&!opc.pertenece(CERR,d)) VECINOS.insertar(d); }
 }
 			 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;
	}
}
CLASE PRINCIPAL GRAFO
 public class Principal{
 public static void main(String[] args)
 { 	Grafo g=new Grafo();
	 OperGrafo op=new OperGrafo();
	 g=op.insertarN(g);
	 System.out.print("Vertice inicial:");
	 int vini=Leer.datoInt();
	 op.horizontal(g,vini);
 }
 }
PROBLEMAS
PROBAR EL EJEMPLO