1

我正在尝试实现单词阶梯问题，我必须尽可能以最短的路径将一个单词转换为另一个单词。显然我们可以使用广度优先搜索（BFS）来解决它，但在此之前我们必须先绘制图表。我有实现了桶的概念，如果某些单词与桶类型匹配，则它们属于桶。但我的图表没有正确实现。

给定的单词列表是 ["CAT", "BAT", "COT", "COG", "COW", "RAT", "BUT", "CUT", "DOG", "WED"]

所以对于每个单词我可以创建一个桶。例如对于单词'CAT'，我可以有三个桶_AT，C_T，CA_。类似地，我可以为其余的单词创建存储桶，并且与存储桶类型匹配的单词将属于这些存储桶。

我用图形表达问题的代码工作正常，我得到这样的图形（理论上） 在此处输入图像描述

现在我需要找到将“CAT”转换为“DOG”的最短操作数。所以我使用 BFS 的修改方法来实现它。当我制作自己的示例图时它工作正常。例如

graph = {'COG': ['DOG', 'COW', 'COT'], 'CAT': ['COT', 'BAT', 'CAT', 'RAT'], 'BUT': ['CUT', 'BAT'], 'DOG': ['COG']}

代码工作正常，我得到了正确的结果。但是如果我有一个巨大的单词列表，比如 1500，那么键入并创建这么长的字典是不可行的。所以我创建了一个函数，从列表中获取这些单词，实现我在上面讨论过的技术并为我创建了图表，直到这里都可以正常工作。但是当我尝试获得两个单词之间的最短距离时，出现以下错误

for neighbour in neighbours:
TypeError: 'Vertex' object is not iterable

这是我下面的代码

class Vertex:
    def __init__(self,key):
        self.id = key
        self.connectedTo = {}

    # add neighbouring vertices to the current vertex along with the edge weight
    def addNeighbour(self,nbr,weight=0):
        self.connectedTo[nbr] = weight

    #string representation of the object
    def __str__(self):
        return str(self.id) + " is connected to " + str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self,nbr):
        return self.connectedTo[nbr]

class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self,key):
        self.numVertices += 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self,n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def addEdge(self,f,t,cost=0):
        if f not in self.vertList:
            nv = self.addVertex(f)

        if t not in self.vertList:
            nv = self.addVertex(t)

        self.vertList[f].addNeighbour(self.vertList[t],cost)

    def getVertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())

# I have only included few words in the list to focus on the implementation
wordList = ["CAT", "BAT", "COT", "COG", "COW", "RAT", "BUT", "CUT", "DOG", "WED"]

def buildGraph(wordList):
    d = {} #in this dictionary the buckets will be the keys and the words will be their values
    g = Graph()
    for i in wordList:
        for j in range(len(i)):
            bucket = i[:j] + "_" + i[j+1:]
            if bucket in d:
                #we are storing the words that fall under the same bucket in a list 
                d[bucket].append(i)
            else:
                d[bucket] = [i]

    # create vertices for the words under the buckets and join them
    #print("Dictionary",d)
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                #we ensure same words are not treated as two different vertices
                if word1 != word2:
                    g.addEdge(word1,word2)
    return g

def bfs_shortest_path(graph, start, goal):
    explored = []
    queue = [[start]]
    if start == goal:
        return "The starting node and the destination node is same"
    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node not in explored:
            neighbours = graph[node] # it shows the error here
            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)
                if neighbour == goal:
                    return new_path

            explored.append(node)

    return "No connecting path between the two nodes"

# get the graph object
gobj = buildGraph(wordList)
# just to check if I am able to fetch the data properly as mentioned above where I get the error (neighbours = graph[node])
print(gobj["CAT"]) # ['COT', 'BAT', 'CUT', 'RAT']
print(bfs_shortest_path(gobj, "CAT", "DOG"))

要检查每个顶点的相邻顶点，我们可以这样做

for v in gobj:
    print(v)

得到的输出如下正确地描述了上面的图表。

CAT is connected to ['COT', 'BAT', 'CUT', 'RAT']
RAT is connected to ['BAT', 'CAT']
COT is connected to ['CUT', 'CAT', 'COG', 'COW']
CUT is connected to ['COT', 'BUT', 'CAT']
COG is connected to ['COT', 'DOG', 'COW']
DOG is connected to ['COG']
BUT is connected to ['BAT', 'CUT']
BAT is connected to ['BUT', 'CAT', 'RAT']
COW is connected to ['COT', 'COG']
CAT is connected to ['COT', 'BAT', 'CUT', 'RAT']

那会出什么问题呢？

4

1 回答 1

0

好的，所以我发现了问题。问题出在这行代码中

neighbours = graph[node]

基本上它正在尝试获取特定节点的邻居。因此它需要访问vertList声明为类属性的字典。因此，要访问字典Graph值的对象，必须实现一种__getitem__特殊方法。所以我声明了这一点类下Graph如下

# returns the value for the key which will be an object    
def __getitem__(self, key):
    return self.vertList[key]

现在graph[node]将能够获取节点的对象表示，因为vertList字典的值是一个顶点对象（vertList将顶点名称存储为键，顶点对象存储为值）。所以我必须明确告诉它获取对象的邻居而不是对象本身。所以我可以调用类getConnections()下的方法，该方法Vertex进一步调用connectedTo属性来获取特定顶点对象的邻居对象。（connectedTo字典将顶点对象作为键，边权重作为值。）

所以现在这些邻居对象将拥有自己的 id，我可以访问它们并将其用于 BFS 操作。下面的行是bfs_shortest_path完成上述工作的修改后的代码（在方法下）。

if node not in explored:
    neighbours = [x.id for x in graph[node].getConnections()]

现在我得到了特定节点的邻居列表并使用它。其余代码保持不变。

于 2017-11-16T17:11:09.727 回答