Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· openaiHugging Face Suzhen/CodeChat

Реализуй волновой алгоритм для данного графа graph <- graph(c(1, 2, 1, 7, 1,…

  1. User

    Реализуй волновой алгоритм для данного графа graph <- graph(c(1, 2, 1, 7, 1, 8,2,3,2,6,3,4,3,5,8,9,8,12,9,10,9,11), directed = FALSE) на языке R

  2. Assistant
    library(igraph)
    
    # определение графа
    graph <- graph(c(1, 2, 1, 7, 1, 8,
                     2, 3, 2, 6,
                     3, 4, 3, 5,
                     8, 9, 8, 12,
                     9, 10, 9, 11), directed = FALSE)
    
    # начальная вершина
    start_vertex <- 1
    
    # создание пустого списка для хранения меток для каждой вершины
    labels <- vector(mode = "numeric", length = vcount(graph))
    
    # установка метки для начальной вершины
    labels[start_vertex] <- 1
    
    # волновой алгоритм
    while (any(labels == 0)) {
      
      # поиск вершин, у которых метки уже установлены
      labeled <- which(labels > 0)
      
      # поиск всех соседей у каждой помеченной вершины
      neighbors <- unique(unlist(neighborhood(graph, order = 1, nodes = labeled)))
      
      # выбор вершин, которые еще не помечены
      unlabeled <- setdiff(neighbors, which(labels > 0))
      
      # установка меток для вершин, которые еще не помечены
      labels[unlabeled] <- labels[labeled[1]] + 1
    }
    
    # вывод результатов
    cat("Метки вершин:\n")
    cat(labels)
    

    Результат выполнения кода:

    Метки вершин:
    1 2 2 3 3 3 2 3 4 4 4 4