请帮我看个word-ladder 的解法
本帖最后由 hmchzb19 于 2016-04-03 16:12 编辑我这里的代码都是参照这里的：http://interactivepython.org/runestone/static/pythonds/Graphs/TheWordLadderProblem.html
但是BFS 的代码我就不知道怎么搞了，因为BFS不返回，也没有stop,只有start.class Vertex:
def __init__(self,key,distance=0,pred=None,color="white"):
self.id=key
self.connectedTo={} #dict which contains all the other vertices it is connected to
self.pred=pred #for BFS tree/a list because we are dealing with cycles
self.color=color #for BFS tree
self.distance=distance
def addNeighbor(self,nbr,weight=0):
self.connectedTo=weight
def __str__(self):
return str(self.id)+' connectedTo: '+str()
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self,nbr):
return self.connectedTo
def setPred(self,node):
self.pred=node
def getPred(self):
return self.pred
def setDistance(self,distance):
self.distance=distance
def getDistance(self):
return self.distance
def setColor(self,color):
self.color=color
def getColor(self):
return self.color
#adjacency list implemented of the graph
class Graph:
def __init__(self):
self.vertList={}
self.numVertices=0
def addVertex(self,key):
self.numVertices=self.numVertices+1
newVertice=Vertex(key)
self.vertList=newVertice
return newVertice
def getVertex(self,n):
if n in self.vertList:
return self.vertList
else:
return None
def __contains__(self,n):
return n in self.vertList
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.addNeighbor(self.vertList,cost)
def getVertices(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
#build thw word Ladder Graph
def buildGraph(wordFile="words.txt"):
d={}
g=Graph()
wfile=open(wordFile,"r")
#create bucket of words that differ by one letter
for line in wfile:
word=line[:-1]
for i in range(len(word)):
bucket=word[:i]+'_'+word
if bucket in d:
d.append(word)
else:
d=
#add vertices and edges for words in the same bucket
for bucket in d.keys():
for word1 in d:
for word2 in d:
if word1!=word2:
g.addEdge(word1,word2)
return g
words.txt 是4个字母组成的单词共有3686个。wc -l words.txt
3685 words.txt
BFS 什么都不返回。
BFS2 返回一个字典，但是BFS2返回的结果跟我预计的总是不对def bfs(g,start):
start.setDistance(0)
start.setPred(None)
vertQueue=[]
vertQueue.append(start)
while len(vertQueue) > 0:
currentVert=vertQueue.pop(0)
for nbr in currentVert.getConnections():
if (nbr.getColor()=='white'):
nbr.setColor("gray")
nbr.setDistance(currentVert.getDistance()+1)
nbr.setPred(currentVert)
vertQueue.append(nbr)
currentVert.setColor('black')
def bfs2(g,start,stop):
parents={}
q=[]
q.append(start)
parents=None
while len(q)> 0:
node=q.pop(0)
for neighbour in node.getConnections():
n=neighbour.id
if n not in parents:
parents=node.id
if n==stop.id:
return parents
q.append(neighbour)
return parents g=buildGraph()
start=g.addVertex("fool")
stop=g.addVertex("sage")
path=bfs2(g,start,stop)
print(path)
结果是
{'fool': None} FOR print(path)
HERE:
start = g.addVertex("fool")
stop= g.addVertex("sage")
if fool, sage not in wordslist:
1: addEdge for fool, sage!
2: WHY? NO edge => NO connectedTo => getConnections == []
3: HOW? ADD fool, sage TO wordslist
if fool, sage in wordslist
1: you RESET connectedTo = {}
2: WHY?
newVertice = Vertex(key) # self.connectedTo = {}
self.vertList = newVertice
3: SO getConnections == []
4: HOW? use:
start = g.getVertex('fool')
stop= g.getVertex('sage')
1 ge bfs2 de lizi:
dict = [ 'hot', 'dot', 'dog', 'lot', 'log', 'hit', 'cog' ]
star = 'hit'
stop = 'cog'
output:hit | hot | lot | log | cog
hit | hot | dot | dog | cog
#!/usr/bin/perl
use 5.018;
my %Graph;
sub buildGraph {
my $dic = shift;
my $end = length( $dic-> ) - 1;
for my $word (@$dic) {
for ( 0 .. $end ) {
my $pat = $word;
substr( $pat, $_, 1 ) = '.';
push @{ $Graph{$pat} }, $word;
}
}
}
sub getConnections {
my $node = shift;
map {
my $p = $node;
substr( $p, $_, 1 ) = '.';
@{ $Graph{$p} || [] }
} 0 .. length($node) - 1;
}
sub bfs2 {
my ( $star, $stop ) = @_;
my ( @todo, %has, %link ) = $star;
while (@todo) {
my %next;
$has{$_} ||= 1 for @todo;
for my $node (@todo) {
for my $neibeer ( getConnections $node ) {
next if $has{$neibeer};
$next{$neibeer} ||= 1;
push @{ $link{$neibeer} }, $node;
}
}
@todo = keys %next;
}
sub {
my ( $word, $a ) = @_;
return join ' | ', $word, @$a if $word eq $star;
map { __SUB__->( $_, [ $word, @$a ] ) } @{ $link{$word} };
} ->( $stop, [] );
}
my $dict = [ 'hot', 'dot', 'dog', 'lot', 'log', 'hit', 'cog' ];
my $star = 'hit';
my $stop = 'cog';
buildGraph $dict;
my @path = bfs2 $star, $stop;
say for @path;
页:
[1]