def bfs(graph,start): visited , queue = set() , [start] while queue != []: verte

Question

def bfs(graph,start):

visited , queue = set() , [start]

while queue != []:

vertex = queue.pop(0) # from queue : pop the oldest

if vertex not in visited:

visited.add(vertex)

queue.extend(graph[vertex] - visited)

return visited

print (bfs(words,'hit'))

###wordlist [hit,hot,dot,dog,cog,log,lot]

###Modify bfs() function to allow the user to enter 'startWord' and 'endWord'. The function should return 'True' if a transformation sequence exists. Return 'False' if there is no such transformation sequence. Notice that you don't need to find the number of transformations. It searches the tree using BFS algorithm to see if a transformation sequence exists

Sample Run

enter startWord : hot

enter endtWord : dog

True  

Explanation / Answer

# To check if two words differ by exactly one character
def isadjacent(a, b):
count = 0
n = len(a)

# If more than 1 mismatched character, return false
for i in range(n):
if a[i] != b[i]:
count += 1
if count > 1:
break

return True if count == 1 else False

# A queue item to store word and minimum chain length to reach the word.
class QItem():
def __init__(self, word):
self.word = word

# Returns length of shortest chain to reach'endWord' from 'startWord'
# using minimum number of adjacent moves. D is dictionary
def bfs(startWord, endWord, D):
# Create a queue for BFS and insert 'startWord' as source vertex
Q = []
item = QItem(startWord)
Q.append(item)

flag = False

while( len(Q) > 0):
curr = Q.pop()

# Go through all words of dictionary
for it in D:

# Process a word if it is adjacent to current word of BFS
temp = it
if isadjacent(curr.word, temp) == True:

# Add the dictionary word to Q
item.word = temp
Q.append(item)

D.remove(temp) # Remove; so that this word is not processed again

# If we reached target
if temp == endWord:
flag = True

if flag == True:
return True
else:
return False

D = ["hit", "hot", "dot", "dog", "cog", "log", "lot"]

startWord = raw_input("Input the start word: ")
endWord = raw_input("Input the end word: ")

print bfs(startWord, endWord, D)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.