2 차원 평면에서 좌표 집합을 연결하는 최소 스패닝 트리를 찾는 방법은 무엇입니까?

Question

이미 파이썬에서 Prim의 알고리즘을 코딩했습니다. 그러나 이것은 입력으로 노드와 에지가있는 가중치 그래프를 취합니다.

주어진 좌표를 그래프로 변환하여 프로그램에서 입력을 받아 들일 수 있고 의미있는 대답을 얻으려면 어떻게해야합니까?

Answer 1

여기서 클래스의 개념이 유용 할 것입니다.

좌표 클래스를 만들고 노드와 가장자리를 해당 클래스의 인스턴스로 저장하십시오. Coordinate 클래스에 __sub__ 메소드를 추가하여 두 좌표 간의 가중치 (거리 또는 원하는 가중치)를 가져옵니다.

예 : -

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. 

지금 당신은 쉽게 사용자의 편의에 따라 인접성지도/목록을 만들 수 있으며, 해당 가중치를 찾아 알고리즘을 사용합니다.