sábado, 13 de agosto de 2016

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.



Entrada destacada

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 pa...