where I need to find the minimum spanning tree with a specified known start and known end node
The next algorthim return shortest path without specifing the nodes
package com.company;
import java.util.*;
public class KruskalMST {
public static void runKruskalAlgorithm(Graph graph, int src, int dest) {
List<Edge> MST = new ArrayList<>();
//List<Edge> edges = graph.getEdges();
int numberOfVertices = graph.getNumberOfVertices();
Edge result[] = new Edge[numberOfVertices];
Edge[] edges = graph.getEdge();
int e = 0;
int i = 0;
for (i = 0; i < numberOfVertices; ++i)
result[i] = new Edge();
// Sorting the edges
Arrays.sort(edges);
DisjointSet disjointSet = new DisjointSet();
disjointSet.makeSet(numberOfVertices);
int index = src;
while (e < numberOfVertices - 1)
{
Edge next_edge = edges[index++];
int x = disjointSet.find(next_edge.src);
int y = disjointSet.find(next_edge.dest);
if (x != y)
{
result[e++] = next_edge;
disjointSet.union(x, y);
}
}
System.out.println("Following are the edges in "
+ "the constructed MST");
int minimumCost = 0;
for (int j = 0; j < e; ++j)
{
System.out.println(result[j].src + " -- "
+ result[j].dest
+ " == " + result[j].weight);
minimumCost += result[j].weight;
}
System.out.println("Minimum Cost Spanning Tree "
+ minimumCost);
}
} package com.company;
import java.util.HashMap; import java.util.Map;
public class DisjointSet {
Map<Integer, Integer> parent = new HashMap<>();
public void makeSet(int n) {
for (int i = 0; i < n; i++) {
parent.put(i, i);
}
}
public int find(int k) {
if (parent.get(k) == k) {
return k;
}
return find(parent.get(k));
}
public void union(int a, int b) {
int x = find(a);
int y = find(b);
parent.put(x, y);
}
}
Can anyone please show me how to find the minimum spanning tree of this graph