그래프 관련 알고리즘

Kruskal 알고리즘

Union & Find를 사용하여 연결되어있는지를 확인하는 알고리즘이다.

struct Edge{
    int v1, v2, val;
    Edge(int a, int b, int c){
        v1 = a;
        v2 = b;
        val = c;
    }
    bool operator< (const Edge& v) const{
        return val<v.val;
    }
};
int unf[26];
int Find(int a){
    if(unf[a] == a) return a;
    else return unf[a] = Find(unf[a]);
}

void Union(int a, int b){
    a= Find(a);
    b = Find(b);
    if(a != b){
        unf[a] = b;
    }
}
int main(){
    freopen("input.txt","rt",stdin);
    int v = 0, e = 0 , c = 0;
    int n = 0, m = 0;
    scanf("%d %d",&n, &m);
    vector<Edge> a;
    int res = 0;
    
    for(int i=1; i<=n; i++){
        unf[i]= i;
    }
    for(int i=1; i<=m; i++){
        scanf("%d %d %d",&v, &e, &c);
        a.push_back(Edge(v,e,c));
    }
    sort(a.begin(), a.end());
    for(int i=0; i<m; i++){
        
        if(Find(a[i].v1)!=Find(a[i].v2)){
            printf("%d %d %d\n",a[i].v1,a[i].v2,a[i].val);
            res+=a[i].val;
            Union(a[i].v1, a[i].v2);
        }
        
    }
    printf("%d\n",res);
    return 0;
}

Priority_Queue 사용

#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int ch[31];
struct Edge{
    int e;
    int val;
    Edge(int a, int b){
        e = a;
        val = b;
    }
    bool operator<(const Edge &b) const {
        return val > b.val;
    }
};

int main(){
    freopen("input.txt","rt",stdin);
    priority_queue<Edge> Q;
    vector<pair<int, int> > map[30];
    int i, n, m, a, b, c, res = 0;
    scanf("%d %d",&n, &m);
    for(i=1; i<=m; i++){
        scanf("%d %d %d",&a, &b, &c);
        map[a].push_back(make_pair(b,c));
        map[b].push_back(make_pair(a,c));
    }

    Q.push(Edge(1,0));
    while(!Q.empty()){
        Edge tmp = Q.top();
        int v = tmp.e;
        int cost = tmp.val;
        if(ch[v] == 0){
            res+=cost;
            ch[v] = 1;
            for(i=0; i<map[v].size(); i++){
                Q.push(Edge(map[v][i].first, map[v][i].second));
            }
        }
    }

    printf("%d\n",res);

    return 0;
}

다익스트라 알고리즘

한정점에서 다른 모든 정점으로의 최소거리를 구하는 알고리즘이다.

#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

struct Edge{
    int vex;
    int dis;
    Edge(int a, int b){
        vex = a;
        dis = b;
    }
    bool operator<(const Edge &b) const {
        return dis > b.dis;
    }
};

int main(){
    freopen("input.txt","rt",stdin);
    priority_queue<Edge> pQ;
    vector<pair<int, int> > graph[30];
    int i, n, m, a, b, c;
    cin>>n>>m;
    vector<int> dist(n+1, 2147000000);
    for(i=1; i<=m; i++){
        cin>>a>>b>>c;
        graph[a].push_back(make_pair(b,c));
    }
    pQ.push(Edge(1,0));
    dist[1] = 0;
    while(!pQ.empty()){
        int now = pQ.top().vex;
        int cost = pQ.top().dis;
        pQ.pop();
        if(cost>dist[now]) continue;
        for(i=0; i<graph[now].size(); i++){
            int next = graph[now][i].first;
            int nextDis = cost + graph[now][i].second;
            if(dist[next] > nextDis){
                dist[next] = nextDis;
                pQ.push(Edge(next, nextDis));
            }
        }
    }
    return 0;
}