DFS - Checking if a graph is bipartite

Question

I wonder what will be the complexity of this algorithm of mine and why, used to check whether a graph (given in the form of neighbors list) is bipartite or not using DFS.

The algorithm works as following:

We will use edges classification, and look for back edges.

If we found one, it means there is a circle in the graph.

We will now check whether the cycle is odd cycle or not, using the the pi attribute added to each vertex, counting the number of edges participating in the cycle.

If the cycle is an odd one, return false. Else, continue the process.

Initially I thought the complexity will be O(|V| + |E|) as |V| stands for the number of vertices in the graph, and |E| stands for the number of edges in the graph, but I am afraid it might take O(|V| + |E|^2), and I wonder which option is correct and why (it may not be any of the above as well). Amortized or expected run times may also be different, and I wonder how can I check them as well. Please help me figure!

pseudo code

DFS(G=(V,E))
// π[u] – Parent of u in the DFS tree 
1 for each vertex u ∈ V {
2 color[u] ← WHITE
3 π[u]← NULL
4 time ← 0}
5 for each vertex u ∈ V {
6 if color[u] = WHITE
7 DFS-VISIT(u)}

and for the DFS-Visit:

DFS-Visit(u)
// white vertex u has just been discovered
1 color[u] ← GRAY
2 time ← time+1
3 d[u] ← time
4 for each v ∈ Adj[u] { // going over all edges {u, v}
5 if color[v] = WHITE {
6 π[v] ← u
7 DFS-VISIT(v) }
8 else if color[v] = GRAY // there is a cycle in the graph 
9 CheckIfOddCycle (u, v); 
10 color[u] ← BLACK
// change the color of vertex u to black as we finished going over it
11 f[u] ← time ← time+1 

and as for deciding what type of cycle is it:

CheckIfOddCycle(u, v)
1 int count  ← 1; 
2 vertex p = u; 
3 while (p! = v) {
4 p ← π[p]  
5 count++ }
6 if count is an odd number {
7 S.O.P (“The graph is not bipartite!”); 
8 stop the search, as the result is now concluded!

Thanks!

Answer 1

While your algorithm is visiting a node $v$, if it detects a back edge $(v,u)$ then it backtracks until it reaches $u$, using the parent information stored in pi, counts the number of edges, and then decides if it is bipartite or not. In this case your edges and nodes are visited at most two times (once when you move forward and once when you backtrack) which is still linear, i.e. is $O(V + E)$.

As for average and amortized case analysis I have never done such a thorough analysis of dfs but my guess is both are $O(V+E)$.