Рекурсия не останавливается

Question

Я пишу код для поиска цикла в графе, используя алгоритм DFS. Однако, когда я иду печатать путь цикла, происходит что-то очень странное. Читайте мою озабоченность в комментариях.

#include <iostream> 
#include "graph.h" 
#include <stdio.h>

using namespace std;

int discovered[MAXV+1];
int parent[MAXV+1];

//Printing path that contains the cycle 

void find_path(int start, int end)
{
    int s = start;
    int e = end;

    while(s != e)
    {
        cout<<s<<" ";
        s = parent[s];
    }

/*The loop above does not stops ; 
  which means the condition parent[s] == e ;
  does not meet . However , on printing out the 
  values of s , parent[s] , and e , on successive iteration 
  I can see that the value of parent[s] and e becomes
  equal after a certain time , even though the loop does not 
  terminate.

*/
}

void dfs(graph *g , int start)
{    
    int dis = 1;
    int u = 0 ;
    edgenode *p;

    p = g->edges[start]; 
    discovered[start] = dis;

    while(p!= NULL)
    {
        u = p->y;
        parent[u] = start;

        if(discovered[u]== 1){ cout<<"Cycle"<<start<<u<<endl; find_path(start,u);}
        else dfs(g,u);

        p = p->next;
    }

    discovered[start] = dis +1;
    printf("\n");   
}

int main()
{
    for(int i= 1; i<=MAXV+1; i++)
    {
        discovered[i] = false;
        parent[i] = -1;
    }

    graph *g = new graph();
    read_graph(g,true);

    dfs(g,1);
}

Итак, есть ли ошибка в моей логике при вызове вышеупомянутой рекурсии, или мой компилятор g++ ведет себя странно. Любое прочтение моего кода будет высоко оценено. Благодарю.

PS: Вы можете предположить, что у меня уже есть реализованная структура графов, которую я включаю во время компиляции. И я предполагаю, что у вас есть хорошее представление о реализации алгоритма BFS. Если вы хотите понять код, дайте мне знать.

Answer 1

Алгоритм в dfs сломано. Когда он проверяет ребра от узла 1, он находит ребро от узла 1 к узлу 2 и помечает 1 как родителя для 2. Позже он находит ребро от узла 5 к узлу 2 и отмечает 5 как родителя. из 2, заменив предыдущую запись в parent массив.

Позже, когда он определяет, что есть цикл от 1 до 5 (до 1), он вызывает find_path(5, 1), Тем не мение, find_path никогда не может найти узел 1, потому что следование за родителями с 5 приводит к 4, 3, 2 и обратно к 5.