¿Cómo convertir un árbol de expansión mínimo a una lista de índices utilizando scipy?
Si tengo los siguientes gráficos de entrada y salida:
Gráfico de entrada árbol de expansión mínimo
(0) (0)
/ \ /
3 8 3
/ \ /
(3)—5—(1) (3)—5—(1)
\ / /
6 2 2
\ / /
(2) (2)
… creados usando scipy.sparse.csgraph.minimum_spanning_tree:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
X = csr_matrix([[0, 8, 0, 3],
… [0, 0, 2, 5],
… [0, 0, 0, 6],
… [0, 0, 0, 0]])
Tcsr = minimum_spanning_tree(X)
Tcsr.toarray().astype(int)
array([[0, 0, 0, 3],
[0, 0, 2, 5],
[0, 0, 0, 0],
[0, 0, 0, 0]])
¿Cómo puedo obtener una lista simple de índices? Entonces:
[0,3,1,2]
davy.ai
Esta lista representa el orden en el que el árbol de expansión mínima visitó los nodos en el grafo de entrada.
Para obtener esta lista, puedes utilizar el algoritmo DFS (búsqueda en profundidad) para recorrer el árbol de expansión mínima comenzando desde el nodo 0. Aquí tienes un ejemplo de implementación en Python:
La variable
lista_adj
es una lista de listas que representa la lista de adyacencia del grafo de entrada. Cada sublista contiene los índices de los nodos adyacentes al nodo correspondiente.La función
dfs
visita de forma recursiva cada nodo en el árbol de expansión mínima, comenzando desde la raíz (nodo 0). La listavisitado
lleva un registro de qué nodos ya han sido visitados para evitar ciclos. La listaresultado
se utiliza para almacenar el orden en el que se visitaron los nodos.Finalmente, se imprime la lista
resultado
, que debería darte el resultado deseado[0, 3, 1, 2]
.