J'ai déjà codé l'algorithme de Prim en python, mais cela prend en entrée un graphe pondéré avec des nœuds et des arêtes, ce qui n'est pas ce que j'ai.Comment trouver le Spanning Tree minimum reliant un ensemble de coordonnées dans le plan 2D?
Comment puis-je convertir les coordonnées données en un graphique tel que le programme peut accepter les entrées, et obtenir une réponse significative?
C'est là que le concept de Classes s'avérera utile.
Créez une classe Coordinate et stockez vos noeuds et arêtes en tant qu'instances de cette classe. Ajoutez une méthode __sub__ à la classe Coordinate afin d'obtenir les poids (distances ou tout ce que vous voulez que les poids soient.) Entre deux coordonnées.
Exemple: -
class Coordinate:
def __init__(self, x, y):
self.x = x
self.y = y
def __sub__(self, other):
return (self.x - other.x)**2 + (self.y - other.y)**2
# No need to square root to compare distances.
Maintenant, vous pouvez facilement créer une contiguïté Carte/Liste selon votre convenance et aussi trouver les poids correspondants et utilisez votre algorithme.
Construire un graphe (non orienté) qui connecte chaque point à tous les autres, et régler le poids de chaque arête à la distance entre les deux points le terminant – meowgoesthedog