Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 016ea51

Browse files
Add files via upload
1 parent 7efc0de commit 016ea51

File tree

2 files changed

+174
-0
lines changed

2 files changed

+174
-0
lines changed

‎GRAPH 2/KRUSKAL'S ALGO.txt‎

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
import java.util.*;
2+
import java.io.*;
3+
public class Solution {
4+
5+
public static void main(String[] args) {
6+
Scanner sc = new Scanner(System.in);
7+
int n = sc.nextInt();
8+
int e = sc.nextInt();
9+
int t1,t2,t3;
10+
EdgeClass [] edge = new EdgeClass[e];
11+
for(int i=0;i<e;i++)
12+
{
13+
t1 = sc.nextInt();
14+
t2 = sc.nextInt();
15+
t3 = sc.nextInt();
16+
edge[i] = new EdgeClass(t1,t2,t3);
17+
}
18+
Arrays.sort(edge, new Comparator<EdgeClass>()
19+
{
20+
@Override
21+
public int compare(EdgeClass o1, EdgeClass o2)
22+
{
23+
return o1.cost.compareTo(o2.cost) ;
24+
}
25+
});
26+
EdgeClass [] ans = new EdgeClass[n-1];
27+
int parent [] = new int[n];
28+
for(int i=0;i<n;i++)
29+
{
30+
parent[i] =i;
31+
}
32+
for(int i=0,j=0;i<e && j<n-1;i++)
33+
{
34+
t1 = edge[i].u;
35+
t2 = edge[i].v;
36+
t3 = edge[i].cost;
37+
if(unionFind(parent,t1,t2)==true)
38+
{
39+
ans[j] = new EdgeClass(t1,t2,t3);
40+
j++;
41+
}
42+
}
43+
for(int i =0;i<n-1;i++)
44+
{
45+
if(ans[i].u<ans[i].v)
46+
System.out.println(ans[i].u+" "+ans[i].v+" "+ans[i].cost);
47+
else
48+
System.out.println(ans[i].v+" "+ans[i].u+" "+ans[i].cost);
49+
50+
}
51+
52+
53+
54+
}
55+
56+
public static boolean unionFind(int []parent, int start, int end)
57+
{
58+
int n = parent.length-1;
59+
int pre = parent[end];
60+
61+
62+
while(parent[start] == parent [end])
63+
{
64+
start = parent[start];
65+
n--;
66+
if(n<0)
67+
break;
68+
}
69+
if(n<0)
70+
return false;
71+
else
72+
{
73+
int cur = parent[start];
74+
for(int i=0;i<parent.length;i++)
75+
{
76+
if(parent[i]==pre)
77+
parent[i] = cur;
78+
}
79+
return true;
80+
}
81+
}
82+
83+
84+
public static class EdgeClass
85+
{
86+
Integer u,v,cost;
87+
EdgeClass(int u, int v, int cost)
88+
{
89+
this.u=u;
90+
this.v=v;
91+
this.cost = cost;
92+
}
93+
94+
}
95+
}

‎GRAPH 2/PRIM'S ALGO.txt‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
import java.util.Scanner;
2+
3+
public class Solution {
4+
5+
public static void main(String[] args) {
6+
Scanner sc = new Scanner(System.in);
7+
int n = sc.nextInt();
8+
int e = sc.nextInt();
9+
int graph [][] = new int [n][n];
10+
int t1,t2,cost;
11+
int []weight= new int[n];
12+
while(e>0)
13+
{
14+
e--;
15+
t1=sc.nextInt();
16+
t2=sc.nextInt();
17+
cost = sc.nextInt();
18+
graph[t1][t2] = cost;
19+
graph[t2][t1] = cost;
20+
21+
}
22+
int [] parent = new int[n];
23+
for(int i=0;i<n;i++)
24+
{
25+
weight[i] = Integer.MAX_VALUE;
26+
}
27+
boolean [] visited = new boolean [n];
28+
parent[0] =-1;
29+
weight[0] =0;
30+
int source = 0;
31+
int count, min_edge;
32+
int next_source=0;
33+
34+
for(int i=1;i<n;i++)
35+
{
36+
source = findMinVertex(weight,visited);
37+
visited[source]=true;
38+
39+
for(int j=0;j<n;j++)
40+
{
41+
if(graph[source][j]>0 && visited[j]==false && weight[j] > graph[source][j])
42+
{
43+
weight[j] = graph[source][j];
44+
parent[j] = source;
45+
46+
47+
}
48+
}
49+
}
50+
51+
for(int i = 1;i<n;i++)
52+
{
53+
if(i< parent[i])
54+
System.out.println(i+" "+parent[i]+" "+weight[i]);
55+
else
56+
System.out.println(parent[i]+" "+i+" "+weight[i]);
57+
58+
}
59+
60+
61+
}
62+
public static int findMinVertex(int []weight, boolean[] visited)
63+
{
64+
int v, min_edge,n;
65+
n=weight.length;
66+
v=0;
67+
min_edge = Integer.MAX_VALUE;
68+
for(int i=0;i<n;i++)
69+
{
70+
if(visited[i] == false && min_edge > weight[i])
71+
{
72+
v = i;
73+
min_edge = weight[i];
74+
}
75+
}
76+
return v;
77+
78+
}
79+
}

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /