Grafos como matrices dispersas en Python

csgraph trata una matriz de adyacencia dispersa como un grafo.

import numpy as np
from scipy import sparse
from scipy.sparse import csgraph

aristas = np.array([
    [0, 2, 0, 0],
    [2, 0, 3, 0],
    [0, 3, 0, 0],
    [0, 0, 0, 0],
])
grafo = sparse.csr_array(aristas)

conteo, etiquetas = csgraph.connected_components(grafo, directed=False)
print(conteo, etiquetas)

distancias = csgraph.dijkstra(grafo, directed=False, indices=0)
print(distancias)
print(csgraph.minimum_spanning_tree(grafo).toarray().astype(int))

Cómo funciona

connected_components etiqueta la componente de cada nodo.
dijkstra da los caminos más cortos desde un origen.
minimum_spanning_tree devuelve otra matriz dispersa.

Palabras clave y builtins usados aquí

as
int
print

El intento, en números

Líneas: 18
Caracteres a escribir: 438
Tokens: 129
Ritmo de tres estrellas: 110 tpm

Al ritmo de tres estrellas de 110 tokens por minuto, este intento toma unos 70 segundos.

Escribe este fragmento

Paso 2 de 4 en Dispersas y espaciales; paso 20 de 23 en Computación científica con SciPy.

← Anterior Siguiente →