CODEWITHSUNDEEP
algorithm
Jason Ji
Jason Ji

Reputation: 11

algorithm design to find all nodes in graph

In a game, a set of nodes is connected via some set of one-way edges. At every node there is an object to pick up. Design an algorithm to find a path that you can follow to collect all objects, if this is possible. To make your task easier, you know that starting from any node, no matter what path you follow, you will never get back to the same node.

The question asks us to do something "if possible".Therefore, I'm thinking if the graph is direct and has no cycle to the node itself, it's possible to use BFS to traversal the entire graph. Because if the graph is Direct Acyclic Graph, which means that it is impossible to traverse the entire graph starting at one edge.

Upvotes: 1

Views: 712

Answers (2)

Nia
Nia

Reputation: 21

The best way to find the path that visits all nodes in a directed acyclic graph is topological sort because it orders the vertices such that for every directed edge ab from vertex a to b, a comes before b in the ordering. This is essential because in topological sort you start with the vertex that has no incoming edges which ensures that your path starts at the right vertex (beginning of the path) and then traverses the rest of the graph using DFS. Although BFS could traverse the graph, there is no way to know that BFS is starting at the beginnning of the path. Since you can not return to a node, if BFS starts at an edge tha has incoming edges it will never reach the parent to that node because then that would be a cycle and by never reaching the parent you will not find all nodes in the graph. Thus, it is important to start at a vertex with no incoming edges as topological sort describes

Upvotes: 1

smilingfish
smilingfish

Reputation: 7

This is similar to the Hamiltonian path problem. A Hamiltonian path is a path in an directed or undirected graph that visits each vertex exactly once. In your case, the vertex is now the node. If you can find a path that visits each node exactly once, it means you are trying to find the Hamiltonian path. I don't think you can use topological sort to solve your problem, you can google what topological sort exactly do. The Hamiltonian path problem is known as NP-complete, which means that it can not be solved in polynomial time by using any existing algorithm.

Upvotes: 0

Related Questions