Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

#------------------------------------------------- Алгоритм Краскала поиска минимального…

  1. User

    #-------------------------------------------------

    Алгоритм Краскала поиска минимального остова графа

    #-------------------------------------------------

    список ребер графа (длина, вершина 1, вершина 2)

    R = [(13, 1, 2), (18, 1, 3), (17, 1, 4), (14, 1, 5), (22, 1, 6), (26, 2, 3), (22, 2, 5), (3, 3, 4), (19, 4, 6)]

    Rs = sorted(R, key=lambda x: x[0]) U = set() # список соединенных вершин D = {} # словарь списка изолированных групп вершин T = [] # список ребер остова

    for r in Rs: if r[1] not in U or r[2] not in U: # проверка для исключения циклов в остове if r[1] not in U and r[2] not in U: # если обе вершины не соединены, то D[r[1]] = [r[1], r[2]] # формируем в словаре ключ с номерами вершин D[r[2]] = D[r[1]] # и связываем их с одним и тем же списком вершин else: # иначе if not D.get(r[1]): # если в словаре нет первой вершины, то D[r[2]].append(r[1]) # добавляем в список первую вершину D[r[1]] = D[r[2]] # и добавляем ключ с номером первой вершины else: D[r[1]].append(r[2]) # иначе, все то же самое делаем со второй вершиной D[r[2]] = D[r[1]]

        T.append(r)             # добавляем ребро в остов
        U.add(r[1])             # добавляем вершины в множество U
        U.add(r[2])
    

    for r in Rs: # проходим по ребрам второй раз и объединяем разрозненные группы вершин if r[2] not in D[r[1]]: # если вершины принадлежат разным группам, то объединяем T.append(r) # добавляем ребро в остов gr1 = D[r[1]] D[r[1]] += D[r[2]] # объединем списки двух групп вершин D[r[2]] += gr1

    print(T) Данный код написан на python, перепиши его в R

  2. Assistant

    #-------------------------------------------------

    Алгоритм Краскала поиска минимального остова графа

    #-------------------------------------------------

    список ребер графа (длина, вершина 1, вершина 2)

    R <- list(list(13, 1, 2), list(18, 1, 3), list(17, 1, 4), list(14, 1, 5), list(22, 1, 6), list(26, 2, 3), list(22, 2, 5), list(3, 3, 4), list(19, 4, 6))

    Rs <- R[order(sapply(R, function(x) x[1]))] # отсортируем ребра по длине U <- c() # список соединенных вершин D <- list() # словарь списка изолированных групп вершин T <- list() # список ребер остова

    for (r in Rs) { if (!(r[2] %in% U) || !(r[3] %in% U)) { # проверка для исключения циклов в остове if (!(r[2] %in% U) && !(r[3] %in% U)) { # если обе вершины не соединены, то D[[r[2]]] <- c(r[2], r[3]) # формируем в словаре ключ с номерами вершин D[[r[3]]] <- D[[r[2]]] # и связываем их с одним и тем же списком вершин } else { # иначе if (length(D[[r[2]]]) == 0) { # если в словаре нет первой вершины, то D[[r[3]]] <- c(r[3], r[2]) # добавляем в список первую вершину D[[r[2]]] <- D[[r[3]]] # и добавляем ключ с номером первой вершины } else { # иначе, все то же самое делаем со второй вершиной D[[r[2]]] <- c(D[[r[2]]], r[3]) D[[r[3]]] <- D[[r[2]]] } } T <- c(T, list(r)) # добавляем ребро в остов U <- c(U, r[2]) # добавляем вершины в список U U <- c(U, r[3]) } }

    for (r in Rs) { # проходим по ребрам второй раз и объединяем разрозненные группы вершин if (!(r[3] %in% D[[r[2]]])) { # если вершины принадлежат разным группам, то объединяем T <- c(T, list(r)) # добавляем ребро в остов gr1 <- D[[r[2]]] D[[r[2]]] <- c(D[[r[2]]], D[[r[3]]]) # объединем списки двух групп вершин D[[r[3]]] <- c(D[[r[3]]], gr1) } }

    print(T)