Algoritmia - Problema con grafos

Hola a Todos
Esta es una lista ligada en c++ que la quiero utilizar para crear rutas de vertices

#include<iostream.h>
int op,pos,dato;
int menu()
{
int opc;
cout<<" MENU"<<endl;
cout<<"1.Insertar datos"<<endl;
//cout<<"2.Eliminar datos"<<endl;
cout<<"2.Mostrar datos"<<endl;
cout<<"3.Salir"<<endl;
cout<<"elija una opcion"<<endl;
cin>>opc;
return opc;
}

class nodo
{

int elemento;
nodo *siguiente;
public:
nodo(int E, nodo *S)//costructor que llena los campos del nodo
{
elemento=E;
siguiente=S;
}
nodo(nodo *S=NULL)// constructor 2 que llena el campo siguiente del nodod CABEZA
{
siguiente=S;
}

int obt_elem()
{
return elemento;
}

nodo *obt_sig()
{
return siguiente;
}
void llenar_sig(nodo* s)
{
siguiente=s;
}
};

class lista
{
nodo *cabeza;
nodo *actual;
nodo *ultimo;

int cont;// contador
public:

//antes del public no se hace operaciones, ni asignaciones
lista();//costructor debe llevar el mismo nombre de la clase, puede resivir argumentos
//COSTRUCTOR DE LISTA VACIA
void insertar(int dato);
void colocarEnPosicion(int pos);//mover el actual, que este en la posicion correcta
void imprimir();
int contador();

};

lista :: lista()//se crea el primer nodo 'CUERPO DE CONSTRUCTOR'
{
cabeza=actual=new nodo;//llama al constructor 2, crea la cabeza
cont=0;
}
void lista ::insertar(int dato)
{

//nodo *aux;
//aux=obt_sig();
actual->llenar_sig(new nodo(dato,actual->obt_sig()));
cont ++;
}
int lista ::contador()
{
return cont;
}
void lista ::colocarEnPosicion(int pos)//ubicacion del actual
{
actual=cabeza;
for(int i=1;i<pos;i++)//asumir que pos es una posicon valida
{
actual=actual->obt_sig();//avance del actual
}


}

void lista ::imprimir()
{
actual=cabeza;
for(int i=0;i<cont;i++)//mostrando lista
{
//cout<<actual->elemento<<" ";
actual=actual->obt_sig();
cout<<actual->obt_elem()<<" ";
}
cout<<endl;
}

void main()
{

lista L1;//se crea el objeto L1 que es de la claselista, en este momento se llama al constructor lista();

do
{
//imprimir el menu
op=menu();
switch(op)
{
case 1:

cout<<"ingrese un dato"<<endl;
cin>>dato;

do
{
cout<<"ingrese una posicion"<<endl;
cin>>pos;

//cout<< L1.contador;
}while(pos>L1.contador()+1);

L1.colocarEnPosicion(pos);

L1.insertar(dato );
break;
case 2:

L1.imprimir();
break;
case 3:
cout<<"gracias"<<endl;
break;
default:
cout<<"Error"<<endl;

}

}while(op!=3);
}

esta es la forma en q hice una lista pero por ahi averigue q necesito un vector con punteros q enlazan a vertices y no entiendo como pueda llenar un vector con punteros en esta lista, otra duda si es q realizo una busqueda y la lista se expresa de esta forma .
1-->3,nombre,peso-->5,nombre,peso
2-->1,nombre,peso-->3,nombre,peso
3-->4,nombre,peso-->1,nombre,peso
1 lista solo buscaria una trayectoria de vertices (1-->3-->5) ,
tendria q crear varias listas para las demas trayectorias y creo q no se puede hacer eso.

estoy reconfundida ayudenme pliz muchachos.

Para representar rutas de vértices utilizando listas ligadas en C++, necesitarás modificar tu implementación actual para que cada nodo de la lista contenga la información necesaria para representar un vértice y sus conexiones. Además, podrías utilizar un vector de punteros para almacenar los vértices y sus respectivas listas de adyacencia.

Aquí te muestro una forma de modificar tu código para que puedas representar y manipular rutas de vértices:


En este código, he creado clases separadas para representar los nodos de los vértices y los nodos de las listas de adyacencia. Además, he utilizado un vector para almacenar punteros a los vértices y luego he creado una lista de adyacencia para cada vértice.

Puedes adaptar esta estructura para representar y manipular las rutas de vértices según tus necesidades. ¡Espero que esto te ayude a aclarar tus dudas y avanzar en tu proyecto, Patricia!