1. Список говнокодов пользователя NightCrime

    Всего: 1

  2. Java / Говнокод #5870

    +146

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    75. 75
    76. 76
    77. 77
    78. 78
    79. 79
    80. 80
    81. 81
    82. 82
    83. 83
    84. 84
    85. 85
    86. 86
    87. 87
    88. 88
    89. 89
    90. 90
    91. 91
    92. 92
    93. 93
    94. 94
    95. 95
    96. 96
    97. 97
    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, 03 Марта 2011

    Комментарии (7)