VPF::[Java]Алгоритм Борувки - Форум программистов

NightCrime

Дата 3.3.2011, 13:39 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 3.3.2011

Репутация: нет
Всего: нет

Помогите пожалуйста разобраться с алгоритмом Борувки для нахождения минимального остова графа. Код писал по коду Седжевика подстраивая под свой граф, но видимо наделал кучу глупостей, потому что алгоритм никогда не выходит из цикла. Подскажите где я ошибок наделал и как бы их исправить, буду очень благодарен. Код ниже.

Код


public class Boruvka
{
    // private representations
    /**
     * Array of edges, which form the MST of the graph
     */
    private Edge[] mst;
    /**
     * Edges not yet discarded and not yet in the MST
     */
    private Edge[] wannabes;
    /**
     * Each component's nearest neighbor with find component numbers as indices
     */
    private Edge[] neighbors;
    /**
     * Graph representation on which we are searching for MST
     */
    private Graph g;
    /**
     *
     */
    private UnionFind uf;
    // constructors and methods
    /**
     * constructor
     * @param G Graph
     */
    public Boruvka(Graph G) {
        this.g = G;
    }
    /**
     * Boruvka's algorithm
     *
     *
     * @return minimal spanning tree - edges that form it
     */

    public Edge[] BoruvkaMSTalg()
    {
        Edge hlpEdge = new Edge(g.getMaxWeight(), 0, 0);
        this.uf = new UnionFind(g.getCountVerteces());
        this.wannabes = new Edge[this.g.getCountEdges()];

         /**
         * Get all edges from the graph G to the array edges
         */
        for (int i=0; i < g.getCountEdges(); i++)
            this.wannabes[i] = g.getEdgeAt(i);


        this.neighbors = new Edge[this.g.getCountVerteces()];
        this.mst = new Edge[this.g.getCountVerteces()+1];

        /**
         * index, used to store those edges being saved for the next phase
         */
        int nxtPhase;
        int k=1;

        for (int i=this.g.getCountEdges(); i!=0; i=nxtPhase)
        {
            int l, m, n;

            for (int o=0; o<this.g.getCountVerteces(); o++)
                this.neighbors[o] = hlpEdge;

            for (n=0, nxtPhase=0; n<i; n++) {
                Edge e = this.wannabes[n];
                l = this.uf.find(e.getSVIndex()-1);
                m = this.uf.find(e.getDVIndex()-1);

                if ( l==m )
                    continue;
                if ( e.getWeight() < this.neighbors[l].getWeight() )
                    this.neighbors[l] = e;
                if ( e.getWeight() < this.neighbors[m].getWeight() )
                    this.neighbors[m] = e;

                this.wannabes[nxtPhase++] = e;
            }

            for (n=0; n<this.g.getCountVerteces(); n++)
                if ( this.neighbors[n] != hlpEdge ) {
                    l = this.neighbors[n].getSVIndex();
                    m = this.neighbors[n].getDVIndex();

                    if ( !this.uf.find(l,m) ) {
                        this.uf.unite(l,m);
                        this.mst[k++] = this.neighbors[n];
                    }
                }
        }
        System.out.println("MST by Boruvka successful");
        return this.mst;
    }
}

Это сообщение отредактировал(а) NightCrime - 5.3.2011, 22:27

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »