0 votes 0 votes DFS and BFS are equal in expressive power??? I(Independent on performances)?? Subbu. asked Jan 27, 2022 Subbu. 444 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply palashbehra5 commented Jan 27, 2022 i edited by palashbehra5 Jan 27, 2022 reply Follow Share Both of them run in linear time with adjacency list graph representation and quadratic in the case of adjacency matrix representation.Both of them require workarounds to traverse/search disconnected graphs.On trees, BFS performs level order traversing whereas dfs will perform preorder traversing (Depending on the order of visiting children), now stack and queues are auxiliary data structures used in searches, and queues can be realized using 2 stacks and vice versa. (But then they will become 2 different searches)Both can take more/less time to find the same node. (Same goes for solving mazes) However, BFS shall guarantee the shortest paths on unweighted edges.https://stackoverflow.com/questions/36479640/time-space-complexity-of-depth-first-searchNow, going by the definition https://en.wikipedia.org/wiki/Expressive_power_%28computer_science%29I guess order of visiting nodes is different and so is their expressive powers? Let me know what you think.Note : It is defined for languages, but i think i get what you are asking so answered accordingly. 2 votes 2 votes Subbu. commented Jan 27, 2022 reply Follow Share Here expressive power means..is there any problem which can solvable by Dfs and not by Bfs....??? 0 votes 0 votes palashbehra5 commented Jan 27, 2022 reply Follow Share Not any that I know of, Typical problems such as searching, topological sorting, checking bipartiteness, finding connected components, cycle-detecting, etc. can be solved by both traversals. The only difference I could think of right now is that BFS finds shortest paths on unweighted edges, whereas DFS cant. Also, they have different edges in search trees. ~ CLRS. 1 votes 1 votes raja11sep commented Jan 27, 2022 reply Follow Share There exist some problems that can be solved by BFS but not by DFS. ex: Shortest path on the unweighted graph. 0 votes 0 votes raja11sep commented Jan 27, 2022 reply Follow Share Can anyone give one example of a problem that can be solved by DFS but not by BFS? 0 votes 0 votes LRU commented Jan 27, 2022 reply Follow Share DFS has a powerful role in making chess engines and used extensively in this domain. The application of BFS in this is almost non-existent. Image Courtesy – Cyberdaemon (Peru) This is one basic Sicilian Defence flow chart played by Black in Chess. 2 votes 2 votes raja11sep commented Jan 27, 2022 reply Follow Share So what is the conclusion? 0 votes 0 votes LRU commented Jan 27, 2022 reply Follow Share It totally depends on what problem we are solving to use either BFS or DFS and both are independent as at the end of the day, we have to make our algorithm efficient. 2 votes 2 votes Please log in or register to add a comment.