1. 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) RSS

    • ava scalar4eblo4no 03.03.2011 17:08 # +5

      http://forum.algolist.ru/
      Ответить

    • ava Lure Of Chaos 03.03.2011 17:31 # +3

      а вы адресом случайно не ошиблись? тут альтруистов нет. Люди все злые и уставшие, они не помогать хотят, а поржать и выпить пива
      Ответить

    • ava ZX_Spectrum 03.03.2011 17:35 # 0

      Тут вообще-то полно специалистов по алгоритму Борувки, но, к сожалению, именно сейчас все они в отпуске!
      Ответить

    • ava bugmenot 03.03.2011 17:39 # 0

      > буду очень благодарен
      мы благодарность принимаем исключительно авансом
      Ответить

    • ava NightCrime 04.03.2011 01:32 # 0

      перерыв весь интернет, мне уже все равно куда писать...ну и куда же еще выложить такой цикл "for (int i=this.g.getCountEdges(); i!=0; i=nxtPhase)" как не на говно код, так как по сути nxtPhase будет увеличиваться пока не дойдет до 2^32-1..а потом я даж хз что случится)
      Ответить

    Добавить комментарий