Кластеризация из минимального связующего дерева python

Question

Мне поручено взять матрицу смежности, найти минимальное остовное дерево и затем кластеризовать его в K (кластеры, введенные пользователем). Моя матрица смежности

[[0, 3, 4, 5, 2], 
[3, 0, 2, 4, 0], 
[4, 2, 0, 1, 0], 
[5, 4, 1, 0, 0], 
[2, 0, 0, 0, 0]]

Мой main ()

g = Graph(n)
g.graph = adjmtrx
newg = Graph(g.V)
newg = g.primMST()

Мне дали этот шаблон, который найдет минимальное связующее дерево:

import sys  # Library for INT_MAX

class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                      for row in range(vertices)]

        # A utility function to print the constructed MST stored in parent[]

    def printMST(self, parent):
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree 
    def minKey(self, key, mstSet):

        min = sys.maxsize

        for v in range(self.V):
            if key[v] < min and mstSet[v] == False:
                min = key[v]
                min_index = v

        return min_index

    # Function to construct and print MST for a graph
    # represented using adjacency matrix representation
    def primMST(self):

        outMST = Graph(self.V)
        # Key values used to pick minimum weight edge in cut 
        key = [sys.maxsize] * self.V
        parent = [None] * self.V  # Array to store constructed MST
        # Make key 0 so that this vertex is picked as first vertex 
        key[0] = 0
        mstSet = [False] * self.V

        parent[0] = -1  # First node is always the root of

        for cout in range(self.V):

            # Pick the minimum distance vertex from  
            # the set of vertices not yet processed.  
            # u is always equal to src in first iteration 
            u = self.minKey(key, mstSet)

            # Put the minimum distance vertex in  
            # the shortest path tree 
            mstSet[u] = True

            # Update dist value of the adjacent vertices  
            # of the picked vertex only if the current  
            # distance is greater than new distance and 
            # the vertex in not in the shotest path tree 
            for v in range(self.V):
                # graph[u][v] is non zero only for adjacent vertices of m 
                # mstSet[v] is false for vertices not yet included in MST 
                # Update the key only if graph[u][v] is smaller than key[v] 
                if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        for v in range(self.V):
            outMST.graph[v][parent[v]] = self.graph[v][parent[v]]
            outMST.graph[parent[v]][v] = self.graph[parent[v]][v]

        self.printMST(parent)
        return outMST

Теоретически, Я собирался попытаться сохранить ребра и веса в списке гнезд следующим образом:

[[[0, 1], 3], [[1, 2], 2], [[2, 3], 1], [[0, 4], 2]]

Затем найдите самый тяжелый вес и затем установите этот вес на 0. Это было бы для кластеров с K = 2.

Полагаю, я застрял в той части, где после обновления веса как разделить ребра на кластеры? После того, как вы урежете путь от 0 до 1, мне все равно нужно будет следовать пути от 0 до 4 и следовать пути 1 до 3. Я думал, что для K> 2 это должна быть некоторая рекурсивная функция. Вывод будет что-то вроде:

For K = 2:
0 4
1 2 3