# Find a path that contains specific nodes without back and forward edges

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:

but for the same set of nodes the following paths are not acceptable:

and

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?

• What do you mean by "this path dont contain back edges(cycles) and forward edges"? The third example you give is even not a path. Please formally describe your question. – xskxzr Mar 17 '18 at 18:25