CS 15-121 Introduction to Data Structures 				Lab 7

	1.	Draw the graph that s represented by the following adjacency matrix on paper:
 0     1     2     3     
0        0     4     4     5
1        4     0     0     4
2        4     0     0     4
3        5     4     4     0
 
	1.	Read up about Prim's algorithm here: https://en.wikipedia.org/wiki/Prim%27s_algorithm
	2.	Read up about Dijkstra's algorithm here: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
	3.	For the above graph, trace out the trees generated by Prim and Dijkstra.
	4.	What is the difference between these two algorithms in generating a tree? Do they both generate the same type of tree? 
	5.	Below is the code for one of the algorithms. Go through it carefully and find out which algorithm it is implementing. 
        You might want to add comments to make the next task simpler.
*****************************************************************
public class JavaApplication {
    static final int nodes=4;
    int minDistance(int dist[], Boolean visited[])
    {
        int min = Integer.MAX_VALUE, min_index=-1;
 
        for (int v = 0; v < nodes; v++)
            if (visited[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }
 
        return min_index;
    }

    void mystery(int graph[][], int src)
    {
        int dist[] = new int[nodes];
        Boolean visited[] = new Boolean[nodes];
 
        for (int i = 0; i < nodes; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }
        dist[src] = 0;
        for (int count = 0; count < nodes-1; count++)
        {
            int u = minDistance(dist, visited);
            visited[u] = true;
            for (int v = 0; v < nodes; v++)
 
                if (!visited[v] && graph[u][v]!=0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u]+graph[u][v] < dist[v])
                {
                    dist[v] = dist[u] + graph[u][v];                   
                }
        }
        //call the method to print here
    }

    public static void main(String[] args) {
        int graph[][] = new int[][]{{0,4,4,5 },{4,0,0,4},{4,0,0,4 },{5,4,4,0}};
        JavaApplication obj = new JavaApplication();
        obj.mystery(graph, 0);
        
    }
    
}
 
*********************************************************
	1.	Add a method that will print the following for the graph in the JavaApplication class:
Vertex   Distance from Source    Edge costs
0                  0                
1                  4                              4
.
.
.
 
Note that the values for the first two columns are already present in the code. You will, however, need to add extra code to keep track of 
edge costs of previously visited nodes for each node.