Java中的Prim's和Kruskal算法

Question

爲了在給定的無向加權圖中找到最小生成樹，我必須在Java中實現Prim's和Kruskal算法。我怎樣才能做到這一點 ？實現必須至少實現Prim算法的O（2）和Kruskal算法的O（3）（n是節點的數量）。

public class Graph { 
/*The following square matrix represents a weighted undirected graph. 
    the value in (i,j) position indicates the cost between i and j node. 
    Zeros indicate no connection*/ 

    static int[][] matrix = { { 0, 3, 0, 2, 0, 0, 0, 0, 4 }, // 0 
     { 3, 0, 0, 0, 0, 0, 0, 4, 0 }, // 1 
     { 0, 0, 0, 6, 0, 1, 0, 2, 0 }, // 2 
     { 2, 0, 6, 0, 1, 0, 0, 0, 0 }, // 3 
     { 0, 0, 0, 1, 0, 0, 0, 0, 8 }, // 4 
     { 0, 0, 1, 0, 0, 0, 8, 0, 0 }, // 5 
     { 0, 0, 0, 0, 0, 8, 0, 0, 0 }, // 6 
     { 0, 4, 2, 0, 0, 0, 0, 0, 0 }, // 7 
     { 4, 0, 0, 0, 8, 0, 0, 0, 0 } // 8 
    }; 
    /* static int[][] matrix = { { 0, 2, 3, 0, 0 }, // 0 
       { 2, 0, 15, 2, 0 }, // 1 
       { 3, 15, 0, 0, 13}, // 2 
       { 0, 2, 0, 0, 9}, // 3 
       { 0, 0, 13, 9, 0}, // 4 }; */ 

static int Node = matrix.length; 
static int[][] Edge = new int[Node][Node]; 
static int NotConnected = 999999; 

public static void MakeGraph() { 
    for (int i = 0; i < Node; i++) { 
     for (int j = 0; j < Node; j++) { 
      Edge[i][j] = matrix[i][j]; 
      if (Edge[i][j] == 0)// If Node i and Node j are not connected 
       Edge[i][j] = NotConnected; 
     } 
    } 
    // Print the graph representation matrix. 
    for (int i = 0; i < Node; i++) { 
     for (int j = 0; j < Node; j++) 
      if (Edge[i][j] != NotConnected) 
       System.out.print(" " + Edge[i][j] + " "); 
      else // when there is no connection 
       System.out.print(" * "); 
     System.out.println(); 
    } 
} 

public static void Prim(){ 
    System.out.println("OUPUT OF PRIM'S ALGORITHM:"); 
    // Write the code for Prim algorithm to find the minimum cost spanning tree here 
    // and print the result in console with the following format: 
    /*==========================OUTPUT FORMAT=========================== 
      Minimun Cost of Spanning Tree = "....... "  

      Edges of the minimum cost spanning tree: 
      ".........................................................." 
      (for example: 
      Edges of the minimum cost spanning tree: 
      "0 -- 1 
      7 -- 2 
      0 -- 3 
      3 -- 4 
      2 -- 5 
      5 -- 6 
      1 -- 7 
      0 -- 8)" 
    ================================================================== */ 

} 

public static void Kruskal(){ 
    System.out.println("OUPUT OF KRUSKAL'S ALGORITHM:"); 
    // Write the code for Kruskal algorithm to find the minimum cost spanning tree here 
    // and print the result in console with the following format: 
    /*==========================OUTPUT FORMAT=========================== 
      Minimun Cost of Spanning Tree = "....... "  

      Edges of the minimum cost spanning tree: 
      ".........................................................." 
    ================================================================== */ 
} 

public static void main(String[] args) { 
    MakeGraph(); 
    Prim(); 
    Kruskal(); 
} 

} 

Answer 1

這是我實現：

public class Library { 
// Add the missing implementation to this class 

    java.util.ArrayList<Book> books; 

    private static String openingHours = "The Library is open every day from 9AM to 5PM"; 
    private String a ddress = ""; 
    private String[] collection = new String[10]; 
    private int collectionCount = 0; 

    public Library(String libraries) { 
     address = libraries; 
     books = new java.util.ArrayList<>(); 
    } 

    public 
      String getAddress() { 
     return this.address; 
    } 

    void setaddress(String address) { 
     this.address = address; 
    } 

    public static void printOpeningHours() { 
     System.out.println("Library Hours: "); 
     System.out.println(openingHours); 
    } 

    public void printAddress() { 
     System.out.println(address); 
    } 

    public void addBook(Book book) { 
     books.add(book); 
    } 

    public void printAvailableBooks() { 
     boolean bookPresent = false; 
     for (Book book : books) { 
      if (!book.isBorrowed()) { 
       System.out.println(book.getTitle()); 
       bookPresent = true; 
      } 
     } 
     if (!bookPresent) { 
      System.out.println("No such book in our catalog"); 
     } 
    } 

    private void borrowBook(String title) { 
     int found = 0; 
     for (Book book : books) { 
      if (book.getTitle().equals(title)) { 
       if (found == 0) { 
        found = 1; 
       } 
       if (!book.isBorrowed()) { 
        book.borrowed(); 
        found = 2; 
        break; 
       }; 
      } 
     } 
     if (found == 0) { 
      System.out.println("Sorry, this book is not in our catalog."); 
     } else if (found == 1) { 
      System.out.println("Sorry, this book is already borrowed."); 
     } else if (found == 2) { 
      System.out.println("You successfully borrowed " + title); 
     } 
    } 

    public void returnBook(String title) { 
     boolean found = false; 
     for (Book book : books) { 
      if (book.getTitle().equals(title) && book.isBorrowed()) { 
       book.returned(); 
       found = true; 
       break; 
      } 
     } 
     if (found) { 
      System.out.println("You successfully returned " + title); 
     } 
    } 

    public static void main(String[] args) { 
     Library firstLibrary = new Library("Moylish Park, Limerick"); 
     Library secondLibrary = new Library("Clare Street, Limerick"); 
     Library thirdLibrary = new Library("Nenagh Road, Thurles"); 

     // Add four books to the first library 
     firstLibrary.addBook(new Book("Java How To Program")); 
     firstLibrary.addBook(new Book("What's new in Java 7?")); 
     firstLibrary.addBook(new Book("Java in a nutshell")); 
     firstLibrary.addBook(new Book("Pro Android 2")); 

     // Print Opening hours and the addresses 
     Library.printOpeningHours(); 
     System.out.println(); 
     System.out.println("Library Addresses: "); 
     firstLibrary.printAddress(); 
     secondLibrary.printAddress(); 
     thirdLibrary.printAddress(); 
     System.out.println(); 

     // Print the titles of all available books from both libraries 
     System.out.println("Books available in the first library:"); 
     firstLibrary.printAvailableBooks(); 
     System.out.println(); 
     System.out.println("Books available in the second library:"); 
     secondLibrary.printAvailableBooks(); 
     System.out.println(); 
     System.out.println("Books available in the third library:"); 
     thirdLibrary.printAvailableBooks(); 
     System.out.println(); 

     // Return Java How To Program 
     System.out.println("Returning Java How To Program"); 
     firstLibrary.returnBook("Java How To Program"); 
     System.out.println(); 

     // Print the titles of available from the first library 
     System.out.println("Books available in the first library:"); 
     firstLibrary.printAvailableBooks(); 
    } 
}