0
$\begingroup$

following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times.

  1. check that G is bipartite.

  2. check G has one simple cycle.

  3. find number of connected component G

  4. with given two vertex u, v, find a path between u and v with minimum edges

anyone can describe, how the authors of this note claim that all of them can be checked with DFS and in O(|V|+|E|) times?

$\endgroup$

closed as too broad by Juho, David Richerby, Luke Mathieson, D.W., Carlos Linares López Feb 28 '15 at 23:20

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Whom are the authors? I think that you can split you're question in a least four. $\endgroup$ – jonaprieto Feb 28 '15 at 8:08
1
$\begingroup$

The time complexity of DFS is O(|V|+|E|), therefore if one can solve these problems with DFS, it follows their time complexity is also O(|V|+|E|), remains only to proof that complexity, for which I should recommend a reading on Cormen.

1) To check if G is bipartite, tag each visited vertex with a color. Initially, all vertex are, say, WHITE. When you start the DFS with a vertex, tag it with RED. Everytime a RED vertex visits a WHITE vertex, tag that WHITE vertex with BLUE, and when a BLUE vertex visits a WHITE vertex, tag it with RED. If a vertex visits another vertex of the same color, then that graph is not bipartite. This is because a graph is bipartite if and only if it is 2-colorable, that is, its chromatic number is 2. In short, every pair of adjacent vertices of that graph can be colored with 2 different colors, and only 2 colors are needed to color the entire graph.

2) Here, a similar approach, but with only WHITE and BLACK. All vertices are initially WHITE. Start the DFS in a vertex and tag it with BLACK. Everytime a BLACK vertex visits a WHITE vertex, tag it with BLACK. If a BLACK vertex visits another BLACK vertex, then there is a cycle in the graph.

3) Start with a counter=1 and start the DFS. If at any point the vertices stack is empty, that is, you have backtracked all the reacheble vertices from the origin and need to access the vertex list once again, then increment the counter variable. That variable indicates the number of connected components of your graph.

4) It is NOT possible to solve this problem with DFS. It is probably a trick. Why can't DFS be used to find shortest paths in unweighted graphs?

$\endgroup$

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