Pathfinding with cycles in a graph (Use each edge once)

Question

I would like to search for some paths in a graph. Graph has cycles, they happen quite often.

Bring back the old riddle about drawing house without putting up pen and drawing same edge 2 times.

  ^
 / \
/ _ \
|\ /|
| x |
|/_\|

It has 5 vertices and 8 edges. Let us say that I want to check if it's possible to draw such a graph without "putting up the pen", with given starting vertex. Notice, that i can (and probably need) to process same vertex with different map state (are the edges around used?) few times. Do I have to make a copy of the whole edge-usage array for each node while running BFS/DFS? Is there any simple method to do that?

Answer 1

For DFS, you just need to have visited flag on the edge. You don't need to copy it, just reset it after the call.

Pseudo-code:

for each node
  for each edge
    edge.visited = false
  dfs(node)

dfs(node)
  // do something with node?
  // perhaps check numberOfEdges == visited.size() to see if we're done
  for each edge in node
    if (!edge.visited)
      edge.visited = true
      dfs(edge.other(node))
      edge.visited = false

Answer 2

Let us say that I want to check if it's possible to draw such a graph without "putting up the pen", with given starting vertex.

If graph isn't connected, drawing is impossible. Otherwise, if graph doesn't have vertices of odd degree, it is possible, no matter what vertex you start from. If it has two such vertices, it is possible if and only if given vertex has odd degree. If it has more than two vertices of odd degree, it is impossible.

I would like to search for some paths in a graph.

If drawing is possible (see above), any path will do as long as remaining edges are connected.