Минимальное связующее дерево из матрицы смежности в Java

Question

Пожалуйста, помогите мне понять, как получить минимальное связующее дерево из матрицы смежности графа! Я пишу курсовые работы об этом в java, крайний срок - 16.12.2010, но я чувствую, что он потерпит неудачу. Теперь моя программа может:

1. тиражной узлы
2. Розыгрыш края
3. Сформировать матрицу смежности графа на фундаменте вашего чертежа с весом ребер
4. Найти минимальный край подключенного к узлу
5. и имеют некоторые другие тестируемые/проверенные функции

Но я не знаю, как реализовать алгоритм Prim/Kruskal al Java в Java. Я пытаюсь найти некоторые разрешения в Google, но найти только Java-апплет, который должен работать .obj-файлы, также я не могу его запустить.

Я пишу Простую консольную java pattern, которая теперь генерирует и печатает матрицу смежности графа. Кто-нибудь может добавить функцию, которая возвращает матрицу смежности минимального остовного дерева графа выглядит как:

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

где:

• граф - генерируется график в п
• количество вершин (узлов)

Заранее благодарен!

Answer 1

Учитывая, что ваша программа в настоящий момент не может обрабатывать структуру данных Disjoint Set, вы, вероятно, захотите использовать Prim.

Увидев, что вы уже можете выполнять большинство вещей, необходимых для работы Prim, я дам его вам в псевдокоде.

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

    } 

}