{"id":134,"date":"2011-11-09T15:40:32","date_gmt":"2011-11-09T09:40:32","guid":{"rendered":"http:\/\/ujjalruet.wordpress.com\/?p=134"},"modified":"2011-11-09T15:40:32","modified_gmt":"2011-11-09T09:40:32","slug":"minimum-spanning-tree-in-java","status":"publish","type":"post","link":"https:\/\/blog.ujjal.net\/?p=134","title":{"rendered":"Minimum Spanning Tree in JAVA"},"content":{"rendered":"

\u09ac\u09a8\u09cd\u09a7\u09c1\u09b0\u09be \u0985\u09a8\u09c7\u0995 \u0986\u0997\u09c7 \u09a5\u09c7\u0995\u09c7 \u09ab\u09cd\u09b0\u09bf\u09b2\u09be\u09a8\u09cd\u09b8\u09bf\u0982 \u0995\u09b0\u09b2\u09c7\u0993 \u0986\u09ae\u09bf \u0995\u09b0\u09bf \u09a8\u09be\u0987\u0964 \u0986\u09ae\u09be\u09b0 \u0987\u099a\u09cd\u099b\u09be \u099b\u09bf\u09b2 \u0986\u0997\u09c7 \u09aa\u09cd\u09b0\u09cb\u09ab\u09be\u0987\u09b2 \u09ad\u09be\u09b2 \u0995\u09b0\u09ac \u09af\u09be\u09a4\u09c7 \u09ac\u09bf\u09a1 \u0995\u09b0\u09b2\u09c7\u0987 \u0995\u09be\u099c \u09aa\u09be\u0987\u0964 \u0997\u09a4 \u0995\u09be\u09b2 \u09b0\u09be\u09a4\u09c7 \u09b9\u099f\u09be\u09a4 \u09ac\u09cd\u09b0\u09be\u0993\u099c\u09be\u09b0 \u098f\u09b0 \u09ac\u09c1\u0995\u09ae\u09be\u09b0\u09cd\u0995 \u09a6\u09c7\u0996\u09a4\u09c7 \u09a6\u09c7\u0996\u09a4\u09c7 \u09b9\u099f\u09be\u09a4 \u099a\u09cb\u0996 \u09aa\u09dc\u09b2\u09cb Ezdia \u09a8\u09be\u09ae\u0995 \u098f\u0995\u099f\u09bf \u09b8\u09be\u0987\u099f \u098f\u0964 \u09a2\u09c1\u0995\u09b2\u09be\u09ae \u0964 \u09aa\u09cd\u09b0\u09a5\u09ae\u09c7\u0987 \u09af\u09be\u09b0 \u0993\u09aa\u09b0 \u099a\u09cb\u0996 \u09aa\u09dc\u09b2 \u09a4\u09be \u09b9\u09b2 minimum spanning tree \u098f\u09b0 implementation JAVA \u09a6\u09bf\u09df\u09c7 \u0995\u09b0\u09a4\u09c7 \u09b9\u09ac\u09c7\u0964 \u09ad\u09be\u09ac\u09b2\u09be\u09ae \u0995\u09cb\u09a1 \u09a4\u09cb C++ \u098f \u0995\u09b0\u09be\u0987 \u0986\u09b8\u09c7\u0964JAVA \u09a4\u09c7 convert \u0995\u09b0\u09a4\u09c7 \u09b0 \u0995\u09a4 \u09b8\u09ae\u09df \u09b2\u09be\u0997\u09ac\u09c7\u0964 Bid \u0995\u09b0\u09b2\u09be\u09ae \u0964 \u0995\u09be\u099c \u099f\u09be \u09aa\u09c7\u09df\u09c7\u0993 \u0997\u09c7\u09b2\u09be\u09ae\u0964 JAVA \u0985\u09a8\u09c7\u0995\u09a6\u09bf\u09a8 \u09a6\u09c7\u0996\u09bf \u09a8\u09be\u0987\u0964\u09a4\u09be\u0987 \u09ad\u09c1\u09b2\u09c7 \u0997\u09c7\u09b8\u09bf\u09b2\u09be\u09ae \u0995\u09bf\u099b\u09c1 \u099c\u09bf\u09a8\u09bf\u09b8\u0964 \u09a4\u09be\u0987 \u0995\u09b0\u09a4\u09c7 \u0995\u09bf\u099b\u09c1\u099f\u09be \u09b8\u09ae\u09df \u09ac\u09c7\u09b8\u09bf \u09b2\u09be\u0997\u09b2\u0964 \u09b8\u09ac \u09ae\u09bf\u09b2\u09bf\u09df\u09c7 \u09e8.\u09eb\u09e6 \u0998\u09a3\u09cd\u099f\u09be\u09df \u0995\u09be\u099c \u099f\u09be delivery \u09a6\u09bf\u09b2\u09be\u09ae\u0964<\/p>\n

\u09af\u09be\u0987 \u09b9\u09cb\u0995,\u0995\u09be\u099c\u099f\u09be client \u098f\u09b0 \u09aa\u099b\u09a8\u09cd\u09a6\u0993 \u09b9\u09b2\u0964 \u0995\u09bf\u09a8\u09cd\u09a4\u09c1 \u098f\u0996\u09a8 \u09aa\u09b0\u09cd\u09af\u09a8\u09cd\u09a4 \u0989\u09a8\u09bf \u0986\u09ae\u09be\u0995\u09c7 pay \u0995\u09b0\u09c7\u09a8 \u09a8\u09be\u0987\u0964 \u09aa\u09cd\u09b0\u09a5\u09ae \u0995\u09be\u099c\u09c7\u0987 \u09a7\u09b0\u09be \u0996\u09be\u0987\u09b2\u09be\u09ae\u0964 \u09ac\u09cd\u09af\u09be\u09aa\u09be\u09b0 \u09a8\u09be\u0964 \u0986\u09b0\u0993 \u09b9\u09ac\u09c7\u0964 \u0986\u09aa\u09be\u09a4\u09a4 \u09b8\u09c7\u0987 \u0995\u09be\u099c \u09a4\u09be\u0987 \u0986\u09aa\u09a8\u09be\u0995\u09c7 \u09a6\u09c7\u0996\u09be\u099a\u09cd\u099b\u09bf\u0964 <\/p>\n

updater after 2 days<\/strong>
\n\u09a6\u09c7\u09b0\u09c0\u09a4\u09c7 \u09b9\u09b2\u09c7\u0993 \u09ab\u09bf\u09a1\u09ac\u09cd\u09af\u09be\u0995 \u09aa\u09be\u0993\u09df\u09be \u0997\u09c7\u09b2\u0964\u099f\u09be\u0995\u09be\u0993\u0964<\/p>\n

\nHere is the input\/output format<\/p>\n

Input<\/p>\n

Input starts with an integer T, denoting the number of test cases.<\/p>\n

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.<\/p>\n

Output:
\nIf generating a tree is impossible ,then output is -1 else the minimal cost.<\/p>\n

Example:<\/p>\n

Input:
\n3<\/p>\n

2
\n27 26
\n1 52<\/p>\n

4
\n0 10 10 0
\n0 0 1 1
\n0 0 0 2
\n0 0 0 0<\/p>\n

4
\n0 1 0 0
\n1 0 0 0
\n0 0 0 1
\n0 0 1 0<\/p>\n

Output:
\nCase 1: 105
\nCase 2: 12
\nCase 3: -1<\/p><\/blockquote>\n

[code]<\/p>\n

import java.util.*;<\/p>\n

class edge {<\/p>\n

public int dist;
\n int st, end;<\/p>\n

edge(int i, int j, int k) {
\n this.st = i;
\n this.end = j;
\n this.dist = k;
\n }
\n};<\/p>\n

class exe {<\/p>\n

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

int find(int i) {
\n if (i != par[i]) {
\n par[i] = find(par[par[i]]);
\n }
\n return par[i];
\n }<\/p>\n

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

}<\/p>\n

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

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

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

} \/\/krus<\/p>\n

public exe() {<\/p>\n

int i, j, k, T, cs = 0;<\/p>\n

Scanner s = new Scanner(System.in);<\/p>\n

T = s.nextInt();<\/p>\n

while (true) {
\n if (T == 0) {
\n break;
\n }<\/p>\n

C = s.nextInt();<\/p>\n

for (i = 1; i <= C; i++) {
\n par[i] = i;
\n rank[i] = 0;
\n }<\/p>\n

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

if (arr[i][j] != 0 && i != j) {
\n road[k] = new edge(i, j, arr[i][j]);
\n k++;
\n }
\n max1 += arr[i][j];
\n }
\n }<\/p>\n

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

}
\n }<\/p>\n

