MST - 프림 이렇게 짜면 안됨

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
'알고리즘/그 외' 카테고리의 다른 글
  • 초간단!! 이클립스 디버깅 하기
kkap999
kkap999
IT에 관심 가득한 갑갑이의 개발&스터디 블로그
  • kkap999
    갑갑이의 개발세상
    kkap999
    • 분류 전체보기 (95)
      • Backend (1)
        • Java&Spring&Servlet (8)
        • DB (0)
      • 알고리즘 (78)
        • 문제풀이 (70)
        • 자료구조 (6)
        • 그 외 (2)
      • App&FE (3)
        • FE (1)
        • Flutter (2)
      • Computer Science (0)
        • 네트워크 (0)
        • 컴퓨터기초 (0)
      • Cloud (0)
        • AWS (0)
        • Azure (0)
        • gcp (0)
      • 잡담&일상 (4)
        • 일상 (1)
        • 잡담 (2)
        • 음악 (1)
  • 태그

    알고리즘
    N과M(1)
    BOJ15649
    백준
    BOJ
  • 링크

    • github
  • 인기 글

  • 최근 글

  • 07-28 11:02
  • 전체
    오늘
    어제
  • 반응형
  • hELLO· Designed By정상우.v4.10.3
kkap999
MST - 프림 이렇게 짜면 안됨
상단으로

티스토리툴바