Matriz de adyacencia en Python

  2. HowTo
  3. How-To's de Python
  4. Matriz de adyacencia en Python
Aditya Raj 21 junio 2023
Python Python Matrix
  1. Crear una matriz de adyacencia
  2. Crear una matriz de adyacencia en Python usando listas 2D
  3. Cree una matriz de adyacencia en Python usando el módulo NumPy
  4. Conclusión
Matriz de adyacencia en Python

Una estructura de datos de gráficos se utiliza en Python para representar varios objetos de la vida real, como redes y mapas. Podemos representar un gráfico usando una matriz de adyacencia.

Este artículo discutirá diferentes formas de implementar la matriz de adyacencia en Python.

Crear una matriz de adyacencia

Considere el siguiente gráfico.

Gráfico no ponderado no dirigido de matriz de adyacencia de Python

En el gráfico, hay 6 nodos numerados del 1 al 6. Hay 7 aristas en el gráfico que conectan los nodos; un borde eij conecta el nodo i y el nodo j.

Para representar el gráfico, usamos una matriz de adyacencia.

  1. Una matriz de adyacencia consta de una cuadrícula bidimensional.
  2. Cada fila o columna de la cuadrícula representa un nodo.
  3. Para un gráfico no ponderado, como se muestra arriba, si el valor en la posición (i,j) es 1 en la cuadrícula, significa que el nodo i y el nodo j están conectados.
  4. Si el valor en la posición (i,j) es 0, el nodo i y el nodo j no están conectados.

Si desea crear una matriz de adyacencia para el gráfico de la imagen de arriba, se verá de la siguiente manera.

| 0    | 1    | 0    | 0    | 0    | 0    |
| 1    | 0    | 1    | 1    | 0    | 0    |
| 0    | 1    | 0    | 1    | 0    | 1    |
| 0    | 1    | 1    | 0    | 1    | 0    |
| 0    | 0    | 0    | 1    | 0    | 1    |
| 0    | 0    | 1    | 0    | 1    | 0    |

La tabla anterior muestra que el valor en la posición (i,j) también está presente en la posición (j,i). Esto se debe a que la arista eij es la misma que la arista eji.

Esto también da como resultado una matriz de adyacencia que es simétrica a lo largo de su diagonal.

En un gráfico no ponderado, los bordes no tienen peso. En otras palabras, todas las aristas tienen el mismo peso.

Debido a esto, la matriz de adyacencia contiene solo los valores 0 y 1.

Ahora, considere el siguiente gráfico ponderado.

Gráfico ponderado de matriz de adyacencia de Python

Para un gráfico ponderado, todo permanece igual excepto los pesos de los bordes. Puede observar que a cada borde se le ha asignado un valor en la imagen.

Por lo tanto, en la matriz de adyacencia, el valor en la posición (i,j) es el peso de la arista eij en el gráfico.

La matriz de adyacencia para la imagen de arriba se ve de la siguiente manera.

| 0    | 5    | 0    | 0    | 0    | 0    |
| 5    | 0    | 1    | 12   | 0    | 0    |
| 0    | 1    | 0    | 8    | 0    | 4    |
| 0    | 12   | 8    | 0    | 7    | 0    |
| 0    | 0    | 0    | 7    | 0    | 2    |
| 0    | 0    | 4    | 0    | 2    | 0    |

Nuevamente, puede observar que el valor en la posición (i,j) en la matriz también está presente en la posición (j,i). Esto se debe a que la arista eij es la misma que la arista eji.

Nuevamente, esto da como resultado una matriz de adyacencia simétrica a lo largo de su diagonal.

Crear una matriz de adyacencia en Python usando listas 2D

Para crear una matriz de adyacencia para un gráfico no ponderado con n nodos, primero crearemos una lista bidimensional que contenga n listas internas. Además, cada lista interna contiene n ceros.

Después de crear una lista bidimensional que contenga ceros, asignaremos 1 a las posiciones (i,j) donde existe la arista eij en el gráfico. Para esta tarea, utilizaremos los siguientes pasos.

  • Primero, crearemos una lista vacía llamada matriz_adyacencia. Después de eso, la convertiremos en una lista bidimensional usando un bucle for y el método append().
  • Dentro del ciclo for, crearemos una lista vacía llamada fila. Luego, llenaremos la lista vacía con ceros usando otro bucle for, y finalmente, agregaremos fila a la matriz_adyacencia.
  • En el código, hemos representado el conjunto de aristas usando una lista de tuplas. Cada tupla contiene 2 valores que representan los nodos conectados del gráfico.
  • Después de definir los bordes, asignaremos el valor 1 a las posiciones donde los bordes están presentes en el gráfico usando un bucle for.

Código:

import pprint

row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
    row = []
    for j in range(col_num):
        row.append(0)
    adjacency_matrix.append(row)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
    row = edge[0]
    col = edge[1]
    adjacency_matrix[row - 1][col - 1] = 1
    adjacency_matrix[col - 1][row - 1] = 1

