플밍/그 외

MST - 프림 이렇게 짜면 안됨

kkap999 2022. 2. 23. 03:57
728x90

이렇게 연결되있으면 못찾음

// 프림
		boolean[] visit = new boolean[n];
		double[] minEdge = new double[n];
		Arrays.fill(minEdge, Double.MAX_VALUE);
		int v = 0; // 시작점: 0
		visit[0] = true;
		int cnt = 0;
		double ans = 0;
		while (cnt < n - 1) {
			double dist = Double.MAX_VALUE;
			int minNode = v;
			for (int i = 0; i < n; i++) {
				if (visit[i] || adj[v][i] == 0)
					continue;
				// 나와 그 점과의 거리가 지금보다 작아야돼
				if (adj[v][i] < dist) {
					dist = adj[v][i];
					minNode = i;
				}
			}
			minEdge[v] = dist;
			cnt++;
			ans += dist;
			v = minNode;
			visit[v] = true;
		}

'플밍 > 그 외' 카테고리의 다른 글

초간단!! 이클립스 디버깅 하기  (0) 2022.02.11