Grafos

Disculpa mira si se de hecho eso es algo de mates discretas es muy fácil y programarlo es lógica y algunas definiciones pero a lo que voy a mira te pongo este código conocido es el de Disjktra muy fácil checalo no tengo más tiempo de entrar en detalle ya que ando programando también para el trabajo y esc pero aquí estoy para servirte! esta en c++
#include<Graphics.h>
#include<ConIO.h>
#include<DOS.h>
#include<Stdlib.h>
#include <IOManip.h>
#include <StrStream.h>
#include <StdIO.h>
#include <FStream.h>
#include <IOStream.h>
#include <CType.h>
#include <DOS.h>
#include <graphics.h>
#include <IOStream.h>
#include <IOManip.h>
#include <FStream.h>
#include <ConIO.h>
#include <StdIO.h>
#include <StdLib.H>
#include <DOS.h>
#include <String.H>
#include <CType.H>
#include <Math.H>
//******************************************************************************
// INICIO DE IMPLEMENTACION ALGOTIMOS PARA GRAFO DIRIGIDO
//******************************************************************************
//-----------------------------------------------------------------------------------
//Declaraci¢n de prototipos de funciones:
void Cursor(int X,int Y,char *Cad,int Color,int pos, int Oprimido);
void Ventana(int x1, int y1, int x2, int y2,
                                    int ColorArribaIzquierda, int ColorAbajoDerecha,
                                    int ColorFondo);
void Icono1(int x, int y);
void Icono2(int x, int y);
void Icono3(int x, int y);
//-----------------------------------------------------------------------------------
//Definiciones de constantes:
const unsigned long Infinito=4294967295/2;//M ximo unsigned long
//advertencia: Solo utilizar pesos de aristas hasta 4294967295/2
//esto debido a que tendremos que hacer comparaciones de
//infinito>infinito + peso  y no nos dar¡a el c lculo.
//Si el peso de las aristas tiene decimales, cambiar todos los unsigned int
//de este programa, al tipo num,rico conveniente
const char NombreArch[20] = "Dijkstr5.Gfa";
const    int AltoIcono=20, AnchoIcono=150, MaxIco=3,
                    Xi=1, Yi=1, DeltaX=AnchoIcono+2,
                    PaletaXi=1, PaletaYi=460, AltoPaleta=20, LargoPaleta=40,
                    MaxColores=16,
                    EspacioGrafoXo=0, EspacioGrafoYo=AltoIcono+2,
                    EspacioGrafoXf=639, EspacioGrafoYf=479-AltoPaleta,
                    AnchoVertice=10; //del cuadrado que representa cada v,rtice en pantalla
//-----------------------------------------------------------------------------
//Definiciones de de tipos de datos registros(struct)
typedef struct VERTICE VERTICE;
typedef struct ARISTA ARISTA;
typedef struct INFOVERTICE INFOVERTICE;
typedef struct INFOARISTA INFOARISTA;
struct INFOARISTA{
    unsigned long PesoArista;
    char NombreDestino;  // Etiqueta del v,rtice de destino de la arista
};
struct ARISTA{
    INFOARISTA Info; // informaci¢n de cada arista
    VERTICE *Ady;   //puntero desde el v,rtice de origen al v,rtice de destino
    ARISTA *Sig;    //puntero en la lista anlazada de aristas
};
struct INFOVERTICE{
    char NombreVertice;  // Etiqueta del v,rtice
    char Estado; //En los recorridos. 1:Preparado, 2:Espera, 3:Procesado
    int x, y; //Posici¢n del v,rtice en la pantalla
    unsigned long d; //En algoritmo de Dijkstra es distancia acumulada m¡nima
};
struct VERTICE{
    INFOVERTICE Info; //Informaci¢n propia de cada nodo.
    ARISTA *Cab;//Apunta a cada sublista desde cada nodo de la lista principal
    VERTICE *Sig;//Apunta al siguiente v, rtice en la lista enlazada. El siguiente
                             //Vertice no quiere decir que este adyacente en el grafo, esto
                             //Solo ser, de casualidad. Para los adyacentes ver struct ARISTA
    VÉRTICE *Predecesor; //En algunos recorridos, ser el v, rtice anterior.
                                    //El padre si vemos el recorrido como un rbol.
                                    //En otros casos, no aun aquí, podría ser una lista de los
                                    //Nodos que llegan a este(es decir aristas que llegan)
};
//-----------------------------------------------------------------------------------
//Definici¢n de variables globales:
struct VERTICE *CAB=NULL;// variable global la cual apuntar  a la cabeza de la
        // lista simplemente enlazada que almacena los v,rtices(nodos) del grafo.
