Ejercicio de Grafo en Profundidad c++

RECORRIDO EN PROFUNDIDAD PROGRAMA

programa en c++ adaptado de

https://raw.githubusercontent.com/jariasf/Online-Judges-Solutions/master/Algorithms/C++/Graph%20Theory/Algoritmo%20DFS%20usando%20Recursion.cpp

/*

adaptado por paola martinez , carlos diaz y jorge hernández

*/

#include <stdio.h>

#include <cstring>

#include <vector>

using namespace std;

#define MAX 550

vector<int> ady[ MAX ];  //lista de adyacencia

bool visitado[ MAX ];    //para nodos visitados

int V;

int path[ MAX ];         //para guardar la direccion del  recorrido

///Ver todo el recorrido del grafo de acuerdo al orden ingresado en la lista de adyacencia

bool first;

void dfs( int u )

{

   ( first )? printf("%d" , u ) : printf("->%d" , u ); //operador terneario

   first = false;

   visitado[ u ] = true;

   for( int v = 0 ; v < ady[ u ].size(); ++v )

{

       if( !visitado[ ady[ u ][ v ] ] ){

           dfs( ady[ u ][ v ] );

       }

   }

}

///Ver todos las rutas posibles partiendo de nodo inicial y llegando a uno final, usamos backtracking

void dfs_allPath( int u , int fin , int len ){

   visitado[ u ] = true;

   path[ len ] = u;                    //almaceno la direccion del vertice actual

   if( u == fin ){                     //si se llego al final imprimimos ese path

       first = true;

       for( int i = 0 ; i <= len ; ++i ){

           ( first ) ? printf("%d" , path[i]) : printf("->%d" , path[i] );

           first = false;

       }

       printf("\n");

       return;

   }

   for( int i = 0 ; i < ady[ u ].size(); ++i ){

       int v = ady[ u ][ i ];

       if( !visitado[ v ] ){

           dfs_allPath( v , fin , len + 1 );

           //parte para backtracking, aquellos nodos hoja ya que no poseen adyacentes o ya fueron visitados

           visitado[ v ] = false;              //marcamos como no visitado para usarlo posteriormente en otro path

       }

   }

}

int main(){

   int E , x , y, inicial , final;

   scanf("%d %d" , &V , &E );      //Numero de vertices y numero de aristas

   printf("Digita las entradas para generar grafo");

   for(int i = 1 ; i <= E ; ++i )

{

   

printf("Por favor dijita x y y ");

       scanf("%d %d" , &x , &y );  //Origen y destino

       ady[ x ].push_back( y );

       ady[ y ].push_back( x );    //Commentar si se desea aplicar en grafo dirigido

   }

   

   first = true;

   //Veremos todo el recorrido del grafo iniciando en el vertice ingresado

   printf("Nodo raiz: ");

   scanf("%d" , &inicial );

   memset( visitado , 0 ,sizeof( visitado ) );

   printf("Recorrido DFS de todo el grafo\n");

   dfs( inicial );

   printf("\n\n\n");

   //Veremos posibles rutas de nodo inicial a uno final

   memset( visitado , 0 , sizeof( visitado ) );        //inicializar a no visitado

   printf("Posibles Rutas de inicial a final usando regreso\n");

   printf("Nodo Final: ");

   scanf("%d" , &final );

   dfs_allPath( inicial , final , 0 );                     //posibles rutas de nodo inicial a final

   return 0;

}

ejecución