Algorithm to check whether a graph has no cycles 
Let $G=(V,E)$ be an undirected graph. Design an algorithm which decides whether the graph contains a cycle and proove its correctness and determine its complexity in terms of $\mathcal{O}$-notation. Your algorithm has to be based on DFS/BFS. (Just one algorithm from our lecture used to mark visited nodes smiliar to my solution)


Initial attempt which was too vague
My initial attempt was to use an amended version of the DFS. Without loss of generality I assume having a graph which is connected, otherwise we can apply this algorithm to each component which yields the same result. Furthermore I use a function $\mu:V\to\mathbb N_0$ which indicates whether a node $v\in V$ was already visited ($\mu(v)=0$) or not ($\mu(v)=\infty$).

Input:
  
  
*
  
*Graph $G=(V,E)$ with adjacency lists $(v,A(v))$
  
*A node $s\in V$
  
  
  Output: Boolean value, indicating whether the graph contains a cycle.

BEGIN
    FOR EACH v IN V DO
        IF v = s THEN µ(v) <- 0
                 ELSE µ(v) <- Infinity
    END FOR
    U <- {s} // nodes we still have to apply the DFS on
    WHILE |U| > 0 DO
        FOR EACH u IN U DO // select based on LIFO for DFS, with FIFO we would get BFS
            FOR EACH v IN A(u) DO
                IF µ(v) = Infinity THEN µ(v) <- 0
                                   ELSE RETURN TRUE
                U <- U ∪ {v}
            END FOR
        END FOR
        U <- U \ {u}
    END WHILE
    RETURN FALSE
END

As we use the DFS it is obvious that all nodes of our given undirected graph are reachable, if not the graph would not be connected and we would have to apply the algorithm to all components. While the DFS just ignores already reached nodes which would form a cycle we just added a piece of instruction to abort the computation and therefore are finished. The complexity results from the DFS itself. During our initialisation we need $|V|$ operations. Our iteration always matches two nodes with a worst-case number of comparisons being $2|E|$, hence the complexity being $\mathcal O(|V|+|E|)$.

Second attempt
BEGIN
    FOR EACH v IN V DO
        IF v = s THEN µ(v) <- 0
                 ELSE µ(v) <- Infinity
    END FOR
    U <- {s} // nodes we still have to apply the DFS on
    W <- {} // Keep track of visited nodes to find all components
    WHILE W != V DO
        IF U = {} AND W != V THEN
            U <- {v} // where v is an arbitrary node from V \ W
        END IF
        WHILE U != {} DO
            FOR EACH u IN U DO // select based on LIFO for DFS, with FIFO we would get BFS
                FOR EACH v IN A(u) DO
                    IF µ(v) = Infinity THEN µ(v) <- 0
                                       ELSE RETURN TRUE
                    U <- U ∪ {v}
                    W <- W ∪ {v}
                END FOR
            END FOR
            U <- U \ {u}
        END WHILE
    END WHILE
    RETURN FALSE
END

Assumptions.


*

*If a cycle exists, the algorithm will return true.

*If the algorithm returns true, then a cycle exists.


Proofs.


*

*Without loss of generality, assume that the node $s\in V$ with which we start is part of a component which contains a cycle $C$. Our cycle $C=(v,v_1,\ldots,v_n,v)$ holds the node $v$ which can be reached from $s$ (proof from lecture, every node in one component of a undirected connected graph will be reached by DFS). Once the DFS selects $v$ will follow the path $(v,v_1,\ldots,v_{n-1})$ until it reaches $v_{n-1}$. We know that $\mu(v_n)=0$ because the inner for-loop has done this when the DFS has selected $v$ and obviously $v_n\in A(v)$. However from $v_n\in A(v_{n-1})$ the edge $\{v_{n-1},v_n\}$ closes the cycle and therefore the DFS yields true.

*Assuming the algorithm yields true while following a path $(u,v_1,\ldots,v_n,v)$ we know that $(u,v_1,\ldots,v_n)$ cannot be a cycle. So our last node $v\in A(v_n)$ has to be the trigger which means, that $\mu(v)=0$ implying that we already reached this node once and do have a cycle.



Any comments on whether this is wrong or not are appreciated. Furthermore I am looking to get a better explanation for correctness and complexity but I am not able to come up with something.
 A: The comment was too short.
Your correctness proof is hardly there. I also don't know what do you mean by 'comparisons' and where from you got $2|E|$. On the other hand, this is a correct algorithm given you have a connected graph. Your comment explains what to do in disconnected case, but then you could just apply it, after all, one searches for the connected components with DFS (and those two DFSes could be just one). Moreover, one can do initialization faster, the $|V|$ part of complexity should come from the fact that in the worst case you will have to visit (or at least take care in some way) all the vertices. Of course, if you have initialization done this way, you ought to mention it (as you did; besides this is not a big fault, usually you need to read the graph from some kind of input and this is where you can initialize your arrays/maps).
Finally, this is a fine attempt, you shouldn't be discouraged. There are some issues, but I would be glad if my students had enough patience and precision to work it out as you did.
As for suggestions for complexity, the best way is to express the number of operations in your algorithm depending on some global properties, like "my algorithm visits every vertex at most 42 times and every edge at most 78" or "for every edge it does at most $|V|^{567}$ operations" and so on.
As for suggestions for correctness, one usually splits the proof into two parts: "if cycle exists, then my algorithm will return true" (or "if my algorithm returns false then graph is a forest"), and "if my algorithm returns true, then cycle exists" (or "if cycle doesn't exists, my algorithm will return false"). This is not the fastest way, but it is very easy to do serious mistakes if you prove both implications at the same time.
I hope you will find my advice usefull.
A: Lemma: DFS returns true if and only if $G$ has a cycle
$\Rightarrow)$ DFS returns true then $G$ has a cycle.
Proof: Suppose that in the execution of the algorithm DFS the vertex $u$ is seen before the vertex $v$, the latter vertex has as neighbor to $u$. In other words, $u$ is visited and colored to black, after $n$ recursive calls the vertex $v$ (currently with white color) is visited. In line 8 (FOR EACH v IN A (u) DO) all the neighbors of $v$ are analyzed. Since $u$ is a predecessor of $v$, there is a path from $u$ to $v$ (Theorem 22.9 (White-path theorem) CLRS). Or the second path between $u$ and $v$ is the edge that connects $u$ to $v$. Therefore there are 2 paths between $u$ and $v$, that is, there is a cycle in $G$.
$\Leftarrow)$ $G$ has a cycle then DFS returns true
Proof: Let $C$ be a cycle in $G$, such that $u$, $v$, and $v'$ belong to $C$ and $u$ is a neighbor of $v$ and $v'$. Without loss of generality suppose that $u$ is viewed first during the execution of the DFS. Note the algorithm can choose to visit after $u$ to $v$ or $v'$. Suppose that $v'$ is visited after $u$.  When the DFS visits the vertex $v$, on line 8, all the neighbors of $v$ are analyzed. Note that $v$ is descendant of $u$. Since $u$ is predecessor and is also adjacent to $v$ the algorithm returns true.
