En este hilo que tiene chincheta se explica la implementación de un menú, es una pregunta muy común, hay que esforzarse un poco más en buscar 

http://foro.elhacker.net/programacion_cc/para_que_dejeis_de_preguntar_de_una_vez_por_los_menus-t276719.0.html

Una estructuctura es un tipo de dato compuesto de un conjunto de tipos qué puedes ser estructucturas o no. Hay un aspecto importante, y es que son datos definidos por el programador. ¿Cuándo necesitamos las estructuras? Cuando queremos modelizar un concepto del mundo real.

En la práctica podemos entender la estructura como un objeto/ser/ente  y los tipos de los que se compone serían atributos o características de dicho ente.

Lo que te aconsejo para abordar este tipo de problemas es leer cuidadosamente el enunciado e ir extrayendo cada posible ente y sus características. Por ejemplo:


De cada especie[\b] necesitamos guardar su nombre, el número de ejemplares, la
fecha de incorporación a la reserva natural, la sección del centro donde se van a
emplazar y el habitáculo concreto.

Nombre de la estructura -> especie
Atributos, (campos de la estructura) -> nombre, ejemplares, fecha de incorporacion, sección del centro, habitaculo

Las cadenas son un tanto especiales, ya que cuando pasas (char *) estás pasado el valor de la cadena, no su referencia. Para modificar una cadena tienes que pasar una doble referencia.

#include <iostream>
 
using namespace std;
 
void hacerIgualAChauMundo(char **cadena) {
    *cadena = "Chau mundo";
}
 
int main() {
    char *cadena = "Hola mundo";
 
    hacerIgualAChauMundo(&cadena);
 
    cout << cadena << endl;
 
    return 0;
}

No, me refiero a que magnitudes usas para cuantificar el "beneficio", ¿qué significa tener más beneficio en un camino respecto de otro?, ¿Longitud, tiempo de recorrido ... ?

Los arboles son grafos no ponderados y este es un grafo ponderado en funcion del beneficio, que no sé que métrica seguirá ¿Puedes ponernos un laberinto de ejemplo?

No te digo yo que sea mala opción, pero cuando no tienes soltura es más sencillo modelizarlo con estructuras, aparte de que te queda un código más sencillo de entender y ese TAD grafo lo puedes reutilizar para numerosos problemas, ya que créeme te hartarás a ver grafos en la carrera xD.  

Como primera idea se me ocurre algo así, definir el tipo arista y el tipo nodo


typedef int NODO;

typedef struct {
NODO u;
NODO v;
int peso;
}ARISTA;


typedef struct {
 ARISTA[] aristas;
 NODO [] vertices;
}GRAFO;

Ahora el siguiente paso, seria definir las primitivas que el algoritmo de BT va a necesitar. Te pongo es pseudocódigo y me respondes que se te ocurre

In order to apply backtracking to a specific class of problems, one must provide the data P for the particular instance of the problem that is to be solved, and six procedural parameters, root, reject, accept, first, next, and output. These procedures should take the instance data P as a parameter and should do the following:

    root(P): return the partial candidate at the root of the search tree.
    reject(P,c): return true only if the partial candidate c is not worth completing.
    accept(P,c): return true if c is a solution of P, and false otherwise.
    first(P,c): generate the first extension of candidate c.
    next(P,s): generate the next alternative extension of a candidate, after the extension s.
    output(P,c): use the solution c of P, as appropriate to the application.

The backtracking algorithm reduces the problem to the call bt(root(P)), where bt is the following recursive procedure:

procedure bt(c)
  if reject(P,c) then return
  if accept(P,c) then output(P,c)
  s ← first(P,c)
  while s ≠ Λ do
    bt(s)
    s ← next(P,s)

Antes de nada, buscas hacerlo de un nodo a los demás únicamente, ¿De qué naturaleza son los grafos con los que vas a tratar? (Densos, dispersos . ..) ¿Hay caminos negativos? 

