Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times.
check that G is bipartite.
check G has one simple cycle.
find number of connected component G
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?
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?
