Matriz de adyacencia para un grafo

"La matriz de adyacencia es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias."; aunque para nuestro caso será una de las formas de representar un grafo.

¿Por que matriz cuadrada? (si fuera profesor lo preguntaría para pescar a más de un distraído), la razón es que tanto las filas como las columnas representan cada uno de los nodos del grafo, si el grafo es de n nodos, la matriz correspondiente sería de n * n, es decir matriz cuadrada, fácil.

Continuemos analizando el paso de grafo a una matriz.

Como ya sabemos al tener 6 nodos nuestro grafo, nuestra matriz tendrá unas dimensiones de 6 * 6, es decir 6 filas y seis columnas.

Si nos fijamos en lo que consideraremos nuestro primer nodo, el nodo uno solo esta conectado con el nodo 2 y 5; en la fila 1 que representa el nodo 1 se ha marcado con ceros los nodos con que no se tiene relación y se ha fijado un 1 en los que si, el nodo 2 y 5.

Si nos fijamos en lo que consideraremos nuestro segundo nodo, el nodo dos esta conectado con el nodo 1, 3 y 5; en la fila 2 que representa el nodo 2 se ha marcado con ceros los nodos con que no se tiene relación y se ha fijado un 1 en los que si, el nodo 1, 3 y 5.

Análogamente hacemos de igual forma con los demás nodos hasta terminar el grafo.

Les dejo algunos ejemplo y un ejecutable en Java de mi autoría para que se diviertan.

Clic aquí para descargar ejecutable.

Métodos de ordenamiento usando java

Cuando tenemos una estructura de datos una de las operaciones más relevantes es ordenar el contenido de la misma, ya sea para hacerla más amistosa de leer o mejor aún para aplicar más operaciones sobre dichos datos como por ejemplo hacer búsquedas en ellas, (véase búsqueda binaria y búsqueda secuencial).

El ordenamiento en una estructura de datos la podemos definir como los posibles cambios aplicados a la posición de los datos que la llevaría a estar una relación de orden, ésta relación de orden puede ser alfabética, numérica, entre otras.




Aunque la formulación del problema es fácil y hasta cotidiana, tanto como dar una secuencia de números aleatorios a alguien y pedirle de los ordene de mayor a menor; existen muchos métodos para la resolución de éste problema, y aún en la actualidad se sigue trabajando en ello para lograr cada vez más rapidez y eficacia.

En éste blog abordaré varios de los métodos más usados para la ordenación de datos y que a su vez nos servirán como introducción a éste tema usando Java como lenguaje de programación.

Clic para ver el método de selección.
Clic para ver el método de inserción. (próximamente)
Clic para ver el método de burbuja. (próximamente)
Clic para ver el método de shell. (próximamente)

Método de ordenamiento por selección usando Java

Es un método poco eficiente pero fácil de entender, en caso de ordenar números éste consistirá en determinar cual es el menor de todos y ubicarlo en la primera posición, luego determinar cual es el segundo menor y ubicarlo en la segunda posición hasta terminar con todo los numero.

La cantidad de comparaciones para éste método de ordenamiento está dada por la fórmula: c(n) = (n² – n)/2; es decir para un arreglo de 10 elementos el numero de comparaciones es de (10² – 10)/2 = 45; en el siguiente código fuente al descomentariar la linea 7 y compilar notarán el número de comparaciones.

Analizando podemos darnos cuenta que aunque nuestro arreglo a mitad del proceso este ordenado, el método seguirá haciendo comparaciones innecesarios haciéndolo poco eficiente sobre todo para grandes cantidades de elementos.

Sin más preámbulos, el código:

class seleccion{
 public static void ordenar(int[] arreglo){
  int contador = 1;//solo util para contar las comparaciones
  for (int i = 0; i < arreglo.length - 1; i++){
   int min = i;
   for (int j = i + 1; j < arreglo.length; j++){
   //System.out.println("Comparacion #" + contador);
    contador++;
    if (arreglo[j] < arreglo[min]){
     min = j;
    }
   }
   if (i != min){
    int aux= arreglo[i];
    arreglo[i] = arreglo[min];
    arreglo[min] = aux;
   }
  }
 }
 public static void imprimirLista(int[] arreglo){
  for(int i = 0; i < arreglo.length;i++){
   System.out.print(arreglo[i]+",");
  }
  System.out.println();
 }
 public static void main(String[] args){
  int lista[] = {9,1,4,2,8,3,5,6,7,0};
  System.out.print("Lista desordenada: ");
  imprimirLista(lista);
  
  ordenar(lista);

  System.out.print("Lista ordenada: ");
  imprimirLista(lista);
 }
}

Deseaba en ésta entrada hacer una prueba de escritorio al método, pero haré algo mejor, agregaré comentarios de salida al codigo para detallar cada comparación de la lista que ustedes introduzcan, abajo está el link de descarga, espero les guste y hagan sus comentarios.

Descarga aqui codigo con prueba de escritorio