logo CodeStepByStep logo

findHamiltonPath

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

Write a function named findHamiltonPath that accepts a reference to a BasicGraph as a parameter and returns a Vector of vertex pointers representing a Hamilton path through the vertices of that graph. A Hamilton path is a path that touches every vertex of the graph exactly once, without repeating any vertices or edges. For example, in Graph 1 below, one possible Hamilton path would be {B, A, D, E, C, F}; another would be {B, A, D, F, E, C}. If the graph passed contains more than one Hamilton path, your function should return the one that comes earliest in alphabetical order.

Not every graph has a Hamilton path; for example, Graph 2 below does not contain any Hamilton paths. If the graph does not contain any Hamilton paths, return an empty vector.

Graph 1:
+----- B ---> C -----+
|      |      ^      |
|      |      |      |
|      |      V      V
|      |      E <--- F
|      |      ^      ^
|      |      |      |
V      V      |      |
A ---> D -----+      |
       |             |
       +-------------+
Graph 2:
       B <--> C <----+
       |      |      |
       |      |      |
       |      V      V
       |      E      F
       |      ^      ^
       |      |      |
       V      |      |
A ---> D -----+      |
       |             |
       +-------------+

Constraints: You may assume that the graph's state is valid, and that contains no self-edges (e.g. from V1 to V1). 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.