Couldn't get the required correct output

Question

I'm trying to solve the Hamiltonial cycle and path problem using backtracking method whether a source vertex is given for the input graph. When all the vertex are visited in that input graph, then the path will be displayed. Using backtracking approach, I want to get all the hamiltonaial path or cycle for the input graph.

This is my code:

#include<stdio.h>
#include<conio.h>
#include<stdbool.h>
int m=0;
int ans[5];

void Hamilton(int G[5][5], int visited[5], int n, int f){
    if(m == 5-1){
        for(int i=0;i<f;i++)
            printf("%d ",ans[i]);
        printf("\n");
        return;
    }
    else{
        visited[n] = n;
        m++;
        for(int i=0;i<5;i++){
            if(G[n][i] == 1){
                if(visited[i] == -1){
                     n = i;
                     ans[f++] = i;
                     Hamilton(G, visited, n, f);
                }           
            }
        }
        visited[n] = -1;
        m--;
        return;
    }
}

void main(){
    int G[5][5] = {
        {0,1,1,0,0},
        {1,0,0,1,1},
        {1,0,0,1,0},
        {0,1,1,0,1},
        {0,1,0,1,0}
    };
    int n = 0;
    int visited[5] = {-1,-1,-1,-1,-1};
    ans[0] = 0;
    Hamilton(G, visited, n, 1);
}

But in the output, nothing is showing in the output screen

Did run your code in a **debugger** to see where that error occurs, then run it again with a breakpoint near that failure so you can step ⏯️ carefully ahead and watch what happens leading up to that point? — tadman, Jul 23 '23 at 18:19
What an attractive, clear and descriptive title..... Please understand that "wrong output" is the second most boring title, occuring about ten times a day. Just surpassed by "please do my homework for me". — Yunnosch, Jul 23 '23 at 18:20
A) Under what conditions does this print? B) Where are those conditions set? C) Are you *sure* you're setting the right conditions? D) Why are you using global variables? — tadman, Jul 23 '23 at 18:20
Blank screen, huh? Did you try something like `printf("Start.\n");` as the first thing in your program? That would be a debugging trick to notice when something outside of your algorithm blocks your program from outputting anything. Please try a HelloWorld, to test. — Yunnosch, Jul 23 '23 at 18:22
have some discriptive names for variables. not only will it help you in debugging, it will also help others looking into your code — Sushant, Jul 23 '23 at 18:28
Why did you tag this as `dsa`? Did you read what the `dsa` tag represents? — PaulMcKenzie, Jul 23 '23 at 18:43
Don't use global variables. More often than not, they make your programs undebuggable, especially recursive ones. — n. m. could be an AI, Jul 23 '23 at 19:41
The code increments m from 0 to 3 and then decrements it back to 0. It never gets to 4. — Jerry Jeremiah, Jul 23 '23 at 21:37
Please explain how `G` and `visited` are supposed to work; it is not really obvious. I assume that is an adjacency matrix? — Neil, Jul 24 '23 at 01:21

score 0 · Answer 1 · answered Jul 26 '23 at 06:08

One error is that by n = i; you overwrite the original vertex n, and due to this the resetting visited[n] = -1; later doesn't work. A second error is that f is only incremented and never decremented on backtracking. We can correct those two errors by changing

                     n = i;
                     ans[f++] = i;
                     Hamilton(G, visited, n, f);

to

                     ans[f] = i;
                     Hamilton(G, visited, i, f+1);

- still a remaining problem in the general case (not with cycle graphs as the given G) is that this Hamilton function only finds paths that start at vertex 0.

Couldn't get the required correct output

1 Answers1