Logo elrincondelc.com
curso de programación en c
Foros de programación en C
Inicio :: Código fuente

Valoración
0

Grafos, Algoritmo de Prim & Dijsktra

codigo enviada por: CHELO7380
Este programa trabaja con memoria dinamica usando punteros de direccion de memoria.Le puedes meter n nodos con n enlaces con su costo entero y te da la ruta de menor costo.!!!
Implementa dijkstra y prim usando punteros, direcciones de memoria.
Muestra el arbol de caminos de la ruta mas corta de un nodo a otro y la suma de los costos minimos.
Estructuras de datos, grafos, vertices.
Desarrollado en Dev C++ 4.9.9.2
# include "iostream"
# include <conio.h>
# include <stdio.h>
# include <stdlib.h>

using namespace std;

struct vertice {
       char nod;
       int marca;
       struct vertice *sig;
       struct arco *arc;
};

struct arco {
       struct vertice *ver;
       int marca;
       int suma;
       int clave;
       struct arco *sig;
};


struct vertice *pri, *nue, *aux, *ult, *aux2;
struct arco *nueArc, *auxArc, *arcMen, *auxArc2, *antArc;
char auxNod, auxNod2, ban2, let;
int ban, enlace, ban3, ban4, numVer;

void actualizarCampos ();
void crearVertice();
void enlazarVertices();
void enlazar();
void listarAdyacencia();
void obtenerArcoMenor();
void listarAdyacenciaPrim ();
void sumaCaminos();

void crearVertice () {
     system ("cls");
     if (pri == NULL){
        pri = new vertice;
        cout << "El Grafo no tiene verticesnDigite la letra del Primer Nodo: ";
        cin >> pri->nod;
        pri->marca = 0;
        pri->arc = NULL;
        pri->sig = NULL;
        ult = pri;
        cout << "nNodo registrado correctamente.";
     }
     else {
          cout << "Digite la letra del vertice: ";
          cin >> let;
          do {
              aux = pri;
              ban = 0;
              while (aux != NULL){
                    if (aux->nod == let){
                          ban = 1;
                    }
                    aux = aux->sig;
              }
              if (ban == 1) {
                     cout << "nEsa letra clave ya fue usada, igual que las siguientes:n";
                     aux = pri;
                     while (aux != NULL) {
                           cout << aux->nod << " ";
                           aux = aux->sig;
                     }
                     cout << "nDigita una letra diferente: ";
                     cin >> let;
              }
          }while (ban == 1);
          nue = new vertice;
          nue->nod = let;
          nue->marca = 0;
          nue->sig = NULL;
          nue->arc = NULL;
          ult->sig = nue;
          ult = nue;
          cout << "nNodo registrado correctamente.";
          /*cout << "nAhora que existe un nuevo vertice desea crear enlaces? s/n: "; 
          cin >> ban2;
          while (ban2 == 's'){
                enlazarVertices();                
                cout << "n¿Desea crear otro enlace? s/n: ";
                cin >> ban2;
          } */     
     }     
     
     getch();         
}

void enlazarVertices () {
     system ("cls");
     if (pri != NULL){
        aux = pri;
        while (aux != NULL){
              cout << aux->nod << "n";
              aux = aux->sig;
        }
        cout << "nDigite la letra del nodo al cual desea enlazar: ";
        cin >> auxNod;        
        ban = 0;
        while (ban == 0){
              aux = pri;
              while (aux != NULL && ban == 0){
                   if (aux->nod == auxNod){
                      ban = 1;
                   }
                   aux = aux->sig;
              }
              if (ban == 0){
                 cout << "nEl nodo no existenPor favor digite uno de los listados anteriormente: ";
                 cin >> auxNod;
              }
        }
        cout << "nEstos son los nodos disponibles para hacer el respectivo enlace:n";
        aux = pri;
        aux2 = pri;
        while (aux2->nod != auxNod){
              aux2 = aux2->sig;
        }
        while (aux != NULL){
              if (aux->nod != auxNod){
                  auxArc = aux2->arc;
                  ban4 = 0;
                  while (auxArc != NULL && ban4 == 0){
                        if (aux->nod == auxArc->ver->nod){
                           ban4 = 1;
                        }
                        auxArc = auxArc->sig;
                  }
                  if (ban4 == 0){
                     cout << aux->nod << "n";
                  }
              }
              
              aux = aux->sig;
        }
        cout << "nDigite la letra del nodo al cual desea enlazar el nodo elegido: ";
        cin >> auxNod2;
        ban = 0;
        while (ban == 0){
              aux = pri; 
              while (auxNod2 == auxNod){
                    cout << "nNo se puede hacer ese enlacenDigite otro nodo disponible: ";
                    cin >> auxNod2;
              }
              while (aux != NULL && ban == 0){
                   if (aux->nod == auxNod2){
                      ban = 1;
                   }
                   aux = aux->sig;
              }
              if (ban == 0){
                 cout << "nEl nodo no existenPor favor digite uno de los listados anteriormente: ";
                 cin >> auxNod2;
              }
        }        
        aux = pri;
        while (aux->nod != auxNod){
              aux = aux->sig;
        }        
        auxArc = aux->arc;
        ban3 = 0;
        while (auxArc != NULL && ban3 == 0){
              if (auxArc->ver->nod == auxNod2){
                 ban3 = 1;
              }
              auxArc = auxArc->sig;
        }
        if (ban3 == 0){
           enlazar();
           cout << "nEnlace creado correctamente.";
        }
        else {
             cout << "nEse enlace ya existe. Compruebe el enlace la proxima vez.";
        }
     }
}

