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; 
     } 

    } 

}