我正确理解了Prim算法,但是很难使用Python代码。我该如何实现?

问题描述 投票:0回答:1

我知道它的工作原理,并且弄清楚了为什么这很重要。但是将其移动到python代码对我来说太困难了。因此,我想在分析您共享的代码时学习。你能帮我吗?

class Graph:

  def __init__(self, nodes, matrix):
    self.nodes = nodes
    self.matrix = matrix

  def execute_prim(self):
      #구현
    compare_zone=[]

    for i in range (len(nodes)):
      if self.matrix[i][0] > 0:
        compare_zone.append(matrix[i][0])
      print(compare_zone)
    self.print_result()

  def print_result(self):
    for node in self.nodes:
      if node.get_memo() is not None:
        print( node.get_data() + ' - ' + node.get_memo().get_data() + 
              ' (' + str(node.get_key()) + ')')

这是图形矩阵

matrix = [[0, 4, 0, 0, 0, 0, 0, 8, 0], # w.r.t node A
          [4, 0, 8, 0, 0, 0, 0, 11, 0], # w.r.t node B
          [0, 8, 0, 7, 0, 4, 0, 0, 2], # w.r.t node C
          [0, 0, 7, 0, 9, 14, 0, 0, 0], # w.r.t node D
          [0, 0, 0, 9, 0, 10, 0, 0, 0], # w.r.t node E
          [0, 0, 4, 14, 10, 0, 2, 0, 0], # w.r.t node F
          [0, 0, 0, 0, 0, 2, 0, 1, 6], # w.r.t node G
          [8, 11, 0, 0, 0, 0, 1, 0, 7], # w.r.t node H
          [0, 0, 2, 0, 0, 0, 6, 7, 0]] # w.r.t node I

Python

import sys


class Node:

    index = 0

    def __init__(self, data):
        self.index = Node.index
        Node.index += 1
        self.data = data
        self.neighbors = []

        self.key = sys.maxsize
        self.memo = None
        self.is_done = False

    def get_index(self):
        return self.index

    def get_data(self):
        return self.data

    def get_neighbors(self):
        return self.neighbors

    def get_key(self):
        return self.key

    def get_memo(self):
        return self.memo

    def get_is_done(self):
        return self.is_done

    def add_neighbor(self, neighbor):
        self.neighbors.append(neighbor)

    def set_key(self, key, memo):
        if(self.key > key):
            self.key = key
            self.memo = memo

    def set_is_done(self):
        self.is_done = True


class Graph:

    def __init__(self, nodes, matrix):
        self.nodes = nodes
        self.matrix = matrix

    def execute_prim(self):
            # How can I build it?

        for i in range(len(nodes)):
            if self.matrix[i][0] > 0:
                compare_zone.append(matrix[i][0])
            print(compare_zone)
        self.print_result()

    def print_result(self):
        for node in self.nodes:
            if node.get_memo() is not None:
                print(node.get_data() + ' - ' + node.get_memo().get_data() +
                      ' (' + str(node.get_key()) + ')')


# create an array whose elements are alphabets from 'A' to 'I' using ascii code
dataset = []
for i in range(65, 74):
    dataset.append(chr(i))

# create nodes
nodes = []
for data in dataset:
    nodes.append(Node(data))

# create matrix for weights
matrix = [[0, 4, 0, 0, 0, 0, 0, 8, 0],  # w.r.t node A
          [4, 0, 8, 0, 0, 0, 0, 11, 0],  # w.r.t node B
          [0, 8, 0, 7, 0, 4, 0, 0, 2],  # w.r.t node C
          [0, 0, 7, 0, 9, 14, 0, 0, 0],  # w.r.t node D
          [0, 0, 0, 9, 0, 10, 0, 0, 0],  # w.r.t node E
          [0, 0, 4, 14, 10, 0, 2, 0, 0],  # w.r.t node F
          [0, 0, 0, 0, 0, 2, 0, 1, 6],  # w.r.t node G
          [8, 11, 0, 0, 0, 0, 1, 0, 7],  # w.r.t node H
          [0, 0, 2, 0, 0, 0, 6, 7, 0]]  # w.r.t node I

# set neighbor relation
for i in range(0, len(nodes)):
    for j in range(i+1, len(nodes)):
        if matrix[i][j] > 0:
            nodes[i].add_neighbor(nodes[j])
            nodes[j].add_neighbor(nodes[i])

# create a graph
graph = Graph(nodes, matrix)

# execute prim algorithm
graph.execute_prim()


期望的输出

B-A(4)C-B(8)D-C(7)E-D(9)F-C(4)G-F(2)H-G(1)I-C(2)


这是我的prim Algorithm的完整代码,请帮助我。

python algorithm graph minimum-spanning-tree
1个回答
© www.soinside.com 2019 - 2024. All rights reserved.