Data Structures and Algorithms B
  • Introduction
  • Stable Marrage
  • Huffman Codes
    • ABL
    • Implementation
  • Graph Algorithms
    • Connect Component
    • Bipartiteness
    • Strongly Connected Components
      • Implementation
    • Topological Sort
      • Implementation 1
      • Implementation 2
    • Dijkstra’s Shortest Path
    • Minimum Spanning Tree
      • Prims
        • Implementation 1
      • Kruskels
        • Implementation 1
      • Traveling Salesman Problem
    • k-Clustering
    • Dynamic Programming with Trees
      • Implementation 1
      • Implementation 2
    • Disjoint Sets
      • Implementation
    • Eularian Cycle
      • Implementation
    • Hamiltonian Path
      • Implementation
  • Divide and Conquer
    • Merge Sort
    • Integer Multiplication
    • Closest Pair
    • Master Method
  • Dynamic Programming
    • Interval Scheduling
    • Knapsack Problem
  • Network Flow
    • Maximum Network Flow
    • Improvements
    • Image Segmentation
  • String Algorithms
    • Z Algorithm
    • Boyer-Moore
    • Knuth-Morris-Pratt
    • Suffix Trees
      • Naive Implementation
      • Ukkonens Algorithm
        • Implementation
      • Applications
        • Longest Common Substring
        • Longest Palindromic Substring
        • Longest Repeated Substring
  • Randomized Algorithms
    • Bloom Filters
      • Implementation
Powered by GitBook
On this page

Was this helpful?

  1. Graph Algorithms

Hamiltonian Path

PreviousImplementationNextImplementation

Last updated 5 years ago

Was this helpful?

A Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once. If a Hamiltonian path exists whose endpoints are adjacent, then the resulting graph cycle is called a Hamiltonian cycle (or Hamiltonian cycle).

To give a better understanding of the problem consider the following 3 graphs.

While figure 1 does not contain an Hamiltonian Path, figure 2 contains 2 Hamiltonian paths as depicted in figures 3 and 4.

In general, the problem of finding any Hamiltonian Path in a graph is an NP-complete problem, but there are different levels of efficiency we can still go about solving this problem.

Approach 1: Permutations

  1. Generate all permutation of vertices in the graph.

  2. For each permutation, confirm whether or not it is a valid path. A path is valid if from vertex A_i to A_i+1, A_i has an edge to A_i+1 and there are a total of i=N vertices in the path.

The time complexity for this algorithm is O(N*N!). N! to generate every permutation, and an additional N to check each one.

Approach 2: Back Tracking [implemented]

This algorithm is technically still brute force, but it is a smarter way of approaching things. Essentially, what we do is find all all paths in a graph from a starting vertex. If a path is valid, then we've found a Hamiltonian path. As a short example, look at the image below.

For vertex 0, dfs out and create a tree that represents all the possible paths from vertex 0.