Re: cycle detection in undirected graph

From: Jim Nastos (nastos_at_cs.ualberta.ca)
Date: 04/14/04 

Date: Wed, 14 Apr 2004 02:54:18 -0600

On 13 Apr 2004, venkat wrote:

> Can someone refer me to an efficient algorithm for detecting cycles
> in an undirected graph.

  Test if the graph is a tree. If it is not a tree, then it has a cycle.
Maybe you want to be more specific?
J

Relevant Pages

  • weighted tree generation
    ... For a given undirected graph GI would like to generate all ... change to a given tree. ... is there any standard method to assign weights to an ... algorithm will yield a given tree? ...
    (comp.theory)
  • help on graph algorithms - constructing a tree with a mixed criterion
    ... undirected graph. ... to construct a tree T which minimizes the cost with the format ... minimum spanning tree (MST) in graph G, ... As constructing MST and SPT both are in complexity P, ...
    (sci.math)
  • help on constructing a tree with a mixed criterion
    ... undirected graph. ... to construct a tree T which minimizes the cost with the format ... minimum spanning tree (MST) in graph G, ... As constructing MST and SPT both are in complexity P, ...
    (comp.theory)
  • weighted tree generation
    ... For a given undirected graph GI would like to generate all possible ... rooted trees. ... dijkstra) will yield a given tree? ... but can it be proven that it will always yield the given tree?) ...
    (sci.math.research)
  • Re: Another set with cardinality |Z|
    ... In comp.theory Kent Paul Dolan wrote: ... undirected graph with one fewer edges ... What a complicated definition. ... a tree is a strongly connected acyclic graph. ...
    (sci.math)
Loading