I have an (undirected) graph isomorphic to $C_n$ with unordered edges/vertices in some data structure (in particular, a list of tuples representing the edges), etc. I was wondering what is the fastest algorithm to compute a path which begins and ends at some given node in the cycle, given this set of nodes? The simplest thing seems to be to just use DFS, but that seems like overkill for what I'm sure is a relatively simple algorithm.

  • $\begingroup$ @Juho Yeah, clarified. Anyways, I want to find a path in my graph which is isomorphic to a cycle graph, though the enumeration of nodes in the graph I currently have is essentially random. I was wondering if there was a fast algorithm for computing an ordered list of edges which signifies a path through the cycle which starts and ends at an arbitrary node. $\endgroup$ Aug 1 '16 at 17:44
  • 1
    $\begingroup$ Pick a vertex and follow the edges until you get back to where you started. The seems so obvious that I feel I must have misunderstood your question. $\endgroup$ Aug 1 '16 at 19:29
  • $\begingroup$ @DavidRicherby That would work quite nicely were it not for the data structure being used to store the edges in this particular case. Nominally, yes, I could just construct a dictionary containing the neighbors of the given graph and follow them all the way around, but I was wondering if there was a nicer way that didn't involve additional space constraints that was sub $n^2$. $\endgroup$ Aug 1 '16 at 19:30
  • $\begingroup$ So how are the edges stored? Adjacency matrix? Oracle? Something else? If it's going to take you linear time to find each edge, you're not going to get anything better than a quadratic algorithm. $\endgroup$ Aug 1 '16 at 19:35
  • $\begingroup$ @DavidRicherby That's why I was wondering. If we had only a list of edges and a list of vertices (not wholly helpful), and we aren't allowed to use auxiliary data structures of O(n) space, is there a faster way of constructing such a path? The general answer is obvious, but apart from that, the constraints make it much harder. $\endgroup$ Aug 1 '16 at 21:08

I understand your question this way:

There is given a graph with nodes and edges. There might or might not be one or more circles in that graph. And there is given a certain start-node within the set of nodes.

You ask, if this start-node is part of at least one circle, and you ask, which nodes (of which one is the given start-node) and edges form the smallest circle.

If this was your question, then I have an answer:

DFS is not the best choice. BFS is. BFS = Breadth-first-search. There is an wikipedia-article that describes this algorithm.

The idea of this algorithm is to begin to test all nodes at the end of the edges that are directly connected with the given node. This gives you a list of all direct neighboring nodes of the start-node. I call them the level-1-neighbors.

In the next step you repeat this search for each level-1-neighbors, but now you ignore all edges that directly lead back to where you did come from. The result are the level-2-neighbors. And then you repeat this for the level-n-neighbors to get the level-(n+1)-neighbors.

This transforms your graph into a new graph, which is a tree. The start-node is the root of this tree, the level-1-neighbors are the roots children, level2-neighbors are children of those children.

If your original graph contains a circle, then nodes will appear twice (or more often) in the resulting tree, because there are (at least) two different ways, that you can move through the circle to reach nodes in the circle (clockwise and counter-clockwise).

So, if a certain node appears a second time in the graph, then you have found a circle. The circle is the path starting at one representation of that node, going up till you reach the first common ancestor of both representations and then go down to the second representation.

If the common ancestor is the root node, you found the circle with the least number of nodes that goes through the given node. If the common ancestor is not the root, then you just have found a circle, that is connected with the given node by a side-arm. In this case you must go on searching.

There is an easier (but longer) algorithm for the case that there are directed edges: Use BFS until you hit the start-node for a second time. Then the path from the root to the second representation of the start-node is the shortest circle. This is simpler (you need not compare every new node with any node you already passed, but only with the root), but probably needs more resources because the tree you have to build will be deeper.

In both versions of the algorithm you must pay attention not to get lost in loops (again and again walking through circles that are not the needed circle)

  • 4
    $\begingroup$ The graph itself is just a single cycle $C_n$, for some $n \geq 3$. $\endgroup$
    – Juho
    Aug 1 '16 at 19:23
  • $\begingroup$ Perhaps the current edit makes it a little more clear? In the case where the graph is isomorphic to $C_n$, DFS or BFS will both have exactly the same running time complexity. I feel I wasn't being very clear in my question, but I was looking for a different algorithm. (EDIT: As @Juho just clarified) $\endgroup$ Aug 1 '16 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.