최소 스패팅 트리 와 다익스트라 정리

오랜만에 문제를 풀다가 헷갈리는 부분들이 있어서 정리를 해본다.. 

 

 

최소 스패팅 트리

• 모든 노드에서 가중치 합이 가장 작은 트리를 만드는 것

크루스칼 vs 프림

크루스칼 알고리즘

• 간선의 길이가 짧은 것 부터 시작해서 사이클이 생기지 않게 간선을 추가하는 방식

프림 알고리즘

• 한 시작 노드를 정한 후에 노드에 연결된 간선 중 최소 값을 선택하여 확장해나가는 방식

 

크루스칼 알고리즘 구현 

// 유니온 파인트도 사이클 체크
int findparent(int x){
    if(x==findparent(parent[x])){
        return x;
    }else{
        return parent[x]=findparent(parent[x]);
    }
}
void uni(int x,int y){
    x=findparent(x);
    y=findparent(y);
    parent[y]=x;
}
void solution(){
    
    for(int i=1; i<=n; i++) parents[i] = i;
    sort(edges.begin(), edges.end(), cmp);
    
    for(int i=0; i<edges.size(); i++){
        int node1 = edges[i].second.first;
        int node2 = edges[i].second.second;
        int cost = edges[i].first;  
        
        if(get_parent(node1) != get_parent(node2)){. // 사이클이 안만들어지면 간선 추가
            union_parents(node1, node2);
            total -= cost;       //total은 총 가중치 합 
        }
    }
    
}

 

 

프림 알고리즘 구현(우선순위 큐)

void prim(int start){
    visited[start]=true;    //오름차순 우선순위 큐 사용
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    for(int i=0;i<v[start].size();i++){
        int dis=v[start][i].first;
        int node=v[start][i].second;
        pq.push({dis,node});   //시작 노드에서 이어지는 간선들 큐에 삽입
    }
    while(!pq.empty()){
        int dis=pq.top().first;
        int node=pq.top().second;
        pq.pop();
        if(visited[node]) continue;  //이미 방문한 노드는 넘어간다.
        ans+=dis;             // 추가 되는 가중치 합을 더함 -> 최소 가중치 트리 
        visited[node]=true;
        for(int i=0;i<v[node].size();i++){
            int nextdis=v[node][i].first;
            int nextnode=v[node][i].second;
            if(!visited[nextnode]){
                pq.push({nextdis,nextnode});
            }
        }
    }
}

 

 

 

다익스트라 vs 최소 스패닝 트리 (크루스칼 , 프림)

다익스트라

• 한 노드에서 다른 노드 한점 까지의 최소 노드를 구하는 것이다.

최소 스패닝 트리

• 모든 노드에서 가중치 합이 가장 작은 트리를 만드는 것

 

다익스트라 알고리즘 구현 (방문노드 체크는 필요하지 않다 →최소 로 갱신이 필요하기 때문)

void dijkstra(int start){
    dist[start]=0;
    priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push({dist[start],start});
    while(!q.empty()){
        int distNow = q.top().first;
        int node = q.top().second;
        q.pop();
        
        if(dist[node]<distNow) continue;    //방문할 노드 가중치가 현재 가중치보다 작으면 넘어감
        for(int i=0;i<arr[node].size();i++){
            int distNext = arr[node][i].first;
            int nodeNext = arr[node][i].second;
            if( dist[nodeNext]> dist[node]+distNext){
                dist[nodeNext] = dist[node] + distNext;
                q.push({dist[nodeNext],nodeNext});
            }
        }
    }
}