void enlazar (){
        aux = pri;
        while (aux->nod != auxNod){
              aux = aux->sig;
        }
        aux2 = pri;
        while (aux2->nod != auxNod2){
              aux2 = aux2->sig;
        }
        if (aux->arc == NULL){
           nueArc = new arco;
           nueArc->ver = aux2;
           cout << "nDigite el valor del enlace: ";
           cin >> enlace;
           while (nueArc->clave < 0){
                 cout << "nEl valor debe ser positivonDigite el valor del enlace: ";
                 cin >> enlace;
           }
           nueArc->clave = enlace;
           nueArc->marca = 0;
           nueArc->suma = 0;
           nueArc->sig = NULL;
           aux->arc = nueArc;
           if (aux2->arc == NULL){
               nueArc = new arco;
               nueArc->ver = aux;           
               nueArc->clave = enlace;
               nueArc->marca = 0;
               nueArc->suma = 0;
               nueArc->sig = NULL;
               aux2->arc = nueArc;
            }
            else {
               nueArc = new arco;
               nueArc->ver = aux;
               nueArc->clave = enlace;
               nueArc->marca = 0;
               nueArc->suma = 0;
               nueArc->sig = NULL;
               auxArc = aux2->arc;
               while (auxArc->sig != NULL){
                     auxArc = auxArc->sig;
               }
               auxArc->sig = nueArc;
            }
        }
        else {
           nueArc = new arco;
           nueArc->ver = aux2;
           cout << "nDigite el valor del enlace: ";
           cin >> enlace;
           while (enlace < 0){
                 cout << "nEl valor debe ser positivonDigite el valor del enlace: ";
                 cin >> enlace;
           }
           nueArc->clave = enlace;  
           nueArc->marca = 0;
           nueArc->suma = 0;         
           nueArc->sig = NULL;
           auxArc = aux->arc;
           while (auxArc->sig != NULL){
                 auxArc = auxArc->sig;
           }
           auxArc->sig = nueArc;
           if (aux2->arc == NULL){
               nueArc = new arco;
               nueArc->ver = aux;           
               nueArc->clave = enlace;
               nueArc->marca = 0;
               nueArc->suma = 0;
               nueArc->sig = NULL;
               aux2->arc = nueArc;
            }
            else {
               nueArc = new arco;
               nueArc->ver = aux;
               nueArc->clave = enlace;
               nueArc->marca = 0;
               nueArc->suma = 0;
               nueArc->sig = NULL;
               auxArc = aux2->arc;
               while (auxArc->sig != NULL){
                     auxArc = auxArc->sig;
               }
               auxArc->sig = nueArc;
            }
        }
}

void obtenerArcoMenor () {
     aux2 = pri;
     arcMen = NULL;
     while (aux2 != NULL){
           if (aux2->marca == 1){
                      auxArc = aux2->arc;
                      while (auxArc != NULL){
                            if (auxArc->marca == 1){
                                  if (arcMen == NULL){
                                         arcMen = auxArc;
                                  }
                                  else{
                                       if (auxArc->clave < arcMen->clave){
                                              arcMen = auxArc;
                                       }
                                  }
                            }
                            auxArc = auxArc->sig;
                      }
           }
           aux2 = aux2->sig;
     }
     arcMen->marca = 3;
     arcMen->ver->marca = 1;
}

