¿Que es una matriz de adyacencia ?

es una matriz cuadrada que se utiliza como una forma de representar relaciones binarias.

En este ejemplo veremos como se ira llenando la matriz, en la cual , desde el elemento que sale la flecha sera ubicada en la Fila de la matriz , y donde llega la flecha sera ubicado en la Columna de la matriz.(Pinchar imagen para ver en tamaño completo)

Si no te quedo claro, te invito a ver el siguiente video.

Las ventajas de usar esta representacion son :

• Se puede determinar en un tiempo fijo y constante si un enlace(arco) pertenece o no al grafo.

• Es fácil determinar si existe o no un arco o enlace, solo se debe posicionar en la matriz.

• Es fácil determinar si existe un ciclo en el grafo, basta multiplicar la matriz por ella misma n veces hasta obtener la matriz nula(no hay ciclos) o bien una sucesión periódica de matrices(hay ciclo).

Y una de sus desventajas es que  :

• Solo al leer o examinar la matriz puede llevar un tiempo de O(n2).