• Buat teman - teman yang kesulitan mengatur tampilan blog karena ada bagian yang tertalu panjang seperti blog archive...
  • Bagi kalian yang suka menggunakan selotip/pita perekat hanya untuk menempelkan benda...
  • Setelah bertemu dengan mata kuliah Sistem Operasi, saya baru tahu apa itu konkurensi...
  • Berikut dibawah ini merupakan daftar perintah-perintah yang ada pada command prompt dari A-X...
  • Pada mata pelajaran SMP atau SMA ada masalah tentang Transformasi Geometri. Jangan salah, ternyata Transformasi Geometri...

Wednesday 9 May 2012

Algoritma Kruskal : Minimum Spanning Tree C Programming




















#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxVertices 1000
#define maxEdges 1000000
int graph[maxVertices][maxVertices];
/* Input graph must be undirected,weighted and connected*/
typedef struct Edge
{
       
int from,to,weight;
}Edge;
int compare(const void * x,const void * y)
{
       
return (*(Edge *)x).weight - (*(Edge *)y).weight;
}
Edge E[maxEdges];
int parent[maxVertices];
void init(int vertices)
{
       
int iter=0;
       
for(iter=0;iter<vertices;iter++)
       
{
                parent
[iter]=-1;
       
}

}
int Find(int vertex)
{
       
if(parent[vertex]==-1)return vertex;
       
return parent[vertex] = Find(parent[vertex]); /* Finding its parent as well as updating the parent
                                                         of all vertices along this path */

}
int Union(int parent1,int parent2)
{
       
/* This can be implemented in many other ways. This is one of them */
        parent
[parent1] = parent2;
}
void Kruskal(int vertices,int edges)
{
        memset
(graph,-1,sizeof(graph)); /* -1 represents the absence of edge between them */
       
/* Sort the edges according to the weight */
        qsort
(E,edges,sizeof(Edge),compare);
       
/* Initialize parents of all vertices to be -1.*/
        init
(vertices);
       
int totalEdges = 0,edgePos=0,from,to,weight;
       
Edge now;
       
while(totalEdges < vertices -1)
       
{
               
if(edgePos==edges)
               
{
                       
/* Input Graph is not connected*/
                        exit
(0);
               
}
                now
= E[edgePos++];
                from
= now.from;
                to
= now.to;
                weight
=now.weight;
               
/* See If vetices from,to are connected. If they are connected do not add this edge. */
               
int parent1 = Find(from);
               
int parent2 = Find(to);
               
if(parent1!=parent2)
               
{
                        graph
[from][to] = weight;
                       
Union(parent1,parent2);
                        totalEdges
++;
               
}
       
}

}
int main()
{
       
int vertices,edges;
        scanf
("%d%d",&vertices,&edges);
       
int iter,jter;
       
int from,to,weight;
       
for(iter=0;iter<edges;iter++)
       
{
                scanf
("%d%d%d",&from,&to,&weight);
                E
[iter].from = from;
                E
[iter].to = to;
                E
[iter].weight = weight;
       
}
       
/* Finding MST */
       
Kruskal(vertices,edges);
       
/* Printing the MST */
       
for(iter=0;iter<vertices;iter++)
       
{
               
for(jter=0;jter<vertices;jter++)
               
{
                       
if(graph[iter][jter]!=-1)
                       
{
                                printf
("Vertex %d and %d, weight %d\n",iter,jter,graph[iter][jter]);
                       
}
               
}
       
}
       
return 0;
}

1 komentar:

Masyonow.com said...

mohon maaf mas, terus terang mas aku gak paham tentang ilmu yang di jelaskan diposting ini. saya hanya mau tanya mungkin mas boy tau dan paham. tentang blog saya lodingnya lama karena conect ke m[.]addthisedge[.]com dan karena itulah saya nyasar ke blog mas boy. ketika saya cari tentang m[.]addthisedge[.]com di google search disitu muncul blog mas boy ini. SAYA HANYA INGIN TAU MAS SEBENARNYA m[.]addthisedge[.]com ITU APA? Kok bisa ambulate loding blog saya menjadi lama. MOHON BALASANNYA DI EMAIL SAYA masyonow@gmail.com
SILAHKAN KOMENT INI JIKA TIDAK DIKEHENDAKI BISA DIHAPUS YANG PENTING SAYA TUNGGU BALASANNYA DI EMAIL SAYA MAKASIH MAS BOY.

Post a Comment

Catatan Harian si Boy ©Template Blogger Green by Dicas Blogger.

To Up