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

Есть алгоритм Краскала на языке python class Graph: def init(self, vertex): self.V =…

  1. User

    Есть алгоритм Краскала на языке python class Graph: def init(self, vertex): self.V = vertex self.graph = []

    def add_edge(self, u, v, w): self.graph.append([u, v, w])

    def search(self, parent, i): if parent[i] == i: return i return self.search(parent, parent[i])

    def apply_union(self, parent, rank, x, y): xroot = self.search(parent, x) yroot = self.search(parent, y) if rank[xroot] < rank[yroot]: parent[xroot] = yroot elif rank[xroot] > rank[yroot]: parent[yroot] = xroot else: parent[yroot] = xroot rank[xroot] += 1

    def kruskal(self): result = [] i, e = 0, 0 self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] for node in range(self.V): parent.append(node) rank.append(0) while e < self.V - 1: u, v, w = self.graph[i] i = i + 1 x = self.search(parent, u) y = self.search(parent, v) if x != y: e = e + 1 result.append([u, v, w]) self.apply_union(parent, rank, x, y) for u, v, weight in result: print(“Edge:”,u, v,end =" “) print(”-",weight)

    g = Graph(5) g.add_edge(0, 1, 8) g.add_edge(0, 2, 5) g.add_edge(1, 2, 9) g.add_edge(1, 3, 11) g.add_edge(2, 3, 15) g.add_edge(2, 4, 10) g.add_edge(3, 4, 7) g.kruskal(). Реализуй аналогичный код на языке R

  2. Assistant

    Код на R для алгоритма Краскала:

    определение класса Graph

    Graph <- function(vertex) { V <<- vertex graph <<- data.frame(matrix(ncol = 3, nrow = 0)) }

    добавление ребер в граф

    add_edge <- function(u, v, w) { graph <<- rbind(graph, c(u, v, w)) }

    поиск корня дерева

    search <- function(parent, i) { if (parent[i] == i) return(i) return(search(parent, parent[i])) }

    применение операции объединения для слияния деревьев

    apply_union <- function(parent, rank, x, y) { xroot <- search(parent, x) yroot <- search(parent, y) if (rank[xroot] < rank[yroot]) { parent[xroot] <<- yroot } else if (rank[xroot] > rank[yroot]) { parent[yroot] <<- xroot } else { parent[yroot] <<- xroot rank[xroot] <<- rank[xroot] + 1 } }

    алгоритм Краскала

    kruskal <- function() { result <- data.frame(matrix(ncol = 3, nrow = 0)) i <- 1 e <- 0 graph <<- graph[order(graph[, 3]),] parent <- 0:(V - 1) rank <- rep(0, V) for (node in 1:V) { parent[node] <- node } while (e < V - 1) { u <- graph[i, 1] v <- graph[i, 2] w <- graph[i, 3] i <<- i + 1 x <- search(parent, u) y <- search(parent, v) if (x != y) { e <<- e + 1 result <<- rbind(result, c(u, v, w)) apply_union(parent, rank, x, y) } } colnames(result) <<- c("u", "v", "weight") return(result) }

    пример использования

    g <- Graph(5) add_edge(0, 1, 8) add_edge(0, 2, 5) add_edge(1, 2, 9) add_edge(1, 3, 11) add_edge(2, 3, 15) add_edge(2, 4, 10) add_edge(3, 4, 7) kruskal()

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.