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

Question

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

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

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

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

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

где:

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

Заранее спасибо!

Answer 1

Если кто-то ищет MST с реализацией матрицы смежности, есть мой пример кода на Java.Я публикую его, потому что в ответе Junkbot отсутствуют некоторые детали.Он работает в O (n ^ 2), поэтому алгоритм Прима - лучший выбор для плотного / полного графа для нахождения 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;
        }

    }

}

Answer 2

Учитывая, что ваша программа в настоящий момент не может обработать структуру данных 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 log E), где E = num ребер, если вы используетекуча.