Word Ladder 挑战中的图表不正确

Question

我正在尝试实现单词阶梯问题，我必须在最短路径中将一个单词转换为另一个单词possible.Obviously我们可以使用广度优先搜索 (BFS) 来解决它，但在此之前我们必须首先绘制 graph.I 已经实现了桶的概念，其中某些词如果与桶相匹配则属于桶 type.But 我的图表没有正确实现。

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

所以对于每个单词，我可以为单词 'CAT' 创建一个 bucket.For 示例，我可以有三个桶 _AT、C_T、CA_。同样，我可以为其余单词创建桶，匹配桶类型的单词将落入这些桶中。

用手实现应该给我这样的图表

因为图是无向的，所以对于顶点 COG，它的相邻顶点应该是 DOG、COW、COT（关系是双向的）但是我得到的是 COG 连接到 nothing.Here 是我的代码以下

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

    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.addVertex(f).addNeighbour(self.addVertex(t),cost)

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

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


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

# get the graph object
gobj = buildGraph(wordList)

for v in gobj: #the graph contains a set of vertices
    print(v)

我得到的结果是

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

我希望结果是这样的

BUT is connected to ['BAT', 'CUT']
CUT is connected to ['CAT', 'COT', 'BUT']
and so on....

我做错了什么？

Answer 1

问题出在您的 addEdge 方法中。

您正在检查图中是否已经存在顶点，好的。但是，如果它们存在，那么您无论如何都会创建新顶点并为这些新顶点添加边，从而丢弃以前的顶点。这就是为什么最后每个顶点只有一条边。

只需将 addEdge 的最后一行更改为：

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

Word Ladder 挑战中的图表不正确

Incorrect graph in Word Ladder challenge

graph

python-3.x

undirected-graph