import java.util.ArrayList;
import java.util.List;

// shortest path
public class GraphAdjacentMatrix_MST {
    public static int empty = -1;

    private int adjMatrix[][];
    private int numVertices;
    private boolean visited[];
    private List<Integer> MST = new ArrayList<>();
    private int sourceV[];
    private int distance[];

    public GraphAdjacentMatrix_MST(int numVertices) {
        this.numVertices = numVertices;

        adjMatrix = new int[numVertices][numVertices];
        for (int i = 0; i < adjMatrix.length; i++) {
            for (int j = 0; j < adjMatrix[i].length; j++) {
                adjMatrix[i][j] = empty;
            }
        }

        visited = new boolean[numVertices];
        distance = new int[numVertices];
        sourceV = new int[numVertices];
        for (int i = 0; i < distance.length; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
    }


    public int getWeight(int i, int j){
        return adjMatrix[i][j];
    }

    public void setEdge(int i, int j, int weight) {
        adjMatrix[i][j] = weight;
//        adjMatrix[j][i] = true; // directed
    }

    public void delEdge(int i, int j) {
        adjMatrix[i][j] = empty;
//        adjMatrix[j][i] = false; // directed
    }

    public boolean isEdge(int i, int j) {
        return (adjMatrix[i][j] != -1);
    }

    public int first(int v1){
        int[] ary = this.adjMatrix[v1];
        int firstNeighborIndex = this.numVertices; // return n if none
        for (int i = 0; i < ary.length; i++) {
            if (ary[i] != empty){
                firstNeighborIndex = i;
                break;
            }
        }
        return firstNeighborIndex;
    }

    public int next(int v1, int v2){
        int[] ary = this.adjMatrix[v1];
        int nextNeighborIndex = this.numVertices; // return n if none
        for (int i = v2 + 1; i < ary.length; i++) {
            if (ary[i] != empty){
                nextNeighborIndex = i;
                break;
            }
        }
        return nextNeighborIndex; // return n if none
    }

    // calculate the shortest distances between the startingVertice to all other vertices
    public int[] Prim(int startingVertice) {
        distance[startingVertice] = 0; // initialize first data - from startingVertice to startingVertice
        for (int i = 0; i < this.numVertices; i++) { // process all vertices
            int v = minVertex(); // seek the next closest vertex to any vertex currently in the MST
            if (v == empty) return distance;// all vertices are visited

            this.visited[v] = true;
            if (v != startingVertice){
                addEdgeToMST(sourceV[v], v);
            }else{
                System.out.println("adding startingVertice to the MST.");
            }

            for (int neighborV = first(v); neighborV < numVertices; neighborV = next(v, neighborV)) {
                // recalculate the distance from the current MST to the rest of the remaining vertices
                if (distance[neighborV] > getWeight(v, neighborV)) {
                    distance[neighborV] = getWeight(v, neighborV);
                    sourceV[neighborV] = v; // where it came from
                }
            }

        }

        return distance;
    }

    private void addEdgeToMST(int i, int v) {
        System.out.printf("%d -> %d %n", i , v);
    }

    // find the shorted distance from startingVertice to D so far; this will be our next starting point
    private int minVertex() {
        int nextVWithShortestDistance = empty; // if all vertices are visited
        // initialize v to some unvisited vertex
        int i;
        for (i = 0; i < this.numVertices; i++) {
            if (!visited[i]) {
                nextVWithShortestDistance = i;
                break;
            }
        }
        // find the smallest D value
        for (i++; i < this.numVertices; i++) {
            if (!visited[i] && distance[i] < distance[nextVWithShortestDistance]) {
                nextVWithShortestDistance = i;
            }
        }

        return nextVWithShortestDistance;
    }

    private void Previsit(boolean[][] graph, int v) {
        System.out.println("Previsit: " + v);
    }

    private void Postvisit(boolean[][] graph, int v) {
        System.out.println("Postvisit: " + v);
    }

    public String toString() {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < numVertices; i++) {
            s.append(i + ": ");
            for (int j : adjMatrix[i]) {
                s.append((i != empty?1:0) + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }

    public static void main(String[] args) {
        GraphAdjacentMatrix_MST gam = new GraphAdjacentMatrix_MST(7);

        // directed graph
        gam.setEdge(1, 3, 7);
        gam.setEdge(3, 1, 7);
        gam.setEdge(1, 5, 9);
        gam.setEdge(5, 1, 9);
        gam.setEdge(3, 4, 1);
        gam.setEdge(4, 3, 1);
        gam.setEdge(2, 3, 5);
        gam.setEdge(3, 2, 5);
        gam.setEdge(3, 6, 2);
        gam.setEdge(6, 3, 2);
        gam.setEdge(4, 6, 2);
        gam.setEdge(6, 4, 2);
        gam.setEdge(2, 6, 6);
        gam.setEdge(6, 2, 6);
        gam.setEdge(5, 6, 1);
        gam.setEdge(6, 5, 1);

        int[] distances = gam.Prim(1);
        printArray(distances);

        System.out.println();
    }


    ////////// UTIL ///////////

    private static void printArray(int[] ary){
        for (int i = 0; i < ary.length; i++) {
            System.out.printf("%4d" , ary[i]);
        }
        System.out.println();
    }

}