2건의 항목
그래프 용어 V : vertex E : Edge path 연결 그래프 : 어떤 두 정점 사이에도 경로가 존재하는 그래프 부분 그래프 가중치 포함 그래프 : Edge에 가중치가 달려있음 순환 경로 순환 그래프, 비순환 그래프 트리 - 비순환, 비방향그래프 신장 트리 : 연결된, 비방향성 그래프에서 순환경로를 제거하면서 연결된 부분 그래프가 되도록 하는 트리 신장 트리의 개수는 Cayley’s formula에 따른 개수를 가짐 최소비용신장트리 신장 트리가 되는 부분 그래프 중에서 가중치가 최소가되는 부분 그래프 무조건 트리로 나온다.
풀이 다익스트라로 한번에 성공했다. 그래도 발전이 있나보네. 스위프트로 플루이드 워셜로 다시 풀었다. Code # AB가 함께 모든 노드까지 가는데 걸리는 최단 거리를 구한다. # 그리고 그 거리 각각에서 출발하여 # 1.