이론공부25 최소신장트리에 대해(신장트리, 크루스칼, 프림) 시작 하기전에 용어에 대해 적어보도록 하겠습니다. ▶노드, 정점 : A,B,C,D라고 적혀있는 부분을 노드 혹은 정점이라고 합니다. ▶간선 : 노드 끼리 연결하는 선을 간선이라고 합니다. ▶거리 : 위의 그림은 간선에 대한 가중치 혹은 값이 적혀있지 않는데, 이값이 적혀있다면 거리라고 합니다. 간선과 거리를 같이 사용할 때도 있습니다. ▶신장트리(spanning tree) : ★모든 노드를 포함하고, ★모든 노드가 서로 연결이 되어있고 ★싸이클이 발생하지 않은 트리 위 사진은 모든 노드가 포함 및 연결이 되어있고 사이클이 발생하지 않았으므로 신장트리 입니다. 이와 같은 경우는 A, B, D에서 사이클을 형성했기 때문에 신장트리가 아닙니다. 대신에 간선을 하나 지움으로써 3가지의 신장트리를 만들 수 있습니.. 이론공부/알고리즘 2019. 12. 9. 이전 1 2 3 다음 💲 광고입니다.