Re: How to judge if the graph is cyclic when add a new edge?

cstnt wrote:

How to judge if the graph is cyclic when add a new edge? How to do it quickly.

I will assume that the graph is undirected, otherwise the following won't work:

Give each connected group in the graph a distinct name, and label each node with the name of its group. When you add an edge then:
(a) If the edge is between two nodes with the same label, you are creating a cycle or cycles.
(b) If the edge is between two nodes with different labels, you are not creating a cycle, and you should re-label the nodes of one group to match the other group, as the two groups have merged.

I think that if you create a tree from a cloud of n disconnected nodes by add random non-cycle-inducing links, and you always re-name the smaller group in case (b), you will need O(n log n) individual re-labelling operations, though I am not sure how to prove it.

--
Simon Richard Clarkstone:
s.r.cl?rkst?n?@durham.ac.uk/s?m?n.cl?rkst?n?@hotmail.com
Scheme guy says: (> Scheme Haskell)
Haskell guy says: (> Scheme) Haskell
.

Relevant Pages

  • counting cycles
    ... :> its meaning is perfectly clear and non-controversial. ... If you try to graph it, ... Except that this cycle IS infinite. ... It's hard to know what you even COULD mean by an infinite cycle. ...
    (sci.logic)
  • Re: Finding Euler paths..
    ... > Euler path in a graph taking input as the edges. ... check that there can exist a euler path in the graph. ... [For a Euler cycle, find any old cycle to start ... So, our original path shares no vertices with the first cycle, so we ...
    (comp.programming)
  • Re: searching an example for the road coloring conjecture, degree 2
    ... >>connected directed graph with outdegree 2 admits an edge coloring such ... >>the smallest coprime cycle set has at least 3 elements. ...
    (sci.math.research)
  • Re: Shortest path algorithm in digraph with multiple goals?
    ... > lot of red edges (thus your solution will produce a huge graph). ... graph traversal algorithms. ... arcs" can occur in any cycle. ... which there have been 'k' previous traversals of the "counted" arcs. ...
    (comp.programming)
  • Re: Shortest path algorithm in digraph with multiple goals?
    ... > lot of red edges (thus your solution will produce a huge graph). ... graph traversal algorithms. ... arcs" can occur in any cycle. ... which there have been 'k' previous traversals of the "counted" arcs. ...
    (comp.theory)