0

我需要在 Python 中实现 Dijkstra 算法。但是，我必须使用 2D 数组来保存三条信息——前任、长度和未访问/已访问。我知道在 C 中可以使用 Struct，虽然我被困在如何在 Python 中做类似的事情，我被告知这是可能的，但我不知道说实话

4

5 回答 5

2

为它创建一个类。

class XXX(object):
    def __init__(self, predecessor, length, visited):
        self.predecessor = predecessor
        self.length = length
        self.visited = visited

或者使用 collections.namedtuple，这对于保存没有自己的行为但命名成员的类似结构的复合类型特别酷：XXX = collections.namedtuple('XXX', 'predecessor length visited').

用XXX(predecessor, length, visited).

于 2011-02-10T20:25:41.417 回答
1

将该信息封装在 Python 对象中，您应该没问题。

于 2011-02-10T20:23:02.400 回答
1

或者您可以简单地在二维数组中使用元组或字典：

width=10
height=10

my2darray = []
for x in range(width):
   my2darray[x]=[]

for x in range(width):
   for y in range(height):
      #here you set the tuple
      my2darray[x][y] = (n,l,v) 
      #or you can use a dict..
      my2darray[x][y] = dict(node=foo,length=12,visited=False)
于 2011-02-10T20:29:52.780 回答
1

如上所述，您可以使用对象的实例。

这位作者在 python 中有一个非常令人信服的 Dijkstras 的 python 实现。

#
# This file contains the Python code from Program 16.16 of
# "Data Structures and Algorithms
# with Object-Oriented Design Patterns in Python"
# by Bruno R. Preiss.
#
# Copyright (c) 2003 by Bruno R. Preiss, P.Eng.  All rights reserved.
#
# http://www.brpreiss.com/books/opus7/programs/pgm16_16.txt
#
class Algorithms(object):

    def DijkstrasAlgorithm(g, s):
        n = g.numberOfVertices
        table = Array(n)
        for v in xrange(n):
            table[v] = Algorithms.Entry()
        table[s].distance = 0
        queue = BinaryHeap(g.numberOfEdges)
        queue.enqueue(Association(0, g[s]))
        while not queue.isEmpty:
            assoc = queue.dequeueMin()
            v0 = assoc.value
            if not table[v0.number].known:
                table[v0.number].known = True
                for e in v0.emanatingEdges:
                    v1 = e.mateOf(v0)
                    d = table[v0.number].distance + e.weight
                    if table[v1.number].distance > d:

                        table[v1.number].distance = d
                        table[v1.number].predecessor = v0.number
                        queue.enqueue(Association(d, v1))
        result = DigraphAsLists(n)
        for v in xrange(n):
            result.addVertex(v, table[v].distance)
        for v in xrange(n):
            if v != s:
                result.addEdge(v, table[v].predecessor)
        return result
    DijkstrasAlgorithm = staticmethod(DijkstrasAlgorithm)

请注意，这些信息被“保存”在他通过调用 Algorithms.Entry() 构建的对象中。Entry 是一个类，定义如下：

class Entry(object):
    """
    Data structure used in Dijkstra's and Prim's algorithms.
    """

    def __init__(self):
        """
        (Algorithms.Entry) -> None
        Constructor.
        """
        self.known = False
        self.distance = sys.maxint
        self.predecessor = sys.maxint

self.known, self.distance... 就是这些信息。他没有在构造函数（init）中显式设置这些，而是​​稍后设置它们。在 Python 中，您可以使用点表示法访问属性。例如：myObject=Entry()。myObject.known、myObject.distance...它们都是公开的。

于 2011-02-10T20:57:13.740 回答
0

Python是面向对象的语言。所以把它想象成从 C 中的结构转移到 C++ 的类。您也可以在 Python 中使用相同的类结构。

于 2011-02-10T20:29:44.597 回答