Java: Estructura de Datos. Grafos.

Desarrollar la Clase Grafo con representación de matriz de adyacencia.

Un grafo consiste de un conjunto de nodos o vértices y un conjunto de ejes o aristas. Usualmente se lo denota = (). Las aristas son pares de vértices () con 2. Si () 2, se dice que y están conectados o son adyacentes. Un trazado o dibujo de un grafo = () usando segmentos de 1 recta para las aristas es una asignación de una posición en el plano a cada vértice en V. En las versiones más simples, los vértices son dibujados como puntos y las aristas como segmentos entre vértices. De aquí en más supondremos que el trazado usa segmentos para las aristas, excepto cuando se aclare lo contrario. También se supondrá que el grafo es conexo, ya que si el grafo a trazar no lo es, se puede trazar cada componente conexa por separado.

Los grafos sólo contienen información relacional entre los vértices, así que en principio no tienen ninguna forma \natural" de ser dibujados. Sin embargo, de las infinitas formas de trazar un grafo en el plano, algunas son claramente peores que otras, siempre teniendo en cuenta que el objetivo es visualizar el grafo.

package grafos;

/**
* Camino Minimo
*
* Calcula el camino minimo
*
* Clase Grafo
*
* @author Damian Adriel Perez Valdes
*
* Un grafo se compone de un conjunto de nodos que están enlazados por
* un conjunto de arcos.
* Cada arco tiene asociado un peso que puede verse como el coste de ir
* del nodo "origen" al nodo "destino"
* Un grafo queda caracterizado, por tanto, por:
* - el número de nodos que tiene
* - los arcos, que representan distancias entre los nodos
*/

public class Grafo {
/**
* Ds nodos sin un arco entre ellos, se dicen que están a distancia INFINITO.
*/
public static final int INFINITO = Integer.MAX_VALUE;

/**
* Número de nodos del grafo.
*/
public int numNodos;

/**
* Tabla con los arcos que enlazan los nodos del grafo.
* Un valor INFINITO indica que no hay conexión entre los nodos.
*/
public int[][] arcos;

/**
* Tablas con la posición (x, y) del nodo en un dibujo.
*/
public int[] posicionX;
public int[] posicionY;

/**
* Construye un grafo con el número de nodos que se pasa como argumento.
*
* @param numero Número de nodos del grafo.
*/
public Grafo(int numero) {
this.numNodos = numero;
arcos = new int[numNodos][numNodos];
posicionX = new int[numNodos];
posicionY = new int[numNodos];
for (int i = 0; i < j =" 0;" i ="=">Representación de dos algoritmos voraces (greedy) sobre la clase Grafo.

El algoritmo de Prim es un algoritmo de la teoría de los grafos para encontrar un árbol de expansión mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol de expansión mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

// Matriz bidimensional de enteros que representa el grafo.
private int grafo[][];

/**
* Método que recorre un vector para comprobar si se encuentra en él un valor
* recibido.
* @param vector Vector de enteros donde va almacenando la solución.
* @param i Número a buscar dentro del vector.
* @return Devuelve true si lo encuentra.
*/
private boolean estaRepetido(int vector[], int i) {
for (int j = 0; j < grafo =" caminos;" numnodos =" grafo.length;" i =" 0;" longitudcamino =" 0;" menor =" 0;" actual =" inicio;" i =" 0;" menor =" i;" actual =" menor;">Solución de un problema real usando el código anterior.

El problema al cuál se da solución es encontrar el camino mínimo en una red de computadoras.

package grafos;

/***
* Camino Minimo
*
* Calcula el camino minimo
*
* @author Damian Adriel Perez Valdes
*/

import java.io.*;

public class Camino extends Grafo
{
// Matriz bidimensional de enteros que representa el grafo.
private int grafo[][];

/**
* Método contructor de la clase.
*/
public Camino(int n) {
super(n);
}

/**
* Método que recorre un vector para comprobar si se encuentra en él un valor
* recibido.
* @param vector Vector de enteros donde va almacenando la solución.
* @param i Número a buscar dentro del vector.
* @return Devuelve true si lo encuentra.
*/
private boolean estaRepetido(int vector[], int i) {
for (int j = 0; j < grafo =" caminos;" numnodos =" grafo.length;" i =" 0;" longitudcamino =" 0;" menor =" 0;" actual =" inicio;" i =" 0;" menor =" i;" actual =" menor;" lectura =" new" n =" Integer.parseInt(lectura.readLine());" gf =" new" i =" 0;" j =" 0;" i=" 0;" j =" 0;" inicio =" Integer.parseInt(lectura.readLine());">= 0)
{
//Instancia de la clase camino.
Camino c = new Camino(n);

// Encontrar el camino mínimo.
solucion = c.caminoMinimo(gf.arcos, inicio);

// Mostrar el árbol mínimo abarcador.
System.out.print("\nCAMINO MÍNIMO ABARCADOR --> Solución: ");

for (int i = 0; i < style="font-weight: bold;">Ejemplo:

Ingrese el orden de la matriz de adyacencia:
3
Ingrese elemento (0,0) : 2
Ingrese elemento (0,1) : 5
Ingrese elemento (0,2) : 6
Ingrese elemento (1,0) : 4
Ingrese elemento (1,1) : 2
Ingrese elemento (1,2) : 3
Ingrese elemento (2,0) : 4
Ingrese elemento (2,1) : 1
Ingrese elemento (2,2) : 2

Matriz de Adyacencia :

2 5 6
4 2 3
4 1 2

Ingrese Nodo de Inicio :
2

CAMINO MÍNIMO ABARCADOR --> Solución: 2 1 1 2 5 6
4 2 3
4 1 2