Minimum Spanning Tree यानि Kruskal Algorithm

#include <iostream>
using namespace std;
int main() {
	int edges[][3] = {{0,1,4},{1,2,2},{0,2,5}};
	cout << "MST: connect all vertices, no cycles, minimum total weight";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[][] edges = {{0,1,4},{1,2,2},{0,2,5}};
		System.out.println("MST: connect all vertices, no cycles, minimum total weight");
	}
}

edges = [(0,1,4),(1,2,2),(0,2,5)]
print("MST: connect all vertices, no cycles, minimum total weight")

#include <stdio.h>
int main() {
	int edges[3][3] = {{0,1,4},{1,2,2},{0,2,5}};
	printf("MST: connect all vertices, no cycles, minimum total weight");
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	vector<vector<int>> edges = {{0,1,4},{1,2,2},{0,2,5}};
	sort(edges.begin(), edges.end(), [](auto&a, auto&b){ return a[2] < b[2]; });
	cout << "Cheapest edge first: " << edges[0][0] << "-" << edges[0][1] << " (w=" << edges[0][2] << ")";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[][] edges = {{0,1,4},{1,2,2},{0,2,5}};
		Arrays.sort(edges, (a,b) -> a[2]-b[2]);
		System.out.println("Cheapest edge first: " + edges[0][0] + "-" + edges[0][1] + " (w=" + edges[0][2] + ")");
	}
}

edges = [[0,1,4],[1,2,2],[0,2,5]]
edges.sort(key=lambda e: e[2])
print(f"Cheapest edge first: {edges[0][0]}-{edges[0][1]} (w={edges[0][2]})")

#include <stdio.h>
int main() {
	int edges[3][3] = {{0,1,4},{1,2,2},{0,2,5}};
	for (int i = 0; i < 3; i++)
		for (int j = i+1; j < 3; j++)
			if (edges[j][2] < edges[i][2]) { int t[3]; for(int k=0;k<3;k++){t[k]=edges[i][k];edges[i][k]=edges[j][k];edges[j][k]=t[k];} }
	printf("Cheapest edge first: %d-%d (w=%d)", edges[0][0], edges[0][1], edges[0][2]);
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int parent[3] = {0,1,2};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
int main() {
	int u = 0, v = 1;
	if (find(u) != find(v)) { cout << "Different sets, add edge, union them"; parent[find(u)] = find(v); }
	else cout << "Same set already, edge would create a cycle -- skip";
	return 0;
}

public class Main {
	static int[] parent = {0,1,2};
	static int find(int x) { return parent[x]==x ? x : find(parent[x]); }
	public static void main(String[] args) {
		int u = 0, v = 1;
		if (find(u) != find(v)) { System.out.print("Different sets, add edge, union them"); parent[find(u)] = find(v); }
		else System.out.print("Same set already, edge would create a cycle -- skip");
	}
}

parent = [0, 1, 2]
def find(x):
    return x if parent[x] == x else find(parent[x])
u, v = 0, 1
if find(u) != find(v):
    print("Different sets, add edge, union them", end="")
    parent[find(u)] = find(v)
else:
    print("Same set already, edge would create a cycle -- skip", end="")

#include <stdio.h>
int parent[3] = {0,1,2};
int find(int x) { return parent[x]==x ? x : find(parent[x]); }
int main() {
	int u = 0, v = 1;
	if (find(u) != find(v)) { printf("Different sets, add edge, union them"); parent[find(u)] = find(v); }
	else printf("Same set already, edge would create a cycle -- skip");
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
	cout << "5 cities: pick cheapest road, then next cheapest that doesn't reconnect two linked cities";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("5 cities: pick cheapest road, then next cheapest that doesn't reconnect two linked cities");
	}
}

print("5 cities: pick cheapest road, then next cheapest that doesn't reconnect two linked cities")

#include <stdio.h>
int main() {
	printf("5 cities: pick cheapest road, then next cheapest that doesn't reconnect two linked cities");
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
	cout << "Kruskal: O(E log E) dominated by sorting edges, union-find is nearly constant with path compression";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Kruskal: O(E log E) dominated by sorting edges, union-find is nearly constant with path compression");
	}
}

print("Kruskal: O(E log E) dominated by sorting edges, union-find is nearly constant with path compression")

#include <stdio.h>
int main() {
	printf("Kruskal: O(E log E) dominated by sorting edges, union-find is nearly constant with path compression");
	return 0;
}

Login to try C/C++/Java code in the editor