Cycles in an Undirected Graph

algorithm graph graph-theory
Eran Kampf picture Eran Kampf · Feb 8, 2009 · Viewed 105.9k times · Source

Given an undirected graph G=(V, E) with n vertices (|V| = n), how do you find if it contains a cycle in O(n)?

Answer

Rafał Dowgird picture Rafał Dowgird · Feb 8, 2009

I think that depth first search solves it. If an unexplored edge leads to a node visited before, then the graph contains a cycle. This condition also makes it O(n), since you can explore maximum n edges without setting it to true or being left with no unexplored edges.

Related questions

Difference between hamiltonian path and euler path

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!

Read More
How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?

Let G be an unweighted directed graph containing cycles. I'm looking for an algorithm which finds/creates all acyclic graphs G', composed of all vertices in G and a subset of edges of G, just small enough to make G' …

Read More
Names of Graph Traversal Algorithms

What I'm looking for is a comprehensive list of graph traversal algorithms, with brief descriptions of their purpose, as a jump off point for researching them. So far I'm aware of: Dijkstra's - single-source shortest path Kruskal's - finds a …

Read More