비트마스크 & minimum spanning tree & 플로이드 워셜

비트마스크

• 비트마스크
  • 정수의 이진수 표현을 자료구조로 쓰는 기법
• 장점
  • 수행시간이 빠르다
  • 코드가 짧다
  • 메모리 사용량이 적다
• 비트연산

 

spanning tree

• 그래프 내의 모든 정점을 포함하는 트리
• 그래프에 있는 n개의 정점을 정확히 n-1개의 간선으로 연결

 

minimum spanning tree

• spanning tree중에서 사용된 간선들의 가중치 합이 최소인 트리
• 간선에 가중치를 고려하여 최소 비용의 spanning tree를 선택하는 것
• 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결

[구현방법]

1. Kruskal MST 알고리즘

[설명] 탐욕적방법을 이용하여 네트워크의 모든 정점을 최소비용으로 연결하는 최적 해답을 구하는 것

[과정]

1. 그래프의 간선들을 가중치의 오름차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택
3. 해당 간선을 현재의 MST의 집합에 추가

2. Prim MST알고리즘

[설명] 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법

[과정]

1. 시작 단계에서는 시작 정점만이 MST집합에 포함
2. 앞 단계에서 만들어진 MST집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장
3. 위의 과정을 트리가 N-1개의 간선을 가질 때까지 반복

victorydntmd.tistory.com/101?category=686701 이 링크 좋은 것 같음

 

플로이드 워셜

- 거쳐가는 정점을 기준으로 최단거리를 구함

- 예제 이해 못하겠음요ㅜㅜ hsp1116.tistory.com/45