Algoritmos y Estructuras de Datos

Matriz de Adyacencia – Representación de Grafos

Un grafo es una estructura compuesta por vértices (nodos) y aristas que conectan dichos vértices. Los grafos pueden emplearse para modelar relaciones entre objetos o para representar una red. A menudo se utilizan para mostrar conexiones entre ciudades, personas o incluso entidades abstractas.
Los grafos pueden ser dirigidos o no dirigidos:
  1. Grafos dirigidos: Todas las aristas tienen una dirección, lo que significa que existe un “camino” de un vértice a otro, pero no necesariamente en sentido contrario. Es similar a una carretera de un solo sentido. Sin embargo, se pueden tener conexiones en ambos sentidos en un grafo dirigido, siempre y cuando se especifique de manera explícita (como en la conexión entre los vértices 5 y 8 en el grafo).
      2. Yet, it’s possible to have both directions in a directed graph. They are just explicitly marked for that (the connection between vertices 5 and 8 in the graph).
Un grafo dirigido con 8 vértices y 10 aristas. Observa que los vértices 5 y 8 tienen una conexión bidireccional.
Un grafo dirigido con 8 vértices y 10 aristas. Observa que los vértices 5 y 8 tienen una conexión bidireccional.
  1. Grafos no dirigidos: Las aristas no tienen dirección, lo que quiere decir que si hay una arista entre dos vértices, dichos vértices están conectados en ambos sentidos.
Un grafo no dirigido con 8 vértices y 9 aristas
Un grafo no dirigido con 8 vértices y 9 aristas
Una de las formas de representar un grafo es mediante una Matriz de Adyacencia. Se trata de una matriz cuadrada que representa todo el grafo. Cada fila y columna de la matriz corresponde a un vértice. Si existe una arista entre dos vértices, la entrada correspondiente en la matriz se marca con 1; de lo contrario, se marca con 0.
Una posible matriz de adyacencia para el grafo dirigido presentado arriba podría verse así:
g = [
#  1  2  3  4  5  6  7  8
  [0, 1, 0, 1, 0, 0, 0, 0],   # conexiones que salen del vértice 1
  [0, 0, 0, 0, 1, 0, 0, 0],   # conexiones que salen del vértice 2
  [0, 1, 0, 0, 0, 0, 0, 0],   # conexiones que salen del vértice 3
  [0, 0, 0, 0, 0, 0, 0, 0],   # conexiones que salen del vértice 4
  [0, 0, 0, 0, 0, 1, 0, 1],   # conexiones que salen del vértice 5
  [0, 0, 0, 1, 0, 0, 1, 0],   # conexiones que salen del vértice 6
  [0, 0, 0, 0, 0, 0, 0, 1],   # conexiones que salen del vértice 7
  [0, 0, 0, 0, 1, 0, 0, 0],   # conexiones que salen del vértice 8
]
Observa que, para una arista bidireccional, se coloca un 1 en ambas posiciones que representan la conexión entre esos dos vértices.
También hay que notar que hemos cambiado la forma de indexar. Por ejemplo, si accedemos a g[0], en realidad obtenemos todas las conexiones del nodo con índice 1. Podríamos haber usado 9 filas y 9 columnas en vez de 8 y mantener una correspondencia directa con la imagen, pero eso es decisión tuya 😎.

Desafío: Aristas a Matriz de Adyacencia

Dado un grafo con v vértices y e aristas, se te pide obtener su matriz de adyacencia.

Entrada

La primera línea de la entrada contiene dos enteros v (1 ≤ v ≤ 1000) y e (1 ≤ e ≤ 100 000).
Las siguientes e líneas contienen pares de enteros v1, v2 (1 ≤ v1, v2 ≤ v) que indican que el vértice v1 está conectado con el vértice v2 y viceversa.

Salida

El programa debe imprimir la matriz de adyacencia del grafo dado. Los valores de cada fila deben separarse con un espacio.

Ejemplos

Entrada
Salida
8 9 1 4 4 6 3 2 2 1 5 2 5 6 8 5 7 6 7 8
0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 5 MB

To check your solution you need to sign in
Sign in to continue