1
$\begingroup$

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:

  1. Graph $G=(V,E)$ with adjacency lists $(v,A(v))$
  2. 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.

  1. If a cycle exists, the algorithm will return true.
  2. If the algorithm returns true, then a cycle exists.

Proofs.

  1. 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.
  2. 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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ How about the following idea: Each time we visit a node we could set µ to 0 and add the visited node to a new set $V'$. At the end of the while loop we could check for emptiness of $V\setminus V'=\emptyset$. If this is true we can return false because there are no more components left; otherwise we pick an arbitrary $v'\in V\setminus V'$ and then repeat everything with $U=\{v'\}$. Do you think that would solve my problem with the components? $\endgroup$ Dec 8, 2012 at 16:05
  • $\begingroup$ Furthermore to reduce redundancy as $\mu$ and $V'$ would hold visited nodes, an option would be to use $\mu$ for a topsort. $\endgroup$ Dec 8, 2012 at 16:10
  • $\begingroup$ Please have a look at my updated question. Is this the kind of proof for correctness you recommended me? $\endgroup$ Dec 8, 2012 at 16:52
  • $\begingroup$ @ChristianIvicevic Regarding correctnes, yes. There is a minor issue: you do not pick a cycle $C$ in the first part, in fact DFS could branch in some other way and reach node $v_n$ from a different neighbour than $v_{n-1}$. $\endgroup$
    – dtldarek
    Dec 8, 2012 at 17:07
  • $\begingroup$ @ChristianIvicevic Regarding algorithm, that should work, I see that you noticed the redundancy. However, with the outer loop in place, you should revise your complexity argument. Ah, and those about cycles are not assumptions ;-) $\endgroup$
    – dtldarek
    Dec 8, 2012 at 17:13
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .