Question

List key programming considerations when searching for an element in a graph G. Consider unconnected graphs. Consider multiple occurrences of a datum; cycles in a graph. this is a theoretical question.

Answer 1

In terms of programming, we can search an element in a graph G using two approaches, i.e, Breadth First Search (BFS) and Depth First Search (DFS). Where in BFS, all the nodes of the graphs are visited by selecting one node and then visiting its adjacent nodes one by one, DFS selects a node and when an adjacent node is found, it moves to that node and traverses it in the same manner. The time complexity of both these algorithm remains same.

For unconnected graphs, we can use both DFS and BFS search algorithm to get the answer but programming approach is to use Breadth First Search (BFS) instead of DFS. BFS can also be used to find connected components of the graph.

For cyclic graphs, programming approach says that there is a cycle in the graph only if there is a back edge present. So for detecting cycles in a graph and to search element in the cyclic graph, Depth First Search is recommended.

Now for multiple occurrences of datum, you can use both BFS and DFS but programming approach advices that to find the nearest neighbor or the shortest path, using BFS would be better but in case if searching element is near to leaf nodes, DFS would be better.

If you have any doubt regarding the answer then let me know in comment. If it helps, kindly give an upVote to this answer.