MSTアルゴリズム

MSTという名前の最小生成ツリー
≪ツリーの生成｜Generate Tree｜oem_src≫:すべてのノードが接続されたツリー
MST:すべてのノードを最低コストで接続するツリー
答えは唯一じゃない
MSTにはkruskalとprimがあります.
kruskal(幹線全体の小さな部分から接続)は実現しにくいためprimで実現する.
Prim's
1.最初にツリーを作成します.
2.出発点から、現段階で行けるすべての場所を検索し、最も安い場所に接続します.
優先キューが使用されます.
例:

実装のために、優先順位キューに値を入力できます.
優先キュー

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

private static int prim() {
		int ret = 0;
		visited = new boolean[V + 1]; // 방문 관리
		pq = new PriorityQueue<Node>(); // 우선 순위 큐
		pq.add(new Node(1, 0));

		int cnt = 0;
		while (!pq.isEmpty()) {

			Node edge = pq.poll();

			// 이미 방문한 정점인 경우
			if (visited[edge.to]) {
				continue;
			}

			ret += edge.value;
			visited[edge.to] = true;

			// 모든 노드를 방문한 경우
			if (++cnt == V) {
				return ret;
			}

			// 연결된 노드들 중 방문하지 않은 노드 탐색
			for (int i = 0; i < adj[edge.to].size(); i++) {
				Node next = adj[edge.to].get(i);
				if (visited[next.to]) {
					continue;
				}

				pq.add(next);
			}

		}

		return ret;
	}