Byte-Sized-Chunks Graph Algorithms and Problems in Java by Loonycorn
A company called Loonycorn, which offers online courses in computer science and related fields, offers a course called Byte-sized-chunks graph algorithms and problems in Java. This course teaches students how to use Java to solve graph algorithms and problems.
For programmers, data analysts, and computer scientists, graph algorithms and problems are crucial resources. They address various issues, such as social network analysis, travel planning, and recommendation engines.
The course, Byte-sized-chunks graph algorithms and problems in Java, are divided into sections, each focusing on a different subject. Students are introduced to graphs and graph algorithms, such as graph traversal, shortest routes, and minimal spanning trees, in the first half of the course.
The Bellman-Ford formula
Another shortest-path approach for determining the shortest route between two graph vertices is the Bellman-Ford algorithm. This approach can handle negative edge weight graphs, but negative cycles cannot.
The Bellman-Ford method continually relaxes the graph's edges, as explained. Except for the beginning vertex, initially set to 0, all distances are initially set to infinity. As a shorter path is discovered, the algorithm iterates through the graph's edges, updating the distances. To guarantee that all potential pathways are investigated, this method is performed V-1 times, where V is the number of vertices in the graph.
The Bellman-Ford algorithm repeatedly relaxes the graph's edges, as explained. Except for the beginning vertex, initially set to 0, all distances are initially set to infinity. As a shorter path is discovered, the algorithm iterates through the graph's edges, updating the distances. To guarantee that all potential pathways are investigated, this method is performed V-1 times, where V is the number of vertices in the graph.
BellmanFord.java
import java.util.*;
public class BellmanFord {
public static int[] bellmanFord(int numVertices, int[][] edges, int source) {
int[] distances = new int[numVertices];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[source] = 0;
for (int j = 0; j < numVertices - 1; j++) {
for (int[] e : edges) {
int u = e[0];
int v = e[1];
int weight = e[2];
if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
}
}
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int weight = edge[2];
if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
throw new IllegalArgumentException("Negative weight cycle detected");
}
}
return distances;
}
public static void main(String[] args) {
int numVertices = 5;
int[][] edges = {
{0, 1, 4},
{0, 2, 3},
{1, 3, 2},
{1, 4, 5},
{2, 3, 5},
{2, 4, 6},
{3, 4, 1}
};
int source = 0;
int[] distances = bellmanFord(numVertices, edges, source);
System.out.println(Arrays.toString(distances)); // [0, 4, 3, 6, 5]
}
}
Output
[0, 4, 3, 6, 7]
Explanation
Vertex 0 is designated as the source in the main method's definition of a tiny directed graph with five vertices and seven edges. We next use the bellmanFord technique with the source vertex, the number of vertices, and the edges, and output the calculated distances between each vertex. The expected output is [0, 4, 3, 6, 5]. An IllegalArgumentException would be raised if the graph had a negative weight cycle.
Topological Sort
Topological sorting is used to arrange the vertices of a directed acyclic graph (DAG) in a certain hierarchy. This method is frequently employed in scheduling issues, such as task scheduling in software development projects.
Adding vertices to the sorted list that don't have any incoming edges is part of the topological sort method, as explained above. The procedure is continued until all vertices are sorted after these vertices have been added, their outgoing edges have been eliminated, and so forth.
Pseudo Code
- Create a stack from scratch to record the vertices in the order of their completion timings.
- DFS operations should be carried out from each unexplored vertex in the graph.
- Mark each vertex as visited during DFS and recursively explore its neighbouring vertices.
- Push a vertex onto the stack once it has been thoroughly studied.
- Pop vertices from the stack once each vertex has been investigated to provide a topological ordering.
TopologicalSort.java
import java.util.*;
public class TopologicalSort {
public static List<Integer> topologicalSort(int numVertices, List<List<Integer>> adjList) {
int[] in = new int[numVertices];
for (List<Integer> neigh : adjList) {
for (int neighbor : neigh) {
in[neighbor]++;
}
}
Queue<Integer> queue = new LinkedList<>();
for (int vertex = 0; vertex < numVertices; vertex++) {
if (in[vertex] == 0) {
queue.add(vertex);
}
}
List<Integer> sortedList = new ArrayList<>();
while (!queue.isEmpty()) {
int vertex = queue.remove();
sortedList.add(vertex);
for (int neighbor: adjList.get(vertex)) {
in[neighbor]--;
if (in[neighbor] == 0) {
queue.add(neighbor);
}
}
}
return sortedList;
}
public static void main(String[] args) {
List<List<Integer>> adj = new ArrayList<>();
adj.add(Arrays.asList(1, 2));
adj.add(Arrays.asList(3));
adj.add(Arrays.asList(3));
adj.add(Collections.emptyList());
List<Integer> sortedList = topologicalSort(4, adj);
System.out.println(sortedList); // [0, 1, 2, 3]
}
}
Output
[0, 1, 2, 3]
Explanation
We define a tiny directed acyclic graph with vertices 0 through 3 as an adjacency list in the main function. Following that, we use the number of vertices and the adjacency list to use the topological sort function, and we display the sorted list of returned vertices. The correct output is [0, 1, 2, 3].
Dijkstra's Algorithm
In a weighted network, the shortest path between a source node and every other node is found using Dijkstra's method, a graph traversal algorithm. The method keeps track of nodes with known shortest distances to the source node and nodes with unknown shortest distances. The method updates the distances between nearby nodes at each step, selecting the node with the least known distance and relaxing that node's outgoing edges.
Routing applications and subroutines in other graph algorithms frequently employ Dijkstra's technique. A fundamental tenet of Dijkstra's algorithm is that all edge weights must be positive.
Pseudo Code
- Initialize the distances of all nodes to infinity, except the source node, which is initialized to 0. Create a set of nodes whose shortest distance is unknown, initially containing all nodes.
- Choose the node with the smallest tentative distance, remove it from the set of nodes whose shortest distance is unknown, and mark it as visited.
- For each neighboring node that is still in the set of nodes whose shortest distance is not yet known, update its tentative distance to the sum of the current node's tentative distance and the weight of the edge connecting them if this is less than the current tentative distance of the neighboring node.
- Repeat steps 2 and 3 until all nodes have been visited, or infinity is the smallest tentative distance in the set of nodes whose shortest distance is unknown.
Dijkstra.java
import java. util.*;
public class Dijkstra {
public static int[] dijkstra(int numVertices, List<List<int[]>> adjList, int source) {
int[] distances = new int[numVertices];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[source] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{source, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0];
int dist = curr[1];
if (dist > distances[u]) {
continue;
}
for (int[] edge : adjList.get(u)) {
int v = edge[0];
int weight = edge[1];
if (dist + weight < distances[v]) {
distances[v] = dist + weight;
pq.offer(new int[]{v, distances[v]});
}
}
}
return distances;
}
public static void main(String[] args) {
int numVertices = 5;
List<List<int[]>> adjList = new ArrayList<>();
for (int i = 0; i < numVertices; i++) {
adjList.add(new ArrayList<>());
}
adjList.get(0).add(new int[]{1, 4});
adjList.get(0).add(new int[]{2, 3});
adjList.get(1).add(new int[]{3, 2});
adjList.get(1).add(new int[]{4, 5});
adjList.get(2).add(new int[]{3, 5});
adjList.get(2).add(new int[]{4, 6});
adjList.get(3).add(new int[]{4, 1});
int source = 0;
int[] distances = dijkstra(numVertices, adjList, source);
System.out.println(Arrays.toString(distances)); // [0, 4, 3, 6, 5]
}
}
Output
[0, 4, 3, 6, 7]
Prims Algorithm
The weighted undirected graph's minimal spanning tree (MST) is found using Prim's method, a greedy technique. Starting with a single vertex, the technique steadily develops the tree by connecting each vertex in the tree to a vertex still in the tree with a minimum-weight edge until all vertices are present.
Prim's Algorithm Pseudocode
- Make a priority queue PQ that will hold the edges connecting X to the vertices not yet in X and a set X that will include the vertices in the MST.
- Add whatever vertex (v) you choose to X.
- Add e to the total for each edge e connecting v to a vertex u that isn't yet in X.
- Remove the edge e from PQ with the least weight while PQ is still full.
- Add the endpoint u of e to X if it is not already there, and add to PQ all edges that link you to vertices that are not yet in X.
- The collection of edges that join the vertices in X is known as the MST.
Prim.java
import java.util.*;
public class Prim{
static class Edge implements Comparable<Edge> {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(weight, other.weight);
}
}
public static List<Edge> primMST(int[][] graph) {
int n = graph.length;
boolean[] visited = new boolean[n];
List<Edge> mst = new ArrayList<>();
PriorityQueue<Edge> pq = new PriorityQueue<>();
// start from vertex 0
visited[0] = true;
for (int j = 0; j < n; j++) {
if (graph[0][j] != 0) {
pq.offer(new Edge(0, j, graph[0][j]));
}
}
while (!pq.isEmpty()) {
Edge e = pq.poll();
if (visited[e.dest]) {
continue;
}
visited[e.dest] = true;
mst.add(e);
int dest = e.dest;
for (int j = 0; j < n; j++) {
if (graph[dest][j] != 0 && !visited[j]) {
pq.offer(new Edge(dest, j, graph[dest][j]));
}
}
}
return mst;
}
public static void main(String[] args) {
int[][] graph = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};
List<Edge> mst = primMST(graph);
System.out.println("Minimum Spanning Tree: ");
for (Edge e : mst) {
System.out.println(e.src + " - " + e.dest + " : " + e.weight);
}
}
}
Output
Minimum Spanning Tree:
0 - 1 : 2
1 - 2 : 3
1 - 4 : 5
0 - 3 : 6
Kruskal's Algorithm
A weighted undirected graph's minimal spanning tree (MST) may be found using the greedy Kruskal's approach. The procedure adds edges to the MST in ascending order of weight after first sorting all of the graph's edges by weight, provided that doing so does not result in a cycle in the MST.
Kruskal's Algorithm Pseudocode:
- Sort every edge in the graph according to ascending weights.
- At each vertex in the graph, make a fresh set.
- In descending order of weight, for each edge in the sorted list of edges:
- Merge the two sets into one set by adding the edge to the minimal spanning tree if it connects two vertices that are not in the same set.
- b. Discard the edge if it joins two vertices already in the same set.
- Once all edges have been handled, repeat step 3.
- The series of edges added to the least spanning tree in step 3 is the minimum spanning tree.
KruskalAlgorithm.java
import java.util.*;
public class KruskalAlgorithm {
static class Edge implements Comparable<Edge> {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(weight, other.weight);
}
}
static class UnionFind {
int[] parent, rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int px = find(x), py = find(y);
if (rank[px] < rank[py]) {
parent[px] = py;
} else {
parent[py] = px;
if (rank[px] == rank[py]) {
rank[px]++;
}
}
}
}
public static List<Edge> kruskalMST(int[][] graph) {
int n = graph.length;
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (graph[i][j] != 0) {
edges.add(new Edge(i, j, graph[i][j]));
}
}
}
Collections.sort(edges);
UnionFind uf = new UnionFind(n);
List<Edge> mst = new ArrayList<>();
for (Edge e : edges) {
int u = e.src, v = e.dest;
if (uf.find(u) != uf.find(v)) {
uf.union(u, v);
mst.add(e);
}
}
return mst;
}
public static void main(String[] args) {
int[][] graph = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};
List<Edge> mst = kruskalMST(graph);
System.out.println("Minimum Spanning Tree using Kruskal's Algorithm:");
for (Edge e : mst) {
System.out.printf("(%d, %d, %d)\n", e.src, e.dest, e.weight);
}
}
}
Output
Minimum Spanning Tree using Kruskal's Algorithm:
(0, 1, 2)
(1, 2, 3)
(1, 4, 5)
(0, 3, 6)