uopspop

Untitled

Sep 21st, 2019
173
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.List;
  3.  
  4. // shortest path
  5. public class GraphAdjacentMatrix_MST {
  6.     public static int empty = -1;
  7.  
  8.     private int adjMatrix[][];
  9.     private int numVertices;
  10.     private boolean visited[];
  11.     private List<Integer> MST = new ArrayList<>();
  12.     private int sourceV[];
  13.     private int distance[];
  14.  
  15.     public GraphAdjacentMatrix_MST(int numVertices) {
  16.         this.numVertices = numVertices;
  17.  
  18.         adjMatrix = new int[numVertices][numVertices];
  19.         for (int i = 0; i < adjMatrix.length; i++) {
  20.             for (int j = 0; j < adjMatrix[i].length; j++) {
  21.                 adjMatrix[i][j] = empty;
  22.             }
  23.         }
  24.  
  25.         visited = new boolean[numVertices];
  26.         distance = new int[numVertices];
  27.         sourceV = new int[numVertices];
  28.         for (int i = 0; i < distance.length; i++) {
  29.             distance[i] = Integer.MAX_VALUE;
  30.         }
  31.     }
  32.  
  33.  
  34.     public int getWeight(int i, int j){
  35.         return adjMatrix[i][j];
  36.     }
  37.  
  38.     public void setEdge(int i, int j, int weight) {
  39.         adjMatrix[i][j] = weight;
  40. //        adjMatrix[j][i] = true; // directed
  41.     }
  42.  
  43.     public void delEdge(int i, int j) {
  44.         adjMatrix[i][j] = empty;
  45. //        adjMatrix[j][i] = false; // directed
  46.     }
  47.  
  48.     public boolean isEdge(int i, int j) {
  49.         return (adjMatrix[i][j] != -1);
  50.     }
  51.  
  52.     public int first(int v1){
  53.         int[] ary = this.adjMatrix[v1];
  54.         int firstNeighborIndex = this.numVertices; // return n if none
  55.         for (int i = 0; i < ary.length; i++) {
  56.             if (ary[i] != empty){
  57.                 firstNeighborIndex = i;
  58.                 break;
  59.             }
  60.         }
  61.         return firstNeighborIndex;
  62.     }
  63.  
  64.     public int next(int v1, int v2){
  65.         int[] ary = this.adjMatrix[v1];
  66.         int nextNeighborIndex = this.numVertices; // return n if none
  67.         for (int i = v2 + 1; i < ary.length; i++) {
  68.             if (ary[i] != empty){
  69.                 nextNeighborIndex = i;
  70.                 break;
  71.             }
  72.         }
  73.         return nextNeighborIndex; // return n if none
  74.     }
  75.  
  76.     // calculate the shortest distances between the startingVertice to all other vertices
  77.     public int[] Prim(int startingVertice) {
  78.         distance[startingVertice] = 0; // initialize first data - from startingVertice to startingVertice
  79.         for (int i = 0; i < this.numVertices; i++) { // process all vertices
  80.             int v = minVertex(); // seek the next closest vertex to any vertex currently in the MST
  81.             if (v == empty) return distance;// all vertices are visited
  82.  
  83.             this.visited[v] = true;
  84.             if (v != startingVertice){
  85.                 addEdgeToMST(sourceV[v], v);
  86.             }else{
  87.                 System.out.println("adding startingVertice to the MST.");
  88.             }
  89.  
  90.             for (int neighborV = first(v); neighborV < numVertices; neighborV = next(v, neighborV)) {
  91.                 // recalculate the distance from the current MST to the rest of the remaining vertices
  92.                 if (distance[neighborV] > getWeight(v, neighborV)) {
  93.                     distance[neighborV] = getWeight(v, neighborV);
  94.                     sourceV[neighborV] = v; // where it came from
  95.                 }
  96.             }
  97.  
  98.         }
  99.  
  100.         return distance;
  101.     }
  102.  
  103.     private void addEdgeToMST(int i, int v) {
  104.         System.out.printf("%d -> %d %n", i , v);
  105.     }
  106.  
  107.     // find the shorted distance from startingVertice to D so far; this will be our next starting point
  108.     private int minVertex() {
  109.         int nextVWithShortestDistance = empty; // if all vertices are visited
  110.         // initialize v to some unvisited vertex
  111.         int i;
  112.         for (i = 0; i < this.numVertices; i++) {
  113.             if (!visited[i]) {
  114.                 nextVWithShortestDistance = i;
  115.                 break;
  116.             }
  117.         }
  118.         // find the smallest D value
  119.         for (i++; i < this.numVertices; i++) {
  120.             if (!visited[i] && distance[i] < distance[nextVWithShortestDistance]) {
  121.                 nextVWithShortestDistance = i;
  122.             }
  123.         }
  124.  
  125.         return nextVWithShortestDistance;
  126.     }
  127.  
  128.     private void Previsit(boolean[][] graph, int v) {
  129.         System.out.println("Previsit: " + v);
  130.     }
  131.  
  132.     private void Postvisit(boolean[][] graph, int v) {
  133.         System.out.println("Postvisit: " + v);
  134.     }
  135.  
  136.     public String toString() {
  137.         StringBuilder s = new StringBuilder();
  138.         for (int i = 0; i < numVertices; i++) {
  139.             s.append(i + ": ");
  140.             for (int j : adjMatrix[i]) {
  141.                 s.append((i != empty?1:0) + " ");
  142.             }
  143.             s.append("\n");
  144.         }
  145.         return s.toString();
  146.     }
  147.  
  148.     public static void main(String[] args) {
  149.         GraphAdjacentMatrix_MST gam = new GraphAdjacentMatrix_MST(7);
  150.  
  151.         // directed graph
  152.         gam.setEdge(1, 3, 7);
  153.         gam.setEdge(3, 1, 7);
  154.         gam.setEdge(1, 5, 9);
  155.         gam.setEdge(5, 1, 9);
  156.         gam.setEdge(3, 4, 1);
  157.         gam.setEdge(4, 3, 1);
  158.         gam.setEdge(2, 3, 5);
  159.         gam.setEdge(3, 2, 5);
  160.         gam.setEdge(3, 6, 2);
  161.         gam.setEdge(6, 3, 2);
  162.         gam.setEdge(4, 6, 2);
  163.         gam.setEdge(6, 4, 2);
  164.         gam.setEdge(2, 6, 6);
  165.         gam.setEdge(6, 2, 6);
  166.         gam.setEdge(5, 6, 1);
  167.         gam.setEdge(6, 5, 1);
  168.  
  169.         int[] distances = gam.Prim(1);
  170.         printArray(distances);
  171.  
  172.         System.out.println();
  173.     }
  174.  
  175.  
  176.     ////////// UTIL ///////////
  177.  
  178.     private static void printArray(int[] ary){
  179.         for (int i = 0; i < ary.length; i++) {
  180.             System.out.printf("%4d" , ary[i]);
  181.         }
  182.         System.out.println();
  183.     }
  184.  
  185. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×