min1 = 0;<\/p>\n

System.out.print("Case " + (++cs) + ": ");
\n kruskal();<\/p>\n

T–;
\n } \/\/ while<\/p>\n

}
\n}\/\/class exe<\/p>\n

public class Ezdia1 {<\/p>\n

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

}
\n \/\/main
\n}\/\/class<\/p>\n

[\/code]<\/p>\n

\u09a7\u09a8\u09cd\u09af\u09ac\u09be\u09a6 \u09b8\u09ac\u09be\u0987\u0995\u09c7\u0964<\/p>\n","protected":false},"excerpt":{"rendered":"

\u09ac\u09a8\u09cd\u09a7\u09c1\u09b0\u09be \u0985\u09a8\u09c7\u0995 \u0986\u0997\u09c7 \u09a5\u09c7\u0995\u09c7 \u09ab\u09cd\u09b0\u09bf\u09b2\u09be\u09a8\u09cd\u09b8\u09bf\u0982 \u0995\u09b0\u09b2\u09c7\u0993 \u0986\u09ae\u09bf \u0995\u09b0\u09bf \u09a8\u09be\u0987\u0964 \u0986\u09ae\u09be\u09b0 \u0987\u099a\u09cd\u099b\u09be \u099b\u09bf\u09b2 \u0986\u0997\u09c7 \u09aa\u09cd\u09b0\u09cb\u09ab\u09be\u0987\u09b2 \u09ad\u09be\u09b2 \u0995\u09b0\u09ac \u09af\u09be\u09a4\u09c7 \u09ac\u09bf\u09a1 \u0995\u09b0\u09b2\u09c7\u0987 \u0995\u09be\u099c \u09aa\u09be\u0987\u0964 \u0997\u09a4 \u0995\u09be\u09b2 \u09b0\u09be\u09a4\u09c7 \u09b9\u099f\u09be\u09a4 \u09ac\u09cd\u09b0\u09be\u0993\u099c\u09be\u09b0 \u098f\u09b0 \u09ac\u09c1\u0995\u09ae\u09be\u09b0\u09cd\u0995 \u09a6\u09c7\u0996\u09a4\u09c7 \u09a6\u09c7\u0996\u09a4\u09c7 \u09b9\u099f\u09be\u09a4 \u099a\u09cb\u0996 \u09aa\u09dc\u09b2\u09cb Ezdia \u09a8\u09be\u09ae\u0995 \u098f\u0995\u099f\u09bf \u09b8\u09be\u0987\u099f \u098f\u0964 \u09a2\u09c1\u0995\u09b2\u09be\u09ae \u0964 \u09aa\u09cd\u09b0\u09a5\u09ae\u09c7\u0987 \u09af\u09be\u09b0 \u0993\u09aa\u09b0 \u099a\u09cb\u0996 \u09aa\u09dc\u09b2 \u09a4\u09be \u09b9\u09b2 minimum spanning tree \u098f\u09b0 implementation JAVA \u09a6\u09bf\u09df\u09c7 \u0995\u09b0\u09a4\u09c7 … <\/p>\n

Continue reading “Minimum Spanning Tree in JAVA”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9,10],"tags":[],"class_list":["post-134","post","type-post","status-publish","format-standard","hentry","category-programming-with-java","category-tutorial"],"_links":{"self":[{"href":"https:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/posts\/134","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=134"}],"version-history":[{"count":0,"href":"https:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/posts\/134\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=134"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=134"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}