qulinxao's Journal

линейный алгоритм построения остовного дерева
дан неориентированный связаный граф .

если в каждом узле минимальное ребро только одно ( либо что проще как критерий - в каждом узле ребра все разной длины(во всём рафе допустимы равные рёбра) - то для построения минимального остовного дерева достаточно для каждого узла выбрать линейным поиском минимальное ребро - очевидно что циклы не возможны и размер полченного дерева минимален.

ps.проще всего реализовать когда граф задан матрицей (NxN) , но и когда рёбрами тоже достаточно просто - для каждого ребра смотрим не есть ли оно минимальное для конечных вершин.

ps2. для обхода случая когда у вершины более одного минимального ребра можно учитывать номера вершин в с которыми связывает ребро и в случае равенства длин рёбер выбирать ВСЕГДА с меньшим(большим) номером.

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