Program Kruskal C++ ~ Tips Watan

Senin, 09 April 2012

Program Kruskal C++

20.43 watan 2 comments

Kruskal adalah salah satu metode untuk mencari Minimum Spanning Tree.
Dengan menggunakan bahasa pemrograman c++, kita bisa membuat program mencari MST dengan algoritma kruskal.
Ini source codenya.
Silahkan copy-paste. Kemudian kompile deh...

/*********************
Program Kruskal Dengan C++
u : variabel untuk menampung verteks awal
v : variabel untuk menampung verteks akhir
w : variabel untuk menampung panjang edge yang menghubungi verteks awal dengan verteks akhir
*********************/

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define edge pair< int, int >
#define MAX 1000

vector< pair< int, edge > > GRAPH, MST;
int verteks, edg, parent[MAX], total ;

int findset(int , int );
void cetak();
void kruskal();
void reset();

int main()
{
    int i, u, v, w;
    printf("Masukkan jumlah verteks : ");
    scanf("%d", &verteks);
    printf("Masukkan jumlah edge : ");
    scanf("%d", &edg);
    reset();
    printf("Masukkan verteks awal, verteks akhir, dan panjang edge-nya : \n");
    for(i=0; i<edg; i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        GRAPH.push_back(pair< int, edge >(w, edge(u, v)));
    }
    kruskal();
    cetak();

    return 0;
}

int findset(int x, int *parent)
{
    if(x != parent[x])
        parent[x] = findset(parent[x], parent);
    return parent[x];
}

void kruskal()
{
    int i, pu, pv;
    sort(GRAPH.begin(), GRAPH.end()); //fungsi untuk mengurutkan dari kecil ke besar.
    for(i=total=0; i<edg; i++)
    {
        pu = findset(GRAPH[i].second.first, parent);
        pv = findset(GRAPH[i].second.second, parent);
        if(pu != pv)
        {
            MST.push_back(GRAPH[i]);
            total += GRAPH[i].first;
            parent[pu] = parent[pv];
        }
    }
}

void reset()
{
    for(int i=1; i<=verteks; i++) parent[i] = i;
}

void cetak()
{
    int i, ukuran;
    ukuran = MST.size();
    for(i=0; i<ukuran; i++)
    {
        printf("( %d", MST[i].second.first);
        printf(", %d )", MST[i].second.second);
        printf(": %d\n", MST[i].first);
    }
    printf("Minimum cost: %d\n", total);
}