0
$\begingroup$

How do time and space complexity compare for unidirectional bfs and bi-directional bfs in worst and practical case such as a social network?

$\endgroup$
  • $\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$ – Yuval Filmus Jan 22 '17 at 8:59
  • $\begingroup$ This is what I think, correct me if I am wrong. For Worst Case: Time complexity and space complexity will be the same for both. O(|E|+|V|). In a practical scenario like a social network, shortest path between two nodes: bidirectional will get the result faster and use less space, but I can't deduct the exact time and space complexities. $\endgroup$ – Abhay P Jan 22 '17 at 23:03
  • $\begingroup$ I'd like to try to provide an answer to your question, but other than rather low diameters (maximum shortest distance between any pair of vertices) and maybe large branching factors, what do you think that better characterizes a social network? $\endgroup$ – Carlos Linares López Jan 23 '17 at 21:22
  • $\begingroup$ that's all I can think of $\endgroup$ – Abhay P Jan 23 '17 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.