void obtenerSumaMenor () {
     aux2 = pri;
     arcMen = NULL;
     while (aux2 != NULL){
           if (aux2->marca == 1){
                      auxArc = aux2->arc;
                      while (auxArc != NULL){
                            if (auxArc->marca == 1){
                                  if (arcMen == NULL){
                                         arcMen = auxArc;
                                  }
                                  else{
                                       if (auxArc->suma < arcMen->suma){
                                              arcMen = auxArc;
                                       }
                                  }
                            }
                            auxArc = auxArc->sig;
                      }
           }
           aux2 = aux2->sig;
     }
     arcMen->marca = 3;
     arcMen->ver->marca = 1;
     auxArc = arcMen->ver->arc;
     while (auxArc != NULL){
           auxArc->suma = arcMen->suma + auxArc->clave;
           auxArc = auxArc->sig;
     }
}

void paso2 (){
            obtenerArcoMenor();
            cout << "nEl arco menor es: "<< arcMen->ver->nod << " vale: " << arcMen->clave;
            getch();
            aux = arcMen->ver;
            auxArc = aux->arc;
            while (auxArc != NULL){
                  if (auxArc->ver->marca == 0){
                         aux2 = pri;
                         while (aux2 != NULL){
                               if (aux2 != aux && aux2->marca == 1){
                                     auxArc2 = aux2->arc;
                                     while (auxArc2 != NULL){
                                           if (auxArc->ver->nod == auxArc2->ver->nod){
                                                  if (auxArc->clave < auxArc2->clave){
                                                         auxArc2->marca = 2;
                                                         auxArc->marca = 1;
                                                  }
                                                  else {
                                                       auxArc->marca = 2;
                                                       auxArc2->marca = 1;
                                                  }
                                           }
                                           auxArc2 = auxArc2->sig;
                                     }
                               }
                               aux2 = aux2->sig;
                         }
                         if (auxArc->marca == 0){
                                auxArc->marca = 1;
                         }
                  }
                  else {
                       auxArc->marca = 2;
                  }
                  auxArc = auxArc->sig;
            }
}


void paso2Dijkstra () {
            obtenerSumaMenor();
            cout << "nLa sumatoria hasta el arco " << arcMen->ver->nod << " es: "<< arcMen->suma;
            getch();
            aux = arcMen->ver;
            auxArc = aux->arc;
            while (auxArc != NULL){
                  if (auxArc->ver->marca == 0){
                         aux2 = pri;
                         while (aux2 != NULL){
                               if (aux2 != aux && aux2->marca == 1){
                                     auxArc2 = aux2->arc;
                                     while (auxArc2 != NULL){
                                           if (auxArc->ver->nod == auxArc2->ver->nod){
                                                  if (auxArc->suma  < auxArc2->suma){
                                                         auxArc2->marca = 2;
                                                         auxArc->marca = 1;
                                                  }
                                                  else {
                                                       auxArc->marca = 2;
                                                       auxArc2->marca = 1;
                                                  }
                                           }
                                           auxArc2 = auxArc2->sig;
                                     }
                               }
                               aux2 = aux2->sig;
                         }
                         if (auxArc->marca == 0){
                                auxArc->marca = 1;
                                auxArc->suma = arcMen->suma + auxArc->clave;
                         }
                  }
                  else {
                       auxArc->marca = 2;
                  }
                  auxArc = auxArc->sig;
            }
}

void algoritmoPrim () {
     system("cls");
     if (pri != NULL){
            actualizarCampos();
            cout << "Digite el vertice inicial: ";
            cin >> auxNod;
            ban = 0;
            while (ban == 0){
                  aux = pri;
                  while (aux != NULL){
                        if (aux->nod == auxNod){
                               ban = 1;
                        }
                        aux = aux->sig;
                  }
                  if (ban == 0){
                         cout << "nNo existe un nodo con esa letra.";
                         aux = pri;
                         cout << "n---Lista de Nodos---n";
                         while (aux != NULL){
                               cout << aux->nod << " ";
                               aux = aux->sig;
                         }
                         cout << "nDigite uno de los anteriores nodos: ";
                         cin >> auxNod;
                  }
            }
            aux = pri;
            while (aux->nod != auxNod){
                  aux = aux->sig;
            }
            aux->marca = 1;
            auxArc = aux->arc;
            while (auxArc != NULL){
                  auxArc->marca = 1;
                  auxArc = auxArc->sig;
            }
            cout << "nSe han marcado todos los arcos para el vertice elegido.";
            ban2 = 1;
            while (ban2 == 1){
                  paso2();
                  ban2 = 0;
                  aux = pri;
                  while (aux != NULL){
                        if (aux->marca == 0){
                               ban2 = 1;
                        }
                        aux = aux->sig;
                  }
            }
            listarAdyacenciaPrim ();
            sumaCaminos();
     }
     getch();
}

