scipy.sparse.csgraph.

minimum_spanning_tree

scipy.sparse.csgraph.minimum_spanning_tree(csgraph, перезаписать=False)

Возвращает минимальное остовное дерево неориентированного графа

Минимальное остовное дерево — это граф, состоящий из подмножества рёбер, которые вместе соединяют все связанные узлы, минимизируя общую сумму весов на рёбрах. Это вычисляется с использованием алгоритма Краскала.

Добавлено в версии 0.11.0.

Параметры:

csgrapharray_like или разреженный массив или матрица, 2 измерения

Матрица N x N, представляющая неориентированный граф из N узлов (см. примечания ниже).

перезаписатьbool, необязательно

Если true, то части входного графа будут перезаписаны для повышения эффективности. По умолчанию False.

Возвращает:

span_treecsr matrix

N x N сжато-разреженное представление неориентированного минимального остовного дерева над входными данными (см. примечания ниже).

Примечания

Эта процедура использует ненаправленные графы как входные и выходные данные. То есть, если и graph[i, j], и graph[j, i] равны нулю, то узлы i и j не имеют соединяющего их ребра. Если хотя бы один из них ненулевой, то они соединены минимальным ненулевым значением из двух.

Эта процедура теряет точность при вводе пользователем плотной матрицы. Малые элементы < 1E-8 плотной матрицы округляются до нуля. Все пользователи должны по возможности вводить разреженные матрицы, чтобы избежать этого.

Если граф не связный, эта процедура возвращает минимальный остовный лес, т.е. объединение минимальных остовных деревьев для каждой связной компоненты.

Если возможны несколько допустимых решений, вывод может варьироваться в зависимости от версии SciPy и Python.

Примеры

Попробуйте в вашем браузере!

Следующий пример показывает вычисление минимального остовного дерева над простым четырёхкомпонентным графом:

 input graph             minimum spanning tree

     (0)                         (0)
    /   \                       /
   3     8                     3
  /       \                   /
(3)---5---(1)               (3)---5---(1)
  \       /                           /
   6     2                           2
    \   /                           /
     (2)                         (2)

Легко видеть при проверке, что минимальное остовное дерево включает удаление ребер с весами 8 и 6. В сжатом разреженном представлении решение выглядит так:

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import minimum_spanning_tree
>>> X = csr_array([[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]])

НазадОткрыть во вкладке