print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

Producción :

The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
[[0, 1, 0, 0, 0, 0],
 [1, 0, 1, 1, 0, 0],
 [0, 1, 0, 1, 0, 1],
 [0, 1, 1, 0, 1, 0],
 [0, 0, 0, 1, 0, 1],
 [0, 0, 1, 0, 1, 0]]

En el código, puede observar que tenemos una indexación basada en 0. Debido a esto, cada nodo (i,j) está representado por la posición (i-1,j-1) en la matriz de adyacencia.

Para crear una matriz de adyacencia para un gráfico ponderado, primero crearemos una lista bidimensional n x n que tenga ceros. Después de eso, asignaremos el peso de la arista eij en la posición (i,j) en la matriz.

Puedes observar esto en el siguiente ejemplo.

import pprint

row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
    row = []
    for j in range(col_num):
        row.append(0)
    adjacency_matrix.append(row)
weighted_edges = [
    (1, 2, 5),
    (2, 4, 12),
    (2, 3, 1),
    (3, 4, 8),
    (4, 5, 7),
    (3, 6, 4),
    (5, 6, 2),
]
for edge in weighted_edges:
    row = edge[0]
    col = edge[1]
    weight = edge[2]
    adjacency_matrix[row - 1][col - 1] = weight
    adjacency_matrix[col - 1][row - 1] = weight

print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

Producción :

The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
[[0, 5, 0, 0, 0, 0],
 [5, 0, 1, 12, 0, 0],
 [0, 1, 0, 8, 0, 4],
 [0, 12, 8, 0, 7, 0],
 [0, 0, 0, 7, 0, 2],
 [0, 0, 4, 0, 2, 0]]

En el código anterior, los bordes se han representado usando un triplete de números. Los primeros 2 números representan los nodos del gráfico que están conectados por el borde.

El tercer número representa el peso del borde.

Cree una matriz de adyacencia en Python usando el módulo NumPy

Para hacer una matriz de adyacencia para un gráfico usando el módulo NumPy, podemos usar el método np.zeros().

El método np.zeros() toma una tupla en forma de (row_num,col_num) como argumento de entrada y devuelve una matriz bidimensional de forma row_num x col_num. Aquí, row_num y col_num son el número de filas y columnas en la matriz.

Usaremos los siguientes pasos para crear una matriz de adyacencia usando el método np.zeros().

  • Primero, crearemos una matriz de tamaño n x n pasando una tupla (n,n) al método zeros().
  • Luego, actualizaremos los valores a 1 en la posición (i-1,j-1) para cada borde eij en el gráfico; aquí, usamos indexación basada en 0. Debido a esto, el nodo (i,j) está representado por la posición (i-1,j-1) en el código.

Después de ejecutar los pasos anteriores, obtendremos la matriz de adyacencia, como se muestra en el siguiente ejemplo.

import pprint
import numpy as np

row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
    row = edge[0]
    col = edge[1]
    adjacency_matrix[row - 1][col - 1] = 1
    adjacency_matrix[col - 1][row - 1] = 1

print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

Producción :

The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
array([[0, 1, 0, 0, 0, 0],
       [1, 0, 1, 1, 0, 0],
       [0, 1, 0, 1, 0, 1],
       [0, 1, 1, 0, 1, 0],
       [0, 0, 0, 1, 0, 1],
       [0, 0, 1, 0, 1, 0]])

Para crear la matriz de adyacencia para los gráficos ponderados, actualizaremos los valores en la posición (i,j) al peso del borde eij como se muestra a continuación.

import pprint
import numpy as np

row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
weighted_edges = [
    (1, 2, 5),
    (2, 4, 12),
    (2, 3, 1),
    (3, 4, 8),
    (4, 5, 7),
    (3, 6, 4),
    (5, 6, 2),
]
for edge in weighted_edges:
    row = edge[0]
    col = edge[1]
    weight = edge[2]
    adjacency_matrix[row - 1][col - 1] = weight
    adjacency_matrix[col - 1][row - 1] = weight

print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)

Producción :

The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
array([[ 0,  5,  0,  0,  0,  0],
       [ 5,  0,  1, 12,  0,  0],
       [ 0,  1,  0,  8,  0,  4],
       [ 0, 12,  8,  0,  7,  0],
       [ 0,  0,  0,  7,  0,  2],
       [ 0,  0,  4,  0,  2,  0]])

Conclusión

Este artículo analiza dos formas de implementar una matriz de adyacencia en Python. Le sugerimos que implemente una matriz de adyacencia con el módulo NumPy, ya que es mucho más eficiente en términos de requisitos de almacenamiento.

Además, realizar diferentes operaciones en una matriz NumPy es mucho más eficiente con respecto a los requisitos de tiempo y memoria.

Autor: Aditya Raj
Aditya Raj avatar Aditya Raj avatar

Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.

GitHub

Artículo relacionado - Python Matrix