void listarAdyacencia () {
     system ("cls");
     if (pri != NULL){
        aux = pri;
        cout << "---Lista de Adyacencia---n";
        while (aux != NULL){
              auxArc = aux->arc;
              cout << "n|n" << aux->nod << "->";
              while (auxArc != NULL){
                    cout << auxArc->ver->nod << " ";
                    auxArc = auxArc->sig;
              }
              aux = aux->sig;
        }
        getch();
     }
}

void sumaCaminos () {
     aux = pri;
     int suma = 0;
     while (aux != NULL){
           auxArc = aux->arc;
           while (auxArc != NULL){
                 if (auxArc->marca == 3){
                        suma = suma + auxArc->clave;
                 }
                 auxArc = auxArc->sig;
           }
           aux = aux->sig;
     }
     cout << "nLa suma de los caminos es: " << suma;
}

void listarAdyacenciaPrim () {
     if (pri != NULL){
        aux = pri;
        cout << "n---Lista de Adyacencia---n";
        while (aux != NULL){
              auxArc = aux->arc;
              cout << "n|n" << aux->nod << "->";
              while (auxArc != NULL){
                    if (auxArc->marca == 3)
                    cout << auxArc->ver->nod << " ";
                    auxArc = auxArc->sig;
              }
              aux = aux->sig;
        }
     }
}


void liberarMemoria () {
     if (pri != NULL){
        aux = pri;
        while (aux != NULL){
              auxArc = aux->arc;
              while (auxArc != NULL){
                    aux->arc = aux->arc->sig;
                    delete auxArc;
                    auxArc = aux->arc;
              }
              pri = pri->sig;
              delete aux;
              aux = pri;
        }
     }
     cout << "Memoria Libre";
     getch();
}


void algoritmoDijkstra () {
     system("cls");
     if (pri != NULL){
            actualizarCampos ();
            cout << "Digite el vertice inicial: ";
            cin >> auxNod;
            ban = 0;
            while (ban == 0){
                  aux = pri;
                  while (aux != NULL){
                        if (aux->nod == auxNod){
                 &nb
ayudame con el codigo enviamelo a Bryan.rigailc@fcmf.ug.edu.ec o al Bryan_rigail@hotmail.com
(rigail1993 2013-01-02 23:01:35)
si me podes mandar el codigo completo en jrkurepa@hotmail.com porfa. lo que tengas de grafos..
(kurepa02 2013-05-31 13:39:09)
Este me sirve!!! me lo podrias enviar? juan.jade@yahoo.com.mx Gracias.
(juan.jade 2013-06-05 18:01:52)
hola este codigo me sirve me lo podrias enviar a: ciberramon_96@hotmail.com ó a: ramon.orellana02@inacapmail.com gracias :D
(MONRA 2013-06-20 17:20:46)
Hola Necesito por favor el código, me sirve mucho. Me lo podrías mandar? manuel_cm@live.cl gracias.
(manuel00 2013-06-21 15:28:37)
Me interesa saber sobre este código, me gustaría que me lo envíes a mi correo electrónico cgaray2002@hotmail.com porfavor Gracias!!!
(cgaray 2013-08-25 17:52:17)
Hola buenas noches, me gustaria que me enviaras el código al siguiente correo ing_0rduna_9102@hotmail.com porfavor, gracias!!
(NHOO 2013-11-07 23:28:57)
Yo también necesito el codigo por favor, enviamelo a Raudony@outlook.com te lo agradecería mucho!
(Raudony 2013-11-10 05:58:48)
A mi me podrían enviar el código por favor, mi correo es zaigo_naye@hotmail.es gracias!
(nayex 2013-11-26 14:25:09)
que tal me podrian pasar este codigo porfavor me ayudarian mucho es urgente de esto depende si paso o no mi parcial T.T a : abl.1994@hotmail.com (todo en minusculas)
(zxero 2014-07-01 21:51:15)
Hola, me gustaría que me envies el codigo completo a mi correo cgaray2002@hotmail.com porfavor me interesa saber del mismo
(cgaray 2014-07-02 06:54:25)

Para enviar comentarios debes estar registrado.

(c) ElRincondelC.com

Un proyecto de Urlan Heat : proyectos de Internet y soporte para el comercio electrónico.