I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For example for set = [1,3,4] the following path is acceptable:
First of all i thought that it would be a good step to write bfs code for finding the nodes that i can visit from a specific starting node. Here is my code:
def bfs(G, s): q = queue.Queue() visited =  #Put s onto a FIFO queue q.put(s) #mark s as visited visited.append(s) #Repeat until the queue is empty while not q.empty(): #remove the least recently added vertex v v = q.get() #for each unmarked vertex pointing from v: #add to queue and mark as visited for node in G.neighbors(v): if node not in visited: q.put(node) visited.append(node) print(visited)
Does anyone have any idea about how to modify bfs algorithm for finding the path containing specific nodes without back and forward edges? Can you write a pseudocode example?