Minimum Spanning Tree in JAVA

বন্ধুরা অনেক আগে থেকে ফ্রিলান্সিং করলেও আমি করি নাই। আমার ইচ্ছা ছিল আগে প্রোফাইল ভাল করব যাতে বিড করলেই কাজ পাই। গত কাল রাতে হটাত ব্রাওজার এর বুকমার্ক দেখতে দেখতে হটাত চোখ পড়লো Ezdia নামক একটি সাইট এ। ঢুকলাম । প্রথমেই যার ওপর চোখ পড়ল তা হল minimum spanning tree এর implementation JAVA দিয়ে করতে হবে। ভাবলাম কোড তো C++ এ করাই আসে।JAVA তে convert করতে র কত সময় লাগবে। Bid করলাম । কাজ টা পেয়েও গেলাম। JAVA অনেকদিন দেখি নাই।তাই ভুলে গেসিলাম কিছু জিনিস। তাই করতে কিছুটা সময় বেসি লাগল। সব মিলিয়ে ২.৫০ ঘণ্টায় কাজ টা delivery দিলাম।

যাই হোক,কাজটা client এর পছন্দও হল। কিন্তু এখন পর্যন্ত উনি আমাকে pay করেন নাই। প্রথম কাজেই ধরা খাইলাম। ব্যাপার না। আরও হবে। আপাতত সেই কাজ তাই আপনাকে দেখাচ্ছি।

updater after 2 days
দেরীতে হলেও ফিডব্যাক পাওয়া গেল।টাকাও।

Here is the input/output format

Input

Input starts with an integer T, denoting the number of test cases.

Each case begins with an integer n denoting the number of nodes. Then there will be n lines, each having n space separated integers, denoting the lengths of two connected nodes. Each length will be between 0 and 100.

Output:
If generating a tree is impossible ,then output is -1 else the minimal cost.

Example:

Input:
3

2
27 26
1 52

4
0 10 10 0
0 0 1 1
0 0 0 2
0 0 0 0

4
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0

Output:
Case 1: 105
Case 2: 12
Case 3: -1

[code]

import java.util.*;

class edge {

public int dist;
int st, end;

edge(int i, int j, int k) {
this.st = i;
this.end = j;
this.dist = k;
}
};

class exe {

public edge road[] = new edge[3000];
edge ce;
int arr[][] = new int[52][52];
int rank[] = new int[52];
int par[] = new int[52];
double ans = 0;
int min1 = 0, max1 = 0;
int cost;
int C, R, cnt, E;

int find(int i) {
if (i != par[i]) {
par[i] = find(par[par[i]]);
}
return par[i];
}

void link(int x, int y) {
if (rank[x] > rank[y]) {
par[y] = x;
} else {
par[x] = y;
if (rank[x] == rank[y]) {
rank[y]++;
}
}

}

void kruskal() {
int i = 0, j = 0, u, v, flag = 0;
System.out.println("Tree diagram is ");
for (i = 0; j < C – 1 && i < E; i++) {
u = find(road[i].st);
v = find(road[i].end);
if (u == v) {
continue;
}
link(u, v);
flag = 1;
j++;
min1 += road[i].dist;

System.out.println(road[i].st + "->" + road[i].end + " cost is " + road[i].dist);

}
if (j < C – 1) {
System.out.println(-1);
} else {
//System.out.println(max1-min1);
System.out.println("Minimal Cost is " + min1);
}

} //krus

public exe() {

int i, j, k, T, cs = 0;

Scanner s = new Scanner(System.in);

T = s.nextInt();

while (true) {
if (T == 0) {
break;
}

C = s.nextInt();

for (i = 1; i <= C; i++) {
par[i] = i;
rank[i] = 0;
}

k = 0;
max1 = 0;
for (i = 1; i <= C; i++) {
for (j = 1; j <= C; j++) {
arr[i][j] = s.nextInt();

if (arr[i][j] != 0 && i != j) {
road[k] = new edge(i, j, arr[i][j]);
k++;
}
max1 += arr[i][j];
}
}

E = k;
for (i = 0; i < E – 1; i++) {
for (j = i + 1; j < E; j++) {
if (road[i].dist > road[j].dist) {
ce = road[i];
road[i] = road[j];
road[j] = ce;
}

}
}

min1 = 0;

System.out.print("Case " + (++cs) + ": ");
kruskal();

T–;
} // while

}
}//class exe

public class Ezdia1 {

public static void main(String ars[]) {
try {
exe object = new exe();
} catch (Exception p) {
}

}
//main
}//class

[/code]

ধন্যবাদ সবাইকে।

One Reply to “Minimum Spanning Tree in JAVA”

Leave a Reply

Your email address will not be published. Required fields are marked *