0

This is similar to How to trace the path in a Breadth-First Search?, but the method described in the answers in that post doesn't work for my case, it seems.

By path here, I essentially mean a sequence of connected nodes to get from a beginning to end state.

Consider an undirected graph with vertices V={a,b,c} and edges = {{a,b},{a,c}}, and assume that we must traverse the successors alphabetically. We start at node a and the end state is to visit all 3 nodes.

Breadth first search would first visit the edge a->b, and then the edge a->c. So the solution path is a->b->a->c. Since there is no edge between b & c, we must go back through a (so we must traverse the edge b->a). In the answer in the above linked post, the accepted solution would only output a->c.

I can't think of a way to modify the conventional bfs algorithm to do this. I have the same question for dfs, but I'd like to start with bfs for now.

24n8
  • 1,898
  • 1
  • 12
  • 25
  • 1
    `a->b->a->c` represents the sequence of nodes visited. The path is not that sequence. The path from `a` to `c` does not go through `b` but directly `a>c`. – c0der Feb 09 '20 at 18:08
  • But if you're traversing the successors alphabetically, the path to get to `c` from `a` will have to go through `b`. – 24n8 Feb 09 '20 at 18:29
  • That's right. You are traversing to search for the path. The traversing sequence is indeed `a->b->a->c` . The path found is `a->c` – c0der Feb 10 '20 at 07:34
  • Please respond to the two answers posted – c0der Feb 12 '20 at 06:55

1 Answers1

0

It seems strange to want to do this. It's certainly simpler with depth-first search (DFS), which always either follows an edge or backtracks along that edge. In contrast, breadth-first search (BFS) generally does not visit (or backtrack to) a node adjacent to the previous one visited.

Specifically, this part of your question is wrong, and reveals a misconception:

Since there is no edge between b & c, we must go back through a (so we must traverse the edge b -> a).

BFS will never traverse the edge back from b to a in your example. It finishes visiting b, then polls c from the queue and visits c immediately, without "travelling" there via a.

For an analogy, it makes sense to think of DFS as tracing out a path; if you are in a maze, you could use breadcrumbs to mark places you've "visited", and therefore solve the maze by DFS. In contrast, a human cannot solve a maze by BFS because humans cannot have a queue of places they know how to get to, and "teleport" to the next place in the queue. BFS does not meaningfully trace out a path that you could follow by travelling along edges in the graph.

That said, if you really wanted to, you can construct a path visiting the nodes of the graph, such that each node is visited for the first time in the same order as BFS. The simplest way to do this would be to do a BFS to build a list of the nodes in "BFS order", while also building the "BFS tree". Then for each node in BFS order, you can get to it from the previous node going via their lowest common ancestor in the BFS tree. This path only goes via nodes that have already been visited earlier in BFS order.

kaya3
  • 47,440
  • 4
  • 68
  • 97
  • It was actually part of a project, specifically the traveling salesman problem, where we were tasked with finding a continuous path through the graph that visits all the cities using various search methods such as BFS, DFS, UCS, A*, etc... I did eventually figure out how to do this, and it needed to be done in state space instead of graph space. – 24n8 Feb 11 '20 at 15:05