알고리즘)greedy(다익스트라등

 

 

 

신장트리는 무방향성

• 조건 1 (모두 포함): 그래프에 있는 **모든 점(정점)**을 다 연결해야 합니다.
• 조건 3 (사이클 없음): **'순환 경로(한 바퀴 도는 루프)'**가 없어야 합니다. 즉, 나무(Tree)처럼 뻗어 나가는 모양이어야 합니다.

 

 

 

위에서 말한 '신장 트리'는 한 그래프 안에서 여러 가지 모양으로 나올 수 있습니다. 그런데 각 도로(에지)마다 **건설 비용(가중치)**이 다르다고 가정해 봅시다.

• 정의: 여러 가지 신장 트리 중에서 연결된 도로들의 비용 합계가 '가장 작은' 트리를 말합니다.

 

 

 

 

 

 

다익스트라랑 차이점 

프림은 '내 구역까지의 누적 거리'를 더하지 않고, 오로지 '내 구역과 연결되는 에지 중 가장 짧은 것'만 갱신합니다

 

 

다익스트라 (최단 경로 
프림 (신장트리

플로이드 (Floyd): "모든 지점 간의 최단 경로 찾기"

• 프림(Prim) 알고리즘: 정점(Vertex) 하나를 잡고, 거기서 뻗어 나가는 가지를 찾는 방식 (정점이 주인공)
• 크루스칼 알고리즘: 모든 엣지를 가중치 순으로 정렬해두고, **"이 엣지 써도 되나?"**를 하나씩 검사하는 방식 (엣지가 주인공)-집합연산 있는 이유 

 

 

 

 

 

 

 

 

 

 

 

 

• 문제: 주머니에 이미 "A마을: 100원"이라고 적힌 쪽지가 들어있는데, 나중에 "A마을: 50원"이라는 더 싼 정보가 들어왔습니다.
• 해결 방법 2가지:
  1. 추가하기: 그냥 50원짜리 쪽지를 하나 더 넣습니다. (주머니가 알아서 50원을 위로 올려줄 테니, 나중에 100원짜리 쪽지가 나오면 무시하면 됩니다.)
  2. 수정하기: 주머니 속을 뒤져서 100원짜리 쪽지를 찾아 50원으로 고칩니다. (이걸 하려면 주머니 속 어디에 누가 있는지 알려주는 **'인덱스(주소록)'**가 별도로 필요합니다.)

 

 

 

v==n

o(1)아닌 이유는 재구성 비용도 포함(민힙)

 

첫번째 반복문은 최소가 되는 정점 찾기이고, 두번쨰 반복문은, 모든 엣지의 거리 갱신인건가, 그래야 다시 1번 반복문에서 최소를 찾을수있어서?ㅇㅇㅇ

 

외부반복문 n-1번 

힙에서 정점을 하나씩 꺼내서 '확정' 짓는 행위 자체가 총 V번 일어나기 때문입니다.
코드상으로는 바뀝니다: for문으로 딱딱하게 돌기보다는, 힙에 데이터가 있는 동안 계속 뽑아 쓰는 while문 형태로 구현되는 경우가 많습니다.

 

 

 

 

 

 

repeat (V-1 times) {         // 바깥 루프: V번
    
    // 1. 최솟값 찾기 루프
    for (i=2; i<=n; i++) {   // 마을 전체 뒤지기: V번
        // 제일 싼 놈 찾기...
    }

    // 2. 가격표 갱신 루프
    for (i=2; i<=n; i++) {   // 마을 전체 뒤지기: V번
        // 가격 고치기...
    }
}

 

 

 

 

 

 

 

 

왜 힙에 '마을(V)'을 넣나요? (도로가 아니라?)

프림 알고리즘의 핵심 목표는 **"아직 우리 팀이 아닌 '마을(정점)'들을 하나씩 포섭하는 것"**입니다.

• 마을 중심의 사고: 우리는 "어떤 도로가 제일 싼가?"를 찾는 게 아니라, **"아직 안 들어온 마을들 중에, 우리 팀이랑 가장 가깝게 붙어있는 '마을'이 누구인가?"**를 찾고 싶은 겁니다.
• 중복 제거: 한 마을에 연결된 도로가 10개라고 해서 힙에 도로 10개를 다 넣을 필요가 없습니다. 그 마을 입장에서는 가장 싼 도로 하나만 알고 있으면 팀에 합류할 수 있거든요.

 

 

 

 

 

 

while (F에 속한 에지의 개수 < n-1) { ... }

• 중요 포인트: 정점이 n개일 때, 모든 점을 연결하는 가장 효율적인 선의 개수는 무조건 **n-1**개입니다. 그래서 선이 n-1개가 될 때까지만 반복합니다

 

 

 

 

 

 

프림, 크루스칼

 

 

 

다익스트라는 갱신하는 부분만 좀 다르고 프림이랑 비슷해서 n**2