Java中的鄰接矩陣的最小生成樹

Question

請幫助我理解如何從圖的鄰接矩陣中獲得最小生成樹！ 我用java編寫關於它的課程，截止日期是16.12.2010，但我覺得它會失敗。 現在我的計劃可以：

1. 繪製節點
2. 繪製邊緣
3. 生成圖形的鄰接矩陣繪畫的地下室重邊的
4. 查找最小的邊緣連接到節點
5. 和有一些其他的測試/測試功能

但我不知道如何實現Java中的Prim/Kruskal算法。我試圖找到一些決議 在谷歌，但只找到Java-applet，需要工作.obj文件，我也無法運行它。

我寫了一些簡單的控制檯java pattern，現在生成並打印圖形的鄰接矩陣。任何人可以添加函數，返回圖的最小生成樹的鄰接矩陣看起來像：

public static int[][] mst(int[][] graph, int n) { 
    ... 
} 

其中：

• 圖 - 在正被生成的圖形
• 頂點的數量（節點）

在此先感謝！

Answer 1

鑑於您的程序目前無法處理不相交集數據結構，您可能需要使用Prim's。

鑑於您已經可以完成Prim's所需的大部分工作，我將以僞代碼的形式將其提供給您。

int bestDist[N] 
int mst[N][N] 
int cameHere[N] 
bool done[N] 
FOR i = 0..N-1: 
bestDist[i] = INFINITY 
done[i] = false 
FOR j=0..N-1: 
    mst[i][j] = INFINITY 

// start at any node 
bestDist[0] = 0; 
FOR i = 0..N-1: 
bestNode = INFINITY 
bestNodeDist = INFINITY 

IF bestNode != 0: 
    mst[cameHere[bestNode]][bestNode] = graph[cameHere[bestNode]][bestNode] 

// find closest node 
FOR j= 0..N-1: 
    IF !done[j] AND bestDist[j] < bestNodeDist: 
    bestNode = j 
    bestNodeDist = bestNodeDist[j] 

// update surrounding nodes 
FOR j=0..N-1: 
    IF !done[j] AND bestNodeDist + graph[bestNode][j] < bestDist[j]: 
    bestDist[j] = bestNodeDist + graph[bestNode][j] 
    cameHere[j] = bestNode 

return mst 

這個運行在O（N^2），但可以讓它運行爲O（E登錄E），在那裏，如果你使用一個堆E = NUM​​邊緣。

Answer 2

如果有人正在尋找具有鄰接矩陣實現的MST，那麼我的示例代碼就是Java。我張貼它，因爲Junkbot答案缺乏一些細節。它運行於O（n^2），所以Prim算法是查找MST的密集/完整圖的最佳選擇。

public void MST-Prim() 
    { 
    int[] source = new int[numberOfVertices]; // i-th element contains number of source vertex for the edge with the lowest cost from tree T to vertex i 
    double[] dist = new double[numberOfVertices]; //i-th element contains weight of minimal edge connecting i with source[i] 
    indicators = new boolean[numberOfVertices]; //if true, vertex i is in tree T 

    // Mark all vertices as NOT being in the minimum spanning tree 
    for (int i = 0; i < numberOfVertices; i++) 
    { 
     indicators[i] = false; 
     dist[i] = Double.POSITIVE_INFINITY; 
    } 

    //we start with vertex number 0 
    indicators[0] = true; 
    dist[0] = 0; 
    int bestNeighbour = 0;// lastly added vertex to the tree T 
    double minDist; 

    for (int i = 0; i < numberOfVertices - 1; i++) 
    { 
     minDist = Double.POSITIVE_INFINITY; 

     for (int j = 0; j < numberOfVertices; j++) // fill dist[] based on distance to bestNeighbour vertex 
     { 
      if (!indicators[j]) 
      { 
       double weight = fullGraph.getEdgeWeight(bestNeighbour, j); 

       if (weight < dist[j]) 
       { 
        source[j] = bestNeighbour; 
        dist[j] = weight; 
       } 
      } 
     } 

     for (int j = 0; j < numberOfVertices; j++) // find index of min in dist[] 
     { 
      if (!indicators[j]) 
      { 
       if (dist[j] < minDist) 
       { 
        bestNeighbour = j; 
        minDist = dist[j]; 
       } 
      } 
     } 

     if (bestNeighbour != 0) 
     {//add the edge (bestNeighbour, dist[bestNeighbour]) to tree T 
      addEdgeToTree(new GraphEdge(fullGraph.getNode(source[bestNeighbour]), fullGraph.getNode(bestNeighbour), 
        dist[bestNeighbour])); 
      indicators[bestNeighbour] = true; 
     } 

    } 

}