fstream BufferArchivo; //
char *IDVertices; //para cada v,rtice se utilizaran letras may£sculas(26)
                                    //como se ve es trivial superar la cantidad de 26
int N=0;//Este ser  el n£mero de v,rtices en el grafo.
int PosIcoX[MaxIco];
//Definici¢n de arreglo de punteros a funciones:
void (*Icono[MaxIco])(int, int) = {Icono1,Icono2,Icono3};
//-----------------------------------------------------------------------------------
//A continuaci¢n las funciones del programa
//-----------------------------------------------------------------------------------
VERTICE *InsertarVerticeEnGrafo (INFOVERTICE Item){//Inserta en la lista principal
    VERTICE *p, *q, *NuevoNodo;
    NuevoNodo = new(VERTICE);
    if ( NuevoNodo == NULL ) {
        cout << "No hay memoria suficiente";
        return(NULL);  // No insertado
    }
    p = NULL;
    q = CAB;
    while (q != NULL && Item.NombreVertice > q->Info.NombreVertice){
        p = q;
        q = q->Sig;
    }
    if (q && Item.NombreVertice == q->Info.NombreVertice) {
        delete(NuevoNodo);
        return (NULL);  //repetido,
    }
    NuevoNodo->Info = Item;
    NuevoNodo->Sig  = q;
    NuevoNodo->Cab  = NULL;
    if ( p == NULL)
        CAB = NuevoNodo;  //era el primero de la lista
    else
        p->Sig = NuevoNodo; //"caso general"
    return(NuevoNodo); // insertado
}
//-----------------------------------------------------------------------------------
int EliminarVerticeDelGrafo(VERTICE *p){
 VERTICE *q;
    if (p == CAB)
        CAB = p->Sig; //eliminado el primer VERTICE de la lista
    else {
        q = CAB;
        while (q->Sig != p)
            q = q->Sig;
            q->Sig = p->Sig;
    }
    delete(p);
    return 1;
}
//-----------------------------------------------------------------------------------
VERTICE* EncontrarVerticeDelGrafo(INFOVERTICE Item){
    VERTICE *p;
    p = CAB;
    while (p && Item.NombreVertice > p->Info.NombreVertice)
        p = p->Sig;
    if(p && Item.NombreVertice != p->Info.NombreVertice)  // No encontrado
        p= NULL;
    return p;
}
//-----------------------------------------------------------------------------------
void ListarVerticesDelGrafo(){
    if (!CAB)
        cout << "Lista vac¡a \a";
    else {
        VERTICE *p = CAB;
        int i=0;
        cout << "Orden en lista    Etiqueta\n";
        while ( p ){
            cout << setw(5) << ++i
                     << "            " << p->Info.NombreVertice << endl;
            p = p->Sig;
        }
    }
}
//-----------------------------------------------------------------------------------
void CapturarVertice(char Grafico){
    INFOVERTICE Item;
    if(Grafico=='S'){
    }
    else{
        cout << "\n\Nombre de la etiqueta del v,rtice: ";
        Item.NombreVertice = getche();
    }
    if ( InsertarVerticeEnGrafo(Item) == 0 ){
        cout << "\n\nRepetido \a";
        getch();
    }
}
//-----------------------------------------------------------------------------------
void EliminarVertice(){
    INFOVERTICE Item;
    VERTICE *Vertice;
    if (CAB == NULL)
        cout << "Lista vac¡a \a";
    else{
        cout << "\n\nDigite etiqueta del v,rtice: ";
        Item.NombreVertice    = getche();
        Vertice = EncontrarVerticeDelGrafo(Item);
        if (Vertice)
            if(!Vertice->Cab)  //Se elimina, solo si no tiene adyacentes
                EliminarVerticeDelGrafo(Vertice);
            else{
                cout<<"\n\nEste v,rtice tiene todav¡a aristas. Favor eliminarlas primero";
                getch();
            }
        else {
            cout << "\n\nNo encontrado en grafo un v,rtice con el nombre: "
                     << Item.NombreVertice;
            getch();
        }
    }
}
//-----------------------------------------------------------------------------------
void EncontrarVertice(){
    INFOVERTICE Item;
    VERTICE *Vertice;
    if (CAB == NULL)
        cout << "Lista vac¡a \a";
    else{
        cout << "\n\nDigite etiqueta del v,rtice a encontrar: ";
        Item.NombreVertice = getche();
        Vertice = EncontrarVerticeDelGrafo(Item);
        if (Vertice)
            cout << "\n\nEncontrado en grafo";
        else
            cout << "\n\nNo encontrado en grafo";
    }
    getch();
}
// ===========================================================================
// A CONTINUACION LAS FUNCIONES PARA MANEJAR CADA ARISTA(SubLista enlazada)
// ===========================================================================
ARISTA *InsertarArista (INFOARISTA Item, ARISTA *Cab, VERTICE *Destino){
    ARISTA *p, *q, *NuevoNodo;
    if ( (NuevoNodo = new ARISTA ) == NULL ){
        cout << "No hay memoria suficiente";
        return NULL;
    }
    //Se insertar n en orden ascendente por el peso de la arista
    p = NULL;
    q = Cab;
    while (q != NULL && Item.PesoArista > q->Info.PesoArista){
        p = q;
        q = q->Sig;
    }
    NuevoNodo->Info = Item;
    NuevoNodo->Sig  = q;
    NuevoNodo->Ady  = Destino;
    if ( p == NULL)
        Cab = NuevoNodo;  //era el primero de la lista
    else
        p->Sig = NuevoNodo; //"caso general"
    return(Cab);
}
//-----------------------------------------------------------------------------------
ARISTA *EliminarArista(ARISTA *p, ARISTA *Cab){
    ARISTA *q;
    if (p == Cab)
        Cab = p->Sig; //eliminado el primer nodo de la lista
    else {
        q = Cab;
        while (q->Sig != p)
            q = q->Sig;
            q->Sig = p->Sig;
    }
    delete(p);
    return Cab;
}
//-----------------------------------------------------------------------------------
ARISTA* EncontrarArista(ARISTA *Cab, VERTICE *Destino){
    ARISTA *p;
    p = Cab;
    while (p && Destino != p->Ady)
        p = p->Sig;
    return p;
}
//-----------------------------------------------------------------------------------
void ListarSubListaDeAristas(ARISTA *Cab){
    ARISTA *p;
    int Adyacentes=0;
    if (!Cab)
        cout << "No tiene aristas \a\n";
    else {
        p = Cab;
        cout << "No.   Peso   Etiqueta Destino\n";
        while ( p ){
            cout << setw(2) << ++Adyacentes << ":   "
                     << setiosflags(ios::left) << setw(10) << p->Info.PesoArista
                     << setw(15) << p->Ady->Info.NombreVertice << endl;
            p = p->Sig;
        }
    }
}
//-----------------------------------------------------------------------------------
ARISTA *CapturarSubLista(ARISTA *Cab){
    INFOARISTA ItemArista;
    INFOVERTICE ItemVertice;
    VERTICE *Destino;
    cout << "\n\Etiqueta v,rtice de destino: ";
    cin >> ItemVertice.NombreVertice;
    Destino= EncontrarVerticeDelGrafo(ItemVertice);
    if(Destino){
        cout << "\n\Peso de la arista a insertar: ";
        cin >> ItemArista.PesoArista;
        ItemArista.NombreDestino = ItemVertice.NombreVertice;
        Cab = InsertarArista(ItemArista, Cab, Destino );
        if ( !Cab  ){
            cout << "\n\nNo se pudo insertar: se llen¢ la memoria\a";
            getch();
        }
    }
    else{
        cout << "\n\aEste destino no existe en el grafo\a";
        getch();
    }
    return Cab;
}
//-----------------------------------------------------------------------------------
ARISTA* BorrarSubLista(ARISTA *Cab){
    INFOVERTICE Item;
    ARISTA *A;
    VERTICE *Destino;
    if (Cab == NULL)
        cout << "Lista vac¡a \a";
    else {
        cout << "\n\nDigite etiqueta del nombre del  v,rtice de destino: ";
        Item.NombreVertice = getche();
        Destino= EncontrarVerticeDelGrafo(Item);
        if(Destino){ // Se encontr¢ el destino, veamos si forma arista:
            A = EncontrarArista(Cab, Destino);
            if (A)
                Cab = EliminarArista(A, Cab);
            else {
                cout << "\n\nNo encontrada esta arista";
                getch();
            }
        }
        else{
            cout << "\n\nNo encontrado en grafo el v,rtice " << Item.NombreVertice;
            getch();
        }
    }
    return Cab;
}
//-----------------------------------------------------------------------------------
void EncuentraSubLista(ARISTA *Cab){
    INFOVERTICE Item;
    ARISTA     *p;
    VERTICE *Destino;
    if (Cab == NULL)
        cout << "Lista vac¡a \a";
    else{
        cout << "\n\nDigite Nombre de v,rtice de destino: ";
        Item.NombreVertice = getch();
        Destino= EncontrarVerticeDelGrafo(Item);
        if(Destino){
            p = EncontrarArista(Cab, Destino);
            if (p)
                cout << "\n\nEncontrada esta arista y tiene el peso "
                         << p->Info.PesoArista;
            else
                cout << "\n\nNo encontrada arista al vertice  " << Item.NombreVertice;
        }
        else
            cout <<"\n\nNo existe en grafo vertice de destino "<<Item.NombreVertice;
    }
    getch();
}
//-----------------------------------------------------------------------------------
void MenuSubListaDeAristas(){
    char op;
    INFOVERTICE Item;
    VERTICE *q;
    if(CAB){
        clrscr();
        cout << "Nombre del v,rtice de origen: ";
        Item.NombreVertice = getche();
        q = CAB;
        while (q && Item.NombreVertice != q->Info.NombreVertice)
                q = q->Sig;
        if (!q){
            cout << "No se encuentra ningun v,rtice de etiqueta: " << Item.NombreVertice;
            getch();
        }
        else
            do{
                clrscr();
                cout << "Estas son las aristas del v,rtice: "
                         << q->Info.NombreVertice << endl;
                ListarSubListaDeAristas(q->Cab);
                cout<< "\nSUBMENU DE ARISTAS: Insertar Borrar Encontrar ESCape: ";
                op = toupper(getch());
                switch (op){
                    case 'I': q->Cab=CapturarSubLista(q->Cab); break;
                    case 'B': q->Cab=BorrarSubLista(q->Cab);   break;
                    case 'E': EncuentraSubLista(q->Cab);       break;
                }
            } while (op != 27);
    }
    else{
        cout << "No hay v,rtices en el grafo\a";
        getch();
    }
}
//===========================================================================
void GrabarSubListas(VERTICE *V){  // funci¢n recursiva
    ARISTA *A;
    int n;
    if ( V ) {
        A = V->Cab;
        n = 0;
        while(A) { //Cuenta # nodos en sublista enlazada de aristas
            n++;
            A=A->Sig;
        }
        BufferArchivo.write((char *)&n, sizeof(n)); //Graba en disco #nodos(aristas)
        A = V->Cab;
        while(A) {
            BufferArchivo.write((char *)&A->Info, sizeof(A->Info));
            A=A->Sig;
        }
        GrabarSubListas(V->Sig);
    }
}
//-----------------------------------------------------------------------------------
void Grabar(){
    int NumeroVertices=0;
    BufferArchivo.open(NombreArch, ios::out|ios::binary|ios::trunc);
    if (!BufferArchivo)
        cout << "Error en la apertura del archivo \a";
    else{
        VERTICE *V;
        V = CAB;   //Se cuentan y luego graban el n£mero de v,rtices
        while(V){
            NumeroVertices++;
            V = V->Sig;
        }
        BufferArchivo.write((char *)&NumeroVertices, sizeof(NumeroVertices));
        V = CAB;   //Se graban a continuaci¢n la info de todos los v,rtices
        while(V){
            BufferArchivo.write((char *)&V->Info, sizeof(V->Info));
            V = V->Sig;
        }
        GrabarSubListas(CAB);//Se graba, recursivamente, info de todas las aristas
        BufferArchivo.close();
    }
}
//-----------------------------------------------------------------------------------
void CargarLISTA_y_SubListas(){
    INFOVERTICE Vertice; //registro que lee con info de cada v,rtice
    VERTICE *V, *Destino;
    int n; //n£mero de nodos en cada sublista, lo lee desde disco cada vez
    int NumeroVertices=0;
    INFOARISTA Arista; //registro que lee con info de cada arista
    CAB = NULL;  //Esta variable se mantiene global
    BufferArchivo.open(NombreArch,ios::in|ios::binary);
    if (!BufferArchivo){
        cout << "No se puede abrir el archivo \a\n";
    }
    else {
        BufferArchivo.read((char *)&NumeroVertices, sizeof(NumeroVertices));
        int i=0;//a continuaci¢n lee desde disco, todos los v,rtices y los
                        //inserta en lista enlazada principal
        while(i < NumeroVertices){
            BufferArchivo.read( (char *)&Vertice, sizeof(Vertice) );
            InsertarVerticeEnGrafo(Vertice);
            i++;
        }
    //A continuaci¢n se recorre la lista enlazada de v,rtices, ya en RAM y
    //simult neamente se leen de disco, para cada vertice, el n£mero de aristas
    //y  luego cada una de ellas(insert ndolas en el lugar corrrepondiente)
        V = CAB;
        while(V){
            BufferArchivo.read( (char *)&n, sizeof(n) );  //# nodos(aristas) en sublista
            V->Cab=NULL;//ya estaba en nulo, no es necesario
            for(i=0; i<n; i++){
                BufferArchivo.read( (char *)&Arista, sizeof(Arista));
                //buscar su  enlace adyacente  NombreDestino
                Destino = CAB;
                while(Destino && Destino->Info.NombreVertice != Arista.NombreDestino)
                    Destino = Destino->Sig;
                if(Destino)
                    V->Cab = InsertarArista(Arista, V->Cab, Destino);
                else
                    return;//ERROR:dado como se grab¢ en disco, es de esperar nunca ocurrir
            }
            V = V->Sig;
        }
        BufferArchivo.close();
    }
}
//-----------------------------------------------------------------------------------
void ListarGrafoComoTexto(){
    if (!CAB)
        cout << "Lista vac¡a \a\n";
    else {
        VERTICE *V = CAB;
        ARISTA *A;
        cout << "ORIGEN     DESTINO   DISTANCIA ARISTA EN PIXELES\n";
        while ( V ){
            if (V->Cab){
                A = V->Cab;
                while ( A ){
                    cout << V->Info.NombreVertice
                             << "          " << A->Ady->Info.NombreVertice
                             << "          "<< setw(10) << A->Info.PesoArista << endl;
                    A = A->Sig;
                }
            }
            else
                cout << setw(2) << V->Info.NombreVertice << endl;
            V = V->Sig;
        }
    }
}
/****************************************************************************/
/*  INICIO FUNCIONES PARA EL MANEJO DEL MOUSE CON INTERRUPCION 33 DEL DOS   */
/****************************************************************************/
int IniciarMouse(int &BotonMouse){
    union REGS entra,sale;
    entra.x.ax = 0x0000;
    int86( 0x33, &entra, &sale);
    BotonMouse = sale.x.bx;
    return ( sale.x.ax );
}
/****************************************************************************/
void MostrarCursorMouse(void){
    union REGS entra, sale;
    entra.x.ax = 0x0001;
    int86 ( 0x33, &entra, &sale );
}
/****************************************************************************/
void EsconderCursorMouse(void){
    union REGS entra, sale;
    entra.x.ax = 0x0002;
    int86( 0x33, &entra, &sale);
}
/****************************************************************************/
int ClickMouseEnXY( int &x, int &y){
    union REGS entra,sale;
    entra.x.ax = 0x0003;
    int86( 0x33, &entra, &sale );
    x = sale.x.cx;
    y = sale.x.dx;
    return(sale.x.bx);
}
//**************************************************************************
void CursorMouseAXY( int x, int y ){
 union REGS entra, sale;
 entra.x.ax = 0x0004;
 entra.x.cx = x;
 entra.x.dx = y;
 int86( 0x33, &entra, &sale);
}
//----------------------------------------------------------------------------------
void ListarGrafoComoGrafico(int Color){
    char Cad[2]=" ";
    if (CAB){
        VERTICE *V;
        ARISTA *A;
        setlinestyle(SOLID_LINE, 1, 3);
        V = CAB;
        while ( V ){
            EsconderCursorMouse(); setfillstyle(SOLID_FILL, Color);
            bar(V->Info.x-(AnchoVertice>>1),V->Info.y-(AnchoVertice>>1),
                    V->Info.x+(AnchoVertice>>1),V->Info.y+(AnchoVertice>>1));
            Cad[0]=V->Info.NombreVertice;
            setcolor(BLACK);
            outtextxy(V->Info.x-3, V->Info.y-2, Cad);
            MostrarCursorMouse();
            A = V->Cab;
            while ( A ){
                EsconderCursorMouse();
                setcolor(YELLOW);
                line(V->Info.x, V->Info.y,
                         A->Ady->Info.x, A->Ady->Info.y);
                setfillstyle(SOLID_FILL, Color);
                bar(V->Info.x-(AnchoVertice>>1),
                        V->Info.y-(AnchoVertice>>1),
                        V->Info.x+(AnchoVertice>>1),
                        V->Info.y+(AnchoVertice>>1));
                Cad[0]=V->Info.NombreVertice; Cad[1]=NULL;
                setcolor(BLACK);
                outtextxy(V->Info.x-3, V->Info.y-2, Cad);
                bar(A->Ady->Info.x-(AnchoVertice>>1),
                        A->Ady->Info.y-(AnchoVertice>>1),
                        A->Ady->Info.x+(AnchoVertice>>1),
                        A->Ady->Info.y+(AnchoVertice>>1));
                Cad[0]=A->Ady->Info.NombreVertice; Cad[1]=NULL;
                outtextxy(A->Ady->Info.x-3, A->Ady->Info.y-2, Cad);
                MostrarCursorMouse();
                A = A->Sig;
            }
            V = V->Sig;
        }
    }
    setlinestyle(SOLID_LINE, 1, 1);
}
//----------------------------------------------------------------------------------
//----------------------------------------------------------------------------------
//ALGORITMO DE RECORRIDO EN PROFUNDIDAD UTILIZANDO UNA PILA
//----------------------------------------------------------------------------------
struct Pila{
    VERTICE *V;
    Pila *Sig;
} *Cima = NULL;
//-----------------------------------------------------------------------------------
void InsertarEnPila(VERTICE *V){
    Pila *Nuevo;
    Nuevo = new Pila;
    Nuevo->V = V;
    Nuevo->Sig = Cima;
    Cima = Nuevo;
}
//-----------------------------------------------------------------------------------
VERTICE *SacarDePila(){
    VERTICE *EnCima;
    Pila  *p;
    EnCima = Cima->V;
    p = Cima;
    Cima = Cima->Sig;
    delete(p);
    return EnCima;
}
//-----------------------------------------------------------------------------------
void RecorridoEnProfundidad(){ //Al utilizar una Pila. Los nodos adyacentes
//estan siendo procesados de mayor arista primero a menor. Ya que la sublista
//esta clasificada en orden ascendente. Primero el menor, pero al colocarlos
//en Pila quedan al contrario. Es decir que esta prefiriendo el mayor.
//Para que tome el menor habria que modificar esta funcion y que lo haga
//recursivamente, la insercion en la Pila
    INFOVERTICE Item;
    VERTICE *Origen, *p, *N;
    ARISTA *A;
    if(CAB){
        cout << "\nDigite la etiqueta del v,rtice de origen: ";
        cin >>Item.NombreVertice;
        Origen = EncontrarVerticeDelGrafo(Item);
        if(!Origen)
            cout << "\nV,rtice no existe en el Grafo\a";
        else{
            p = CAB;
            while(p){
                p->Info.Estado = 1;
                p = p->Sig;
            }
            InsertarEnPila(Origen);
            Origen->Info.Estado = 2;
            cout << endl;
            while(Cima){ //Mientras que la cola no est, vac¡a
                N = SacarDePila();
                cout << N->Info.NombreVertice << "  ";
                N->Info.Estado = 3;
                A = N->Cab;
                while(A){
                    if(A->Ady->Info.Estado == 1){
                        InsertarEnPila(A->Ady);
                        A->Ady->Info.Estado = 2;
                    }
                    A = A->Sig;
                }
            }
        }
        getch();
    }
}
//----------------------------------------------------------------------------------
//----------------------------------------------------------------------------------
//ALGORITMO DE RECORRIDO EN ANCHURA UTILIZANDO UNA COLA
//----------------------------------------------------------------------------------
struct Cola{
    VERTICE *V;
    Cola *Sig;
} *Frente = NULL, *Final=NULL, *Q=NULL, *q=NULL;
void InsertarEnColas(VERTICE *V){
    Cola *Nuevo;
    Nuevo = new Cola;
    Nuevo->V = V;
    Nuevo->Sig = NULL;
    Nuevo->V->Info.d = Infinito; //Se necesitan en Alg. Dijkstra
    Nuevo->V->Predecesor = NULL; // en otro caso no importa
    if(!Q){ //De esta cola no se retiran los elementos
        Q = q = Nuevo;
        Nuevo->V->Info.d = 0; //Se necesitan en Alg. Dijkstra. Es el nodo fuente
    }
    else{
        q->Sig = Nuevo;
        q = Nuevo;
    }
    if(!Frente){
        Frente = Final = Nuevo;
    }
    else{
        Final->Sig = Nuevo;
        Final = Nuevo;
    }
}
//-----------------------------------------------------------------------------------
VERTICE *AtenderFrenteDeCola(char Dijkstra){
    VERTICE *AlFrente;
    Cola  *p;
    AlFrente = Frente->V;
    if(Dijkstra=='N')
        p = Frente;
    Frente = Frente->Sig;
    if(Dijkstra=='N')    //Si es 'S' no se deben borrar los valores en cola
        delete(p);        //frente avanzar  hasta terminar, pero Q apunta al inicio
    return AlFrente;
}
//-----------------------------------------------------------------------------------
int RecorridoEnAnchura(char Dijkstra){
    INFOVERTICE Item;
    VERTICE *Origen, *p, *N;
    ARISTA *A;
    Frente = NULL, Final=NULL, Q=NULL, q=NULL;
    if(CAB){
        cout << "\nDigite la etiqueta del v,rtice de origen: ";
        Item.NombreVertice = getche();
        Origen = EncontrarVerticeDelGrafo(Item);
        if(!Origen){
            cout << "\nV,rtice no Existe en el Grafo\a";
            return 0;
        }
        else{
            p = CAB;
            while(p){
                p->Info.Estado = 1;
                p = p->Sig;
            }
            InsertarEnColas(Origen);
            Origen->Info.Estado = 2;
            cout << endl;
            while(Frente){ //Mientras que la cola no est, vac¡a.
                if(Dijkstra=='S')
                    N = AtenderFrenteDeCola('S');
                else{
                    N = AtenderFrenteDeCola('N');
                    cout << N->Info.NombreVertice << "  ";
                }
                N->Info.Estado = 3;
                A = N->Cab;
                while(A){
                    if(A->Ady->Info.Estado == 1){
                        InsertarEnColas(A->Ady);
                        A->Ady->Info.Estado = 2;
                    }
                    A = A->Sig;
                }
            }
        }
        return 1;
    }
    return 0;
}
//----------------------------------------------------------------------------------
//----------------------------------------------------------------------------------
//ALGORITMO DE DIJKSTRA para el c lculo de trayectorias m¡Nimas entre un
//v, rtice de origen y todos los dem es a los cuales se pueda llegar.
//----------------------------------------------------------------------------------
void AlgoritmoDeDijkstra(){
    Cola *S;//Cola de prioridad ordenada por recorrido en anchura del grafo
                            //Desde el nodo fuente, hasta todos los que se pueda llegar
                            //Por medio de los adyacentes.
    VERTICE *U;
    ARISTA *A;
    if(RecorridoEnAnchura('S')){
        S = Q;
        while(Q){
            U = Q->V; //Se procede a atender el primer nodo de la cola de prioridad
            Q = Q->Sig;
            A = U->Cab;
            while(A){ //Recorre cada una de las aristas del v,rtice U, "relajando"
                if(A->Ady->Info.d > U->Info.d + A->Info.PesoArista){
                    A->Ady->Info.d = U->Info.d + A->Info.PesoArista;
                    A->Ady->Predecesor = U;
                }
                A = A->Sig;
            }
        }
        //listado del conjunto S a continuaci¢n
        clrscr(); cout << "Vertice Predecesor Distancias m s cortas\n";
        while(S){
            cout << S->V->Info.NombreVertice << "         "
                     << S->V->Predecesor->Info.NombreVertice << "         "
                     << setw(8) << S->V->Info.d << endl;
            Q=S;
            S = S->Sig;
            delete(Q);
        }
    }
}
//----------------------------------------------------------------------------------
//FIN ALGORITMO DE DIJKSTRA.
//-----------------------------------------------------------------------------------
//***************************************************************************
//A CONTINUACION CODIGO NECESARIO PARA EL MANEJO DEL GRAFICO DEL GRAFO
//***************************************************************************
void Icono1(int x, int y){
    setcolor(BLUE); outtextxy(x+5, y+6, "Trazar Arista");
}
//-----------------------------------------------------------------------------
void Icono2(int Xm, int Ym){
    setcolor(BLUE); outtextxy(Xm+AnchoVertice+1, Ym+6, "Dibujar Vertice");
    bar(Xm-(AnchoVertice>>1), Ym-(AnchoVertice>>1)-EspacioGrafoYo,
                Xm+(AnchoVertice>>1), Ym+(AnchoVertice>>1)-EspacioGrafoYo );
}
//-----------------------------------------------------------------------------
void Icono3(int x, int y){
 setcolor(BLUE); outtextxy(x+5, y+6, "Dijkstra, etc..");
}
//-----------------------------------------------------------------------------
/************************************************************************** */
/* Funcion  : Ventana                                                       */
/* Objetivo : Dibujar un ReCuadro resaltado o undido.                       */
/************************************************************************** */
void Ventana(int x1, int y1, int x2, int y2,
                                    int ColorArribaIzquierda, int ColorAbajoDerecha,
                                    int ColorFondo)
{    setfillstyle(1, ColorFondo);    bar(x1,y1, x2,y2);
    setlinestyle(SOLID_LINE,0, NORM_WIDTH);
    setcolor(ColorArribaIzquierda);
    line(x1, y1, x1, y2);    line(x1, y1, x2, y1);
    setcolor(ColorAbajoDerecha);
    line(x2, y1, x2, y2);    line(x1, y2, x2, y2);
}
/************************************************************************** */
/* Funcion  : Cursor                                                        */
/* Objetivo : Realiza recuadro, con una cadena centrada en su interior,     */
/*            da a significar una de las opciones de un men£                */
/************************************************************************** */
void Cursor(int x,int y, int pos, int Oprimido)
{ Icono[pos](x, y);
    setlinestyle(SOLID_LINE, 0, NORM_WIDTH);    setcolor(DARKGRAY);
    moveto(x, y); lineto(x+AnchoIcono, y);
    lineto(x+AnchoIcono, y+AltoIcono); lineto(x, y+AltoIcono); lineto(x, y);
    if (!Oprimido) {
        setcolor(BLACK);
        line(x+1, y+1, x+1, y+AltoIcono-1);
        line(x+1, y+1, x+AnchoIcono-1, y+1);
        setcolor(WHITE);
        line(x+AnchoIcono-1, y+1, x+AnchoIcono-1, y+AltoIcono-1);
  ...

Sabes que quizás me sirva, pero es que tengo un grafo dibujado
para el grafo G haga el algoritmo de los caminos mínimos hasta el tercer paso(no se cuales pasos)
Haga el algoritmo de dijkstra para hallar los caminos mínimos entre A y todos los demás vértices del grafo
efectúe el recorrido del grafo mediante búsqueda de profundidad y anchura