1
$\begingroup$

I am trying to understand the approach for this problem:

"If all streets are one way, there is still a legal way to drive from one intersection to another"

The question is to prove that it can be done in linear time. I am not looking for direct answers but the approach to this problem.

How can I think about this problem in terms of graph theory? AFAI understand, this will result in a DAG. But then should I choose BFS or DFS and why to prove it? (both are liner time algos)

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I will answer your comment regarding homework here: Everything is fine, there is no need to tag your question in any special way. See also our policy. $\endgroup$
    – Raphael ♦
    Jul 10, 2012 at 19:05
  • 1
    $\begingroup$ Linear time in what? For example, BFS and DFS are not linear time in the number of nodes. $\endgroup$
    – Raphael ♦
    Jul 10, 2012 at 19:06
  • 1
    $\begingroup$ in graph traversal, both are liner time algos right? $O(|V| + |E|)$? $\endgroup$
    – zengr
    Jul 10, 2012 at 19:54
  • 2
    $\begingroup$ @Raphael They are if the graph is planar, which is probably implied here. $\endgroup$
    – Gilles 'SO- stop being evil'
    Jul 10, 2012 at 20:00
  • 5
    $\begingroup$ @Raphael: Yes, but it's standard to call $O(n+m)$ "linear time" for graph algorithms, even if $m=\Theta(n^2)$, since the complexity of the input is $n+m$. $\endgroup$
    – JeffE
    Jul 11, 2012 at 19:54

2 Answers 2

Reset to default
1
$\begingroup$

First, it definitely won't result in a DAG, just a digraph. You need to get from A to B and B to A in order to satisfy your condition for nodes A and B, but that itself is a cycle.

Lots of time BFS and DFS are equivalent in relation to a problem, so it doesn't matter which one you choose. Here, the real trick is not choosing between DFS and BFS, but dealing with the fact that the graph is directed.

If you don't want a direct answer, here's the strategy I would use: first find a representation for the streets in terms of a digraph. What corresponds to edges? What corresponds to nodes?

Then, you need to find a graph algorithm that will work for this problem. What information do BFS and DFS give you about the graph? How can they be adapted to a directed graph?

To give you a little hint, I'd recommend you Google Eulerian chains.

Improve this answer
$\endgroup$
0
0
$\begingroup$

As a hint, think about the intersections as nodes and the streets as directed edges connecting intersections. Then, try thinking about the following: find all clusters of nodes that are mutually reachable from one another (such nodes are said to be strongly-connected.

Hope this helps!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.