Here is a graph

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

0

There are 0 best solutions below