Why is Hamiltonian graph?

junissen9

Junissen

Posted on November 23, 2024

Why is Hamiltonian graph?
    Graph();

    bool data_input(const std::string file_name); 

    void create_A(); 
    bool hamilton(int curr);

    void data_output(const std::string file_name); 
    void no_way_answer(const std::string file_name); 
    void error_output(const std::string file_name); 

    ~Graph();
Enter fullscreen mode Exit fullscreen mode

Above is an image of a set of the classic Hamiltonian path class. This means that we will be able to understand how it is structured and what functions it performs. Let's go!

#include "Graph.h" - don't forget to connect the declared class to the source (.cpp).

bool Graph::data_input(const string file_name) { 

    int tek;
    ifstream in_file;
    in_file.open(file_name);

    if (in_file) { 
        if (in_file >> n && n>0) {
            while (!in_file.eof()) {
                if(in_file >> tek && tek>0)
                Vert.push_back(tek);
                else return false;
            }
        }
        else return false;
    }
    else return false;
    in_file.close();

    return true;
};
Enter fullscreen mode Exit fullscreen mode

Working with data is easy when you have the right libraries and know how to use them. It's easier to practice on files, because the values ​​are automatically tracked.

  • Initialize the vertices to zeros: for (int i = 0; i < n; i++) Visited.push_back(false);

  • In the graph we need to find a path where we pass the vertex only once. See the algorithm below

bool Graph::hamilton(int curr)
{
    Path.push_back(curr);

    if (Path.size() == n)
        return true;

    Visited[curr] = true;

    for (int nxt = 0; nxt < n; ++nxt) {
        if (A[curr][nxt] == 1 && !Visited[nxt])
            if (hamilton(nxt)) return true;
    }
    Visited[curr] = false;
    Path.pop_back();

    return false;
};
Enter fullscreen mode Exit fullscreen mode
  • The algorithm looks simple, but for correct verification we will output everything to a file, including unsuccessful attempts (to track inaccuracies in the code)
void Graph::error_output(const string file_name) { 

    ofstream errorFile;
    errorFile.open(file_name);

    errorFile << "Error";

    errorFile.close();
}
Enter fullscreen mode Exit fullscreen mode

In data science, this plays a role in storing and optimally accounting for data. Because the Hamiltonian graph contains one cycle and helps in searching for data in a fast way.

πŸ’– πŸ’ͺ πŸ™… 🚩
junissen9
Junissen

Posted on November 23, 2024

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

Why is Hamiltonian graph?
database Why is Hamiltonian graph?

November 23, 2024