Hola chicos, pues voy a hacer mi primera aportación de código a ver si os parece útil. Es una clase que está pensada como almacén de datos de juegos basado en tablero de celdas. Me ha servido para implementar el juego de la vida y seguro que os puede servir para juegos como el tres, el cuatro en raya, damas, que se yo xD.

 
    /*************************************************************************************
     * This class implements a bit board                                                 *
     *                                                                                   *
     * Foreach bit we have one cell. If we turn on a bit means occupied cell. By the     *
     * opposite, if we turn off the bit, means empty cell                                *
     * The main gain of a bitBoard is to decrease the amount of memory used.             *
     * this fact is so important in algorithms like Minimax                              *
     * foreach byte we can cover 8 positions                                             *
     * For instance: If we have and 8x8 board, we can save 64 cells in a 8x1 board       *
     * (8 bytes) because 1 byteCell can save 8 cells                                     *
     *************************************************************************************/
 
 
   public class Board
    {
 
        protected readonly byte[,] board;
        protected readonly int height;
        protected readonly int byteWidth;
        protected readonly int width;
 
        protected Board(int height, int width)
        {
            this.height = height;
            this.byteWidth =(int) Math.Ceiling(width * 0.125); // 0.125 * width = width /8  
            this.width = width; 
            board = new byte[height, byteWidth];
        }
 
 
        private byte IncreaseBitPosn(int n)
        {
 
            return (byte)(0x1 << n);
        }
        private byte ReverseByte (byte b)
        {
            return  (byte) (b ^ 0xFF);
        }
 
        private int ToByteColumn(int y)
        {
            return (int) 0.125 * y;
        }
 
        private int ToBitColumn(int y)
        {
            return (y >= 8) ? y - (ToByteColumn(y) * 8) : y;
        }
 
        /* 
        *  Checks if [x,y] is empty with an and bitwise
        *  For instance: 
        *  x = 3
        *  y = 7  -> Matchs to byteCol 0, bitCol 7 
        *  board (3,0)        = 1 0 0 1 0 1 0 0 
        *  IncreaseBitPosn(7) = 1 0 0 0 0 0 0 0
        *  1 0 0 1 0 1 0 0 &  1 0 0 0 0 0 0 0 = 1 0 0 0 0 0 0 0 != 0 -> returns false               
        */
        protected bool PosIsEmpty(int x, int y)
        {
            return (board[x, ToByteColumn(y)] & IncreaseBitPosn(ToBitColumn(y))) == 0;
	    }
        /* 
        *  Increases bit at position (x,y)
        *  For instance: 
        *  x = 3
        *  y = 7  -> Matchs to byteCol 0, bitCol 7 
        *  board (3,0)        = 1 0 0 1 0 1 0 0 
        *  IncreaseBitPosn(7) = 1 0 0 0 0 0 0 0
        *  0 0 0 1 0 1 0 0  |  1 0 0 0 0 0 0 0 = 1 0 0 1 0 1 0 0  
        */ 
        protected void turnOnBit(int x, int y)
        {
            board[x, ToByteColumn(y)] |= IncreaseBitPosn(ToBitColumn(y));
        }
        /* 
         *  Decreases bit at position (x,y)
         *  For instance: 
         *  x = 3
         *  y = 7  -> Matchs to byteCol 0, bitCol 7 
         *  board (3,0)        = 1 0 0 1 0 1 0 0 
         *  ReverseByte(IncreaseBitPosn(7)) = 0 1 1 1 1 1 1 1
         *  1 0 0 1 0 1 0 0  &  0 1 1 1 1 1 1 1 = 0 0 0 1 0 1 0 0  
         */
 
        protected void turnOffBit(int x, int y)
        {
            board[x, ToByteColumn(y)] &=  ReverseByte(IncreaseBitPosn(ToBitColumn(y)));
        }
 
    }
 

Hola Ivan, estás de suerte porque tengo muy reciente estos temas ya que yo los estoy estudiando también xD, aunque no tengo que usar C por suerte  .

El backtracking es una técnica que se aplica al algoritmo de búsqueda en profundidad. El código se encuentra en wikipedia. Es un algoritmo de búsqueda en grafos, por lo que tenemos que modelizar el laberinto como un grafo, como estamos en C, deberemos definir un TAD Grafo mediante estructuras.

Antes de seguir, ¿Cómo llevas los grafos? ¿Los has estudiado?

Te corrijo un poco, Java y C++ son imperativos, supongo que te refieres a que ahora está estudiando programación estructurada . Tanto la orientación a objetos como la orientación a estructuras son programación imperativa puesto que cada instrucción es una orden que ayuda a resolver el problema. El ordenador hace lo que tu le pides

En la programación declarativa  tu defines el problema y el intérprete lo resuelve con un algoritmo interno (búsqueda con backtracking en el caso de prolog) o bien delegando el proceso en funciones inmutables (Programacion funcional)  que para una misma entrada siempre devuelven una misma salida