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.
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)