algoritmos de grafos - facyt - universidad de carabobo
DESCRIPTION
Ejemplos Algoritmos de grafos mas comunes. Dijkstra (Camino Optimo) Camino HamiltonianoGrafo BicoloreableOrden de Precedencia de un Vertice Eliminar un Vertice Camino mas largo desde unVertice V ( Cualquier Destino )TRANSCRIPT
-
UniversidaddeCaraboboFacultaddeCienciasyTecnologia
DepartamentodeComputacion
AlgoritmosdeGrafos(Ejemplos)
FelixGonzalezJulio2015
-
Dijkstra(CaminoOptimo)RecorridoenBFSguardandolopredecesoresdecadaverticeyelpesodel
caminocaminorecorridoparallegarhastael.Elalgnosdarelcaminooptimo desdeunverticedado(O)atodolodems,estosseconseguiranconlaayuda del vector de predecesores. Este proc retornara la lista Sol con el mejor caminodeOaD.ProcDijkstra(Grafo:gVertice:o,dRefLista:Sol)var
Entetro:iArreglo[1...n]deLogico:Visitado//n=g.OrdenArreglo[1...n]deVertice:PredArreglo[1...n]deReal:PesoCola:CLista:LVertice:u,v
inicioparai1hastag.Orden()hacer
Visitado[i]falsofparaparai1hastag.Orden()hacer
Pred[i]0//Inicializarenunvalorinvalidofparaparai1hastag.Orden()hacer
Peso[i]0//InicializarenunvalorinvalidofparaVisitado[o]verdaderoC.Encolar(o)//RecorridoBFS,sepuedemejoraraadimosalacondicindemientrasu
!=d,asiterminaraencuantoprocesealdestino.mientras(C.EsVacia())hacer
uC.Frente()C.Desencolar()Lg.Sucesores(u)
-
mientras(L.EsVacia())hacervL.Consultar(1)L.Eliminar(1)si(Visitado[v])entonces
Visitado[v]verdaderoPred[v]uPeso[v]Peso[u]+g.PesoArco(u,v)C.Encolar(v)
sino//Siyafuevisitado,peroestecaminoesmejor,//cambiamosporelnuevopredyelnuevopesosi(Peso[u]+g.PesoArco(u,v)
-
CaminoHamiltoniano
SedefinecomoCaminoHamiltonianoauncaminocualquiera,quepasapor todoslosverticesdeungrafo,unasolavez(sincircuitors).Puedeempezar desde cualquier vertice yterminarencualquierotro.EsquemaBacktrackingde unasolucion.procCamHam(Grafo:gVertice:vRefLista:SolLogico:enc)var
Lista:sucVertice:vact
iniciosucg.sucesores(v)mientras(suc.EsVacia()enc)hacer
vactsuc.Consultar(1)suc.Eliminar(1)si(Sol.Esta(vact))entonces
Sol.Insertar(vact,Sol.Longitud()+1)si(Sol.Longitud()=g.nVertices())entonces//Bastacon
encverdadero//comprobarlongitudporqueenSolsino //nohayverticesrepetidos
CamHam(g,vact,Sol,enc)fsi
fsisi(enc)entonces
Sol.Eliminar(visitados.Longitud()+1)fsi
fmientrasfproc
-
LlamamosalprocCamHam()desdecadavertice,hastaencontrarunasolucin.procCaminoHamiltoniano(Grafo:gVertice:vLista:camham)var
Logico:flagLista:vertices
inicioencfalsosuc.construir()verticesg.Vertices()mientras(vertices.EsVacia()enc)hacer
//Elcaminoempiezaenelverticeorigencamham.Insertar(vertices.Consultar(1),1)CamHam(g,vertices.Consultar(1),camham,enc)vertices.Eliminar(1)//Sinoencontrolasoleliminoelverticeorigen//queinserteantesdeCamHam()si(enc)entonces
camham.Vaciar()fsi
fmientrasffunc
-
GrafoBicoloreable
Un grafo es bicoloreable si se puede asignar colores (elegidos de una paletadedoscolores)acadavrticedemaneratalquedosvrticesadyacentes notenganelmismocolor.Esdecirelgrafosepuedecolorearusandosolodos colores.
Observaciones:1.Elgrafonotienebucles.2.Elgrafoesnodirigido.3.Elgrafoesconexo.4.Noutiliceapuntadoresensusolucin.5.ElalgoritmodebeseralosumoO(V+E).funcEsBicoloreable(Grafo:g):Lgicovar
Logico:flagEntetro:iArreglo[1...n]deCadenas:Color//n=g.OrdenCola:CLista:L,VertVertice:u,v
inicioparai1hastag.Orden()hacer
Color[i]"blanco"//Elordendeungrafoeslacantidadde //vertices
fparaVertg.Vertices()Color[Vert.Consultar(1)]"gris"C.Encolar(Vert.Consultar(1))flagverdadero
-
// Como el grafo es conexo podemos empezar a recorrerlo desde //cualquier vertice, por ejemplo el primero de la lista, y //pintarlodecualquiercoloreirpintandosussucesores
//RecorridoBFSmientras(C.EsVacia()flag)hacer
uC.Frente()C.Desencolar()Lg.Sucesores(u)mientras(L.EsVacia())hacer
vL.Consultar(1)L.Eliminar(1)si(Color[v]"blanco")entonces//Sinoannoestpintado,lopintamosdeuncolor//diferentealU(alverticeactual)yloencolamos
si(Color[u]="gris")entoncesColor[v]"negro"
sinoColor[v]"gris"
fsiC.Encolar(v)
sino//Siyaestapintado,debeteneruncolordiferenteal//verticeactual,sisondelmismocolorentoncesse//necesitanmasdedoscoloresyyanoesbicoloreable
si(Color[v]=Color[u])entoncesflagfalso
fsifsi
fmientrasfmientras
retornar(flag)
ffunc
-
SolconApuntadoresydeotramanerafuncGrafo::EsBicoloreable():Lgicovar
Logico:flagEntetro:colAdy,iArreglo[1...n]deEnteros:Color//n=instancia.n(cantidaddevertices)ApuntadoraNodoA:Vact,VelimApuntadoraNodoV:Aact,Aelim
inicioparai1hastainstancia.nhacer
Color[i]0//SincolorfparaflagverdaderoVactinstancia.gmientras(flagVact!=nulo)hacer
si(Color[Vact.ObtInfo()]=0)entoncesColor[Vact.ObtInfo()1//Sinotienecolor,lopintode1//Comoelgrafoesnodirigido,sielnohasidopintadoes//porquesusadyacentestampoco,poresoningunodesus//adyacentesdeberiatenercolor1(ni2),porqueaunno//hansidopintados.
fsisi(Color[Vact.ObtInfo()]=1)entonces
colAdy2//Sielverticeactualesdecolor1losadyacentesdeben//serdecolor2
sinocolAdy1//Sinoalrevez
fsiAactVact.pri
-
//Ahorasepintanlosadyacentesmientras(flagAact!=nulo)hacer
si(Color[Aact.ObtVertice().ObtInfo()]=0)entoncesColor[Aact.ObtVertice().ObtInfo()]colAdy//Sinotienecolor,lopintodelquedebellevar
sinoflagColor[Aact.ObtVertice().ObtInfo()]=colAdy//Ysitienecompruebaqueseaelquedebellevar
fsiAactAact.ObtSig()
fmientrasVactVact.ObtSig()
fmientrasretornar(flag)
ffunc
-
OrdendePrecedenciadeunVertice
LongituddelcaminomaslargodesdeunafuentehastaelverticeV.Buscamosel caminomaslargodesdecadafuentealverticeVyguardamoslalongituddelmas largo.funcordenPrecedencial(Grafo:g,Vertice:v):enterovar
Entero:nlargoLista:fuentes,Sol,caminoAct
inicionlargo0fuentesg.fuentes()Sol.construir()caminoAct.construir()mientras(fuentes.EsVacia())hacer
Sol.Insertar(fuentes(1),1)ordenPrecedencia(g,fuentes(1),v,Sol,caminoAct)si(Sol.Longitud()>nlargo)entonces
nlargoSol.Longitud()fsiSol.Vaciar()fuentes.Eliminar(1)
fmientrasretornar(nlargo)
ffuncprocCamLargo(Grafo:gVertice:o,dRefLista:SolLista:caminoAct)var
Lista:sucVertice:vact
inicio
-
suc.construit()sucg.sucesores(o)mientras(suc.EsVacia())hacer
vactsuc.Consultar(1)suc.Eliminar(1)si(caminoAct.Esta(vact))entonces
caminoAct.Insertar(vact,caminoAct.Longitud()+1)si(vact=d)entonces
si(caminoAct.Longitud()>Sol.Logitud())entoncesSolCaminoAct
fsisino
CamLargo(g,vact,Sol,caminoAct)fsicaminoAct.Eliminar(caminoAct.Longitud()+1)
fsifmientras
fproc
-
EliminarunVerticeSedebeeliminarelnododelvertice,sulistadeadyacencia(nodos
arcosquesalendel)ytodoslosarcosdequeapuntanal(queestnenlaslistasdeadyacenciadelosdemasvertices).procGrafo::Grado(Vertice:v)var
ApuntadoraNodoA:Vact,VelimApuntadoraNodoV:Aact,Aelim
inicioVactinstancia.gsi(Vact.obtInfo()=v) //Sielverticevestaenlaprimera
VelimVact //posicionVactVact.ObtSig()Liberar(Velim)instancia.ninstancia.n1
fsimientras(Vact=nulo)hacer
AactVact.obtPri()si(Vact.obtInfo()=v)entonces
mientras(Aactnulo)hacerAelimAactAactAact.ObtSig()Liberar(Aelim)instancia.ainstancia.a1
fmientrasVelimVactVactVact.ObtSig() //SiguienteverticeLiberar(Velim)instancia.ninstancia.n1
sinosi(Aact!=nulo)entonces //Sielverticeacttiene
Aelimnulo //arcos
-
si(Aact.obtVert().obtInfo()=v)//SielarcoqueVact.priAact.ObtSig() //apuntaavesAelimAact //elprimero
fsimientras(Aact!=nuloAelim=nuloAact.Obtsig().obtVert()!=nulo)hacer si(Aact.Obtsig().obtVert().obtInfo()=e)entonces
AelimAact.ObtSig()Aact.sigAelim.ObtSig()fsi
fmientrassi(Aelim!=nulo)entonces
Liberar(Aelim)instancia.ainstancia.a1
fsifsiVactVact.ObtSig()//Siguientevertice
fsifmientras
fproc
-
Caminomaslargodesdeun
VerticeV(CualquierDestino)
Dado un vertice V encontrar el camino mas largo sin ciclos (sin circuitors)partiendoconl.Esigualqueencontrarelcaminomaslargodeun verticeVaunverticeUperoenestecasoU(eldestino)noseespecifica, elcaminopuedeterminarencualquiervertice.procCamLargoCD(Grafo:gVertice:vRefLista:SolLista:caminoAct)var
Lista:sucVertice:vact
iniciosucg.sucesores(v)mientras(suc.EsVacia())hacer
vactsuc.Consultar(1)suc.Eliminar(1)si(caminoAct.Esta(vact))entonces
caminoAct.Insertar(vact,caminoAct.Longitud()+1)si(EsSol(g,act,caminoAct))entonces//EsSolfuncin
magicasi(caminoAct.Longitud()>Sol.Logitud())entonces
SolCaminoActfsi
sinoCamLargoCD(g,vact,Sol,caminoAct)
fsicaminoAct.Eliminar(visitados.Longitud()+1)
fsifmientras
fproc
-
EsSolucionsitodoslossucesoreselverticeactualyafueronvisitadososinotienesucesores.Sialmenosunodesussucesoresnohasidovisitado,entoncesnoEsSolucionycontinuamosconstruyendoelcamino.funcEsSol(Grafo:gVertice:vLista:caminoAct):Lgicovar
Logico:flagLista:suc
inicioflagverdaderosucg.sucesores(v)mientras(flagsuc.EsVacia())hacer
flagcaminoAct.Esta(suc.Consultar(1))//SiunsucesordeVnoestencaminoAct(retornafalso)esporquenohasidovisitadosuc.Eliminar(1)
fmientrasretornar(flag)
ffunc