1
$\begingroup$

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: enter image description here

but for the same set of nodes the following paths are not acceptable: enter image description here

and

enter image description here

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – xskxzr Mar 17 '18 at 18:25
0
$\begingroup$

This is the Hamiltonian path problem. No efficient algorithm is known, and it is widely suspected that no efficient algorithm exists. You can read the linked article for references that suggest a variety of algorithms for this problem.

$\endgroup$
  • $\begingroup$ I don't think it's this problem, since the vertices on a Hamiltonian path may induce additional edges, but the OP forbids these. But I think the OP is overcomplicating things -- either the given set of vertices induces a cycle, in which case it's easy to find, or it doesn't (also easy to detect). $\endgroup$ – j_random_hacker Mar 17 '18 at 21:02
  • $\begingroup$ I think op does not forbid edges in general, but edges leading to other notes on the path. $\endgroup$ – Dániel Somogyi Jun 16 '18 at 13:18
  • $\begingroup$ @j_random_hacker, you could be right, but that's not how I read it. As I read it, the question says "I want to find a path" not "I want to find a set of vertices and all edges induced by those vertices", and I don't see any indication that any additional induced edges are automatically added to the path. $\endgroup$ – D.W. Jun 16 '18 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.