MST - Использование простых чисел (чтение из файла) Java - PullRequest
Новая
       24

MST - Использование простых чисел (чтение из файла) Java

0 голосов
/ 15 ноября 2018

Что я хочу сделать, это создать MST из нескольких точек (которые я читаю из файла). Это работает так, что я знаю каждое расстояние от каждой точки до любой другой точки.

Моя идея состоит в том, чтобы начать с некоторой точки (которая когда-либо), посмотреть, где находится ближайшая следующая точка, пойти туда и продолжать искать и не переходить ни на один узел, который я уже посетил.

Мой подход состоит в том, чтобы иметь массив со всеми точками. Начните с первой точки, посмотрите все ее ребра на другие точки и отсортируйте расстояние, затем выберите кратчайший путь, перейдите туда и удалите точку из массива.

Проблема в том, что мне нужно держать в курсе, откуда берется край, куда он идет (в какую точку) и расстояние, но только сортировать по расстоянию. У меня есть функция setLink (i, j), которая устанавливает границу между точками i и j, поэтому мне нужно знать точки, но сортировать только по расстоянию.

Мне был предоставлен класс TreeMapPriorityQueue, который, как мне кажется, мне нужно использовать для этого.

Предоставлены функция MST и класс TreeMapPriorityQueue.

открытый класс TreeMapPriorityQueue, Key extends Comparable> {

private class Node implements Comparable<Node>{
    Priority m_p;
    Key m_k;

    Node(Key k, Priority p){
        m_p = p;
        m_k = k;
    }


  public class Edge {
       int src, dest;
       float weight;


       Edge(int src, int dest, float weight) {
           this.src = src;
           this.dest = dest;
           this.weight = weight;
       }
   }

        @Override
    public int compareTo(Node other){
        int pComp = m_p.compareTo(other.m_p);
        if (pComp == 0) {
            return m_k.compareTo(other.m_k);
        }
        else return pComp;
    }
}

TreeMap<Node,Key> m_tree = new TreeMap<Node,Key>();
HashMap<Key,Node> m_map = new HashMap<Key,Node>();


TreeMapPriorityQueue(){

}

void add(Key k, Priority p){
    Node n = new Node(k, p);
    m_tree.put(n, k);
    m_map.put(k, n);
}

void decreasePriority(Key k, Priority p){
    Node n = m_map.get(k);
    if (n == null) throw new IllegalArgumentException("Bad key.");
    if (n.m_p.compareTo(p) > 0){
        m_tree.remove(n);
        m_map.remove(k);
        n.m_p = p;
        m_tree.put(n, k);
        m_map.put(k, n);
    }
}


Key extractMin(){
    Node n = m_tree.firstKey();
    m_tree.remove(n);
    Key k = n.m_k;
    m_map.remove(k);
    return k;
}



public Priority lookup(Key k){
    Node n = m_map.get(k);
    if (n != null)
        return n.m_p;
    else return null;
}

public boolean isEmpty(){
    return m_tree.isEmpty();
}
...