Альтернативное решение алгоритма Прима

Question

Я пытаюсь найти альтернативное связующее дерево для данного графика. Тем не менее, я не могу понять, как я могу иметь несколько решений вместе на выходе.

Для данного графика в выводе я получаю 0-2 с весом 8. Кроме того, 1-3 имеет вес 8. Поэтому я тоже хочу отдельное связующее дерево, которое имеет 1-3как часть решения, давая мне 2 отдельных решения.

import sys 
class Graph(): 

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

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

    def minKey(self, key, Set): 
        min = sys.maxsize 
        for v in range(self.V): 
            if key[v] < min and Set[v] == False: 
                min = key[v] 
                min_index = v 
        return min_index 

# Prim's Algorithm 
    def prim(self): 

        key = [sys.maxsize] * self.V # Key values used to pick minimum weight edge
        parent = [None] * self.V  # Array to store constructed MST 
        key[0] = 0                # Make key 0 so that this vertex is picked as first vertex
        Set = [False] * self.V # Initially there are no vertices in MST set
        parent[0] = -1            # First node is always the root 

        for i in range(self.V):                 
            u = self.minKey(key, Set)                                            
            Set[u] = True 

            for v in range(self.V): 
                if self.graph[u][v] > 0 and Set[v] == False and key[v] > self.graph[u][v]: 
                        key[v] = self.graph[u][v] 
                        parent[v] = u 

        self.printTree(parent) 


Prim = Graph(7) 
Prim.graph = [[0, 4, 8, 0, 0, 0, 0], 
              [4, 0, 9, 8, 10,0, 0], 
              [8, 9, 0, 2, 0, 1, 0], 
              [0, 8, 2, 0, 7, 9, 0], 
              [0, 10, 0, 7, 0, 5, 6],
              [0, 0, 1, 9, 5, 0, 2],
              [0, 0, 0, 0, 6, 2, 0]]
Prim.prim()