请帮我看个word-ladder 的解法

hmchzb19

我这里的代码都是参照这里的：http://interactivepython.org/run ... dLadderProblem.html
但是BFS 的代码我就不知道怎么搞了，因为BFS不返回，也没有stop,只有start.

1. class Vertex:
   
2.     def __init__(self,key,distance=0,pred=None,color="white"):
   
3.         self.id=key
   
4.         self.connectedTo={}             #dict which contains all the other vertices it is connected to
   
5.         self.pred=pred                  #for BFS tree/a list because we are dealing with cycles
   
6.         self.color=color                #for BFS tree
   
7.         self.distance=distance
   
8. 
   
9.     def addNeighbor(self,nbr,weight=0):
   
10.         self.connectedTo[nbr]=weight
    
11. 
    
12.     def __str__(self):
    
13.         return str(self.id)+' connectedTo: '+str([x.id for x in self.connectedTo])
    
14.         
    
15.     def getConnections(self):
    
16.         return self.connectedTo.keys()
    
17. 
    
18.     def getId(self):
    
19.         return self.id
    
20. 
    
21.     def getWeight(self,nbr):
    
22.         return self.connectedTo[nbr]
    
23.    
    
24.     def setPred(self,node):
    
25.         self.pred=node
    
26. 
    
27.     def getPred(self):
    
28.         return self.pred
    
29.    
    
30.     def setDistance(self,distance):
    
31.         self.distance=distance
    
32. 
    
33.     def getDistance(self):
    
34.         return self.distance
    
35.    
    
36.     def setColor(self,color):
    
37.         self.color=color
    
38. 
    
39.     def getColor(self):
    
40.         return self.color
    
41. 
    
42. 
    
43. #adjacency list implemented of the graph
    
44. class Graph:
    
45.     def __init__(self):
    
46.         self.vertList={}
    
47.         self.numVertices=0
    
48. 
    
49.     def addVertex(self,key):
    
50.         self.numVertices=self.numVertices+1
    
51.         newVertice=Vertex(key)
    
52.         self.vertList[key]=newVertice
    
53.         return newVertice
    
54. 
    
55.     def getVertex(self,n):
    
56.         if n in self.vertList:
    
57.             return self.vertList[n]
    
58.         else:
    
59.             return None
    
60. 
    
61.     def __contains__(self,n):
    
62.         return n in self.vertList
    
63. 
    
64.     def addEdge(self,f,t,cost=0):
    
65.         if f not in self.vertList:
    
66.             nv=self.addVertex(f)
    
67.         if t not in self.vertList:
    
68.             nv=self.addVertex(t)
    
69.         self.vertList[f].addNeighbor(self.vertList[t],cost)
    
70. 
    
71.     def getVertices(self):
    
72.         return self.vertList.keys()
    
73. 
    
74.     def __iter__(self):
    
75.         return iter(self.vertList.values())
    
76. 
    

复制代码

1. #build thw word Ladder Graph
   
2. def buildGraph(wordFile="words.txt"):
   
3.     d={}
   
4.     g=Graph()
   
5.     wfile=open(wordFile,"r")
   
6.     #create bucket of words that differ by one letter
   
7.     for line in wfile:
   
8.         word=line[:-1]
   
9.         for i in range(len(word)):
   
10.             bucket=word[:i]+'_'+word[i+1:]
    
11.             if bucket in d:
    
12.                 d[bucket].append(word)
    
13.             else:
    
14.                 d[bucket]=[word]
    
15. 
    
16.     #add vertices and edges for words in the same bucket
    
17.     for bucket in d.keys():
    
18.         for word1 in d[bucket]:
    
19.             for word2 in d[bucket]:
    
20.                 if word1!=word2:
    
21.                     g.addEdge(word1,word2)
    
22.     return g
    

复制代码

words.txt 是4个字母组成的单词共有3686个。

1. wc -l words.txt
   
2. 3685 words.txt
   

复制代码

BFS 什么都不返回。
BFS2 返回一个字典，但是BFS2返回的结果跟我预计的总是不对

1. def bfs(g,start):
   
2.     start.setDistance(0)
   
3.     start.setPred(None)
   
4.     vertQueue=[]
   
5.     vertQueue.append(start)
   
6.     while len(vertQueue) > 0:
   
7.         currentVert=vertQueue.pop(0)
   
8.         for nbr in currentVert.getConnections():
   
9.             if (nbr.getColor()=='white'):
   
10.                 nbr.setColor("gray")
    
11.                 nbr.setDistance(currentVert.getDistance()+1)
    
12.                 nbr.setPred(currentVert)
    
13.                 vertQueue.append(nbr)
    
14.         currentVert.setColor('black')
    
15. 
    
16. 
    
17. def bfs2(g,start,stop):
    
18.     parents={}
    
19.     q=[]
    
20.     q.append(start)
    
21.     parents[start.id]=None
    
22. 
    
23.     while len(q)> 0:
    
24.         node=q.pop(0)
    
25.         for neighbour in node.getConnections():
    
26.             n=neighbour.id
    
27. 
    
28.             if n not in parents:
    
29.                 parents[n]=node.id
    
30.                 if n==stop.id:
    
31.                     return parents
    
32.                 q.append(neighbour)
    
33. 
    
34.     return parents

复制代码

1.     g=buildGraph()
   
2.     start=g.addVertex("fool")
   
3.     stop=g.addVertex("sage")
   
4.     path=bfs2(g,start,stop)
   
5.     print(path)
   

复制代码

结果是
{'fool': None}

rubyish

FOR print(path)
HERE:

1. 
   
2. start = g.addVertex("fool")
   
3. 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?

1. 
   
2. newVertice = Vertex(key)    # self.connectedTo = {}
   
3. self.vertList[key] = newVertice
   

复制代码

3: SO getConnections == []
4: HOW? use:

1. 
   
2. start = g.getVertex('fool')
   
3. stop  = g.getVertex('sage')
   

复制代码

1 ge bfs2 de lizi:

dict = [ 'hot', 'dot', 'dog', 'lot', 'log', 'hit', 'cog' ]
star = 'hit'
stop = 'cog'

output:

1. hit | hot | lot | log | cog
   
2. hit | hot | dot | dog | cog
   

复制代码

1. #!/usr/bin/perl
   
2. use 5.018;
   
3. 
   
4. my %Graph;
   
5. 
   
6. sub buildGraph {
   
7.     my $dic = shift;
   
8.     my $end = length( $dic->[0] ) - 1;
   
9.     for my $word (@$dic) {
   
10.         for ( 0 .. $end ) {
    
11.             my $pat = $word;
    
12.             substr( $pat, $_, 1 ) = '.';
    
13.             push @{ $Graph{$pat} }, $word;
    
14.         }
    
15.     }
    
16. }
    
17. 
    
18. sub getConnections {
    
19.     my $node = shift;
    
20.     map {
    
21.         my $p = $node;
    
22.         substr( $p, $_, 1 ) = '.';
    
23.         @{ $Graph{$p} || [] }
    
24.     } 0 .. length($node) - 1;
    
25. }
    
26. 
    
27. sub bfs2 {
    
28.     my ( $star, $stop ) = @_;
    
29.     my ( @todo, %has, %link ) = $star;
    
30. 
    
31.     while (@todo) {
    
32.         my %next;
    
33.         $has{$_} ||= 1 for @todo;
    
34.         for my $node (@todo) {
    
35.             for my $neibeer ( getConnections $node ) {
    
36.                 next if $has{$neibeer};
    
37.                 $next{$neibeer} ||= 1;
    
38.                 push @{ $link{$neibeer} }, $node;
    
39.             }
    
40.         }
    
41.         @todo = keys %next;
    
42.     }
    
43. 
    
44.     sub {
    
45.         my ( $word, $a ) = @_;
    
46.         return join ' | ', $word, @$a if $word eq $star;
    
47.         map { __SUB__->( $_, [ $word, @$a ] ) } @{ $link{$word} };
    
48.     } ->( $stop, [] );
    
49. }
    
50. 
    
51. my $dict = [ 'hot', 'dot', 'dog', 'lot', 'log', 'hit', 'cog' ];
    
52. my $star = 'hit';
    
53. my $stop = 'cog';
    
54. 
    
55. buildGraph $dict;
    
56. my @path = bfs2 $star, $stop;
    
57. say for @path;
    

复制代码