logo CodeStepByStep logo


Language/Type: C++ Graph collections
Related Links:
Author: Marty Stepp (on 2016/06/16)

Write a function named findEulerPath that accepts as a parameter a reference to a BasicGraph, and tries to find an Euler path in the graph, returning it as a Vector of Vertex pointers. An Euler path is a valid path that uses every edge in the graph exactly once. (A real-world example where you might want an Euler path: A snow plow wants to remove the snow from all the roads in the neighborhood without unnecessarily driving over the same road twice.)

For example, in Graph 1 below, you can form an Euler path by starting at vertex C and forming the following path: {C, A, B, C, E, D, B}. If you follow the preceding path you'll find that it uses every single edge from the graph. It revisits some vertexes more than once, which is fine; it is only the edges we may not reuse. In Graph 2 below at right, you can form an Euler path by starting at vertex F and forming the following path: {F, C, D, A, C, E, A, B, D, F}. This second Euler path happens to be a cycle (also called an Euler circuit), which is fine, but the path you find does not need to be a cycle as long as it is a valid path that uses all the edges exactly once.

Graph 1:
graph 1
Graph 1:
graph 2

If the graph does not contain an Euler path, or if the graph does not contain any vertexes or edges, your function should return an empty vector. For example, in Graph 1 above, if the edge D-E were absent, then the graph would not contain an Euler path.

Implementation hint: This is a classic problem that does not have any known clever algorithm that will work in all cases. You need to perform an exhaustive search and explore all possible paths in the graph to see if you can find an Euler path through brute force. Although you must search exhaustively, you should still write code that is efficient. Do not explore large numbers of the same paths and options multiple times, nor continue exploring paths that are certain to be dead-ends.

Constraints: You may assume that the graph's state is valid, and that it is undirected and unweighted, and that contains no self-edges (e.g. from V1 to V1). You may also assume that there is at most one edge from any vertex V1 to any V2. You may define private helper functions if so desired, and you may construct auxiliary collections as needed to solve this problem. You should not modify the contents of the graph such as by adding or removing vertexes or edges from the graph, though you may modify the state variables inside individual vertexes/edges such as visited, cost, etc.

Type your solution here:

This is a function problem. Write a C++ function as described. Do not write a complete program; just the function(s) above.

You must log in before you can solve this problem.

Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.