Menu
I am trying to find a path between two nodes in a graph, where the edges are unweighted.
I am using a Breadth First Search, which stops when it finds the target, in order to find the existence of a path, but I am not sure how to get the path itself.
I tried looking at the list of visited nodes, but this did not seem to help. I saw someone answer this question using prolog, but I am a C++ programmer.
I also looked at Dijkstras algorithm, but this seems like over kill, since a simple Breadth-first Search has got me almost the whole way.
How to get the path between 2 nodes using Breadth-First Search?
876
Create a graph using the given nodes and a queue for storing the nodes to iterate through breadth-first search. Push v1 to the queue and start Breadth-first search till the queue is not empty. Iterate through all the connected nodes from the current node. Update the parent of new nodes.
Approach: Either Breadth First Search (BFS) or Depth First Search (DFS) can be used to find path between two vertices. Take the first vertex as a source in BFS (or DFS), follow the standard BFS (or DFS). If the second vertex is found in our traversal, then return true else return false.
Breadth First Search (BFS) BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.
In your node struct, you add a variable called parentNode which is the parent of that node in the path. In the end, you can retrieve the path by traversing from the goal node backward.
175
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
