Algoritmos de grafos

[senito]

Boas,

vou ter um trabalho prático para a uma cadeira (estruturas de infomação) em que terei que trabalhar com grafos e implementar alguns algoritmos.

O trabalho é o seguinte:

"O presente trabalho tem por objectivo adicionar à classe template representativa de

grafos, através de lista de adjacências, os seguintes algoritmos:

  •  Árvore de Expansão Mínima – implementar o algoritmo de Prim ou o

      algoritmo de Kruskal para determinar uma árvore de expansão mínima de um

      grafo não dirigido, pesado, conexo;

  •  Fluxo Máximo numa Rede de Transporte – implementar o Algoritmo Ford-

      Fulkerson para determinar qual o fluxo máximo possível num grafo de fluxo;

  •  Circuito de Euler – verificar se um grafo não dirigido tem um circuito de Euler,

      e em caso afirmativo, determiná-lo;

  •  Eulerização de um Grafo – implementar um algoritmo que transforma um

      grafo não Euleriano num grafo Euleriano.

"

Será que alguém tem o código-fonte desses algoritmos que me pudesse arranjar?

É que assim poupava algum tempo de pesquisa no google sobre o que cada algoritmos faz. Como trabalho não tenho muito tempo para estar à procura.

Se alguém me pudesse ajudar agardecia imenso.

Cumps

[saramgsilva]

boas, eu talvez te arranje, porque isso devia estar a dar a Optimização Combinatória ( desisti da cadeira... )  mas vou ver se pego os pdf e te envio!!!!! que tem os algoritmos como tu queres, decerteza....

em relação aos grafos, são árvores... talvez isto que ajude

http://wwwp.fc.unesp.br/~erich/ed.html

tem uns tutis sobre arvores em C, mas acho que facilmente percebes e aplicas a linguagem que pretendes!!

tofas

[senito]

obrigado pela mensagem.

Qd chegar a casa já vou dar uma vista de olhos ao link q me enviaste.

[mogers]

boas, eu talvez te arranje, porque isso devia estar a dar a Optimização Combinatória ( desisti da cadeira... )  mas vou ver se pego os pdf e te envio!!!!! que tem os algoritmos como tu queres, decerteza....

em relação aos grafos, são árvores... talvez isto que ajude

http://wwwp.fc.unesp.br/~erich/ed.html

tem uns tutis sobre arvores em C, mas acho que facilmente percebes e aplicas a linguagem que pretendes!!

tofas

tofas, os grafos são a mesma coisa k árvores? Eu comecei agr a dar grafos (só tive 1 aula ainda)  na faculdade... acho que o meu prof disse que uma árvore é um tipo especial de grafo... já não me lembro porquê  ?

[saramgsilva]

Em 21/05/2006 às 19:18, mogers disse:

se leres a definação de grafo e de árvore ves que

trofas, os grafos são a mesma coisa k árvores? Eu comecei agr a dar grafos (só tive 1 aula ainda)  na faculdade... acho que o meu prof disse que uma árvore é um tipo especial de grafo... já não me lembro porquê  ?

Não sou a trofas mas sim tofas...

em relação a pergunta que fizeste irá perceber melhor....como estás a falar nisso nas aulas....

mas deixo-te aqui uns links sobre isso  😄

Teoria_dos_grafos

Grafos

já agora senito  vê esses link's pode-te dar jeito  😄

[senito]

Não sou a trofas mas sim tofas...

Sorry, foi um pequeno erro de escrita. É o que faz escrever sem olhar pro teclado e dps n verificar o q se escreve. hehe

Obrigado pelas dicas.

[saramgsilva]

Em 22/05/2006 às 11:57, senito disse:

Sorry, foi um pequeno erro de escrita. É o que faz escrever sem olhar pro teclado e dps n verificar o q se escreve. hehe

Obrigado pelas dicas.

sim eu sei.... o  mogers já me mandou mp  😄 ... não problema...só chamei atenção para corrigir ...

bom trabalho

[Rui Carlos]

a wikipedia é um bom local para procurar informações.

tem a descrição de alguns algoritmos que referiste com esquemas/desenhos que explicam como funcionam.

[brunomoniz]

senito... tamos a fazer o mesmo trabalho! já adiantas-te alguma coisa?

[senito]

Infelizmente ainda n tive tempo pra começar. Espero começar no sábado.

Já tens alguma coisa adiantada?

[brunomoniz]

tenho a parte do ficheiro pronta e testada.

tenho alguns métodos de euler mas ainda não está tudo.

tou a tentar fazer kruskal mas é complicado. prim é mais facil...

nao toquei em ford-fulkerson...

[rAtOOn]

Viva.

Pareçe-me que sou outro a fazer esta cadeira de ESTIN....

É ppl do DEI-ISEP?

Tenho que entregar ate dia 11 o trabalho, e ainda estou a tentar implementar o Kruskal (com uma stack) ou o Prim (com vectores), ainda não me decidi, talvez o que funcionar 1º

Quanto ao resto apenas reuni informacao e algoritmos em pseudo-codigo....

se quiseres trocar informações....APITEM 😁

[brunomoniz]

DEI-ISEP rula

estou a tentar implementar uma estrutura local para guardar: origem ramo, destino ramo, peso.

Isto para ordenar os ramos para calcular a árvore de expansão minima (kruskal)

[nurvo0]

Também estou a fazer esse trabalho.

Já implementei o algoritmo Prim...estou a tentar fazer os outros e não estou a conseguir.

Eu queria arranjar os outros algoritmos sem ser aqueles que já estão disponibilizados na disciplina.Se alguém encontrar algum jeitoso, agradecia!

PS: A minha professora disse que o algoritmo Prim é mais facil que o Kruskal.

[rAtOOn]

brunomoniz:

poix, chegei exactamente aí para poder utilizar uma Queue (Vorigem,Vdestino, Peso)

Quanto ao Prim, embora tb me tenham dito que seria mais facil, resulta-me num vector (pai) que nao me faz sentido algum, por isso estou a tentar o Kruskal

// ARVORE DE EXPANSAO MINIMA -> ALGORIMO DE KRUSKAL

template<class TV,class TR>
ListAdjGrafo<TV,TR> ListAdjGrafo<TV,TR>::ArvExpansaoMinK()
{
ListAdjGrafo<TV,TR> a;
Vertice<TV,TR> *v = graf;
Ramo<TV,TR> *r;

Queue<Ramo<TV,TR>*> filaP;


for (int i = 0; i < nvertices; i++)
{
	// Constroi os vertices da nova arvore
	a.juntar_vertice(v->vconteudo);

	r = v->apramo;
	while(r != NULL)
	{
		// Construir fila prioridade crescente de peso com os ramos de E
		// Peso: r->rconteudo 
		// Aqui devia-se acrescentar a filaP, juntamente com r, o v
		acrescentaC(filaP, r);
		r = r->apr;
	}
	v = v->apvertice;
}

cout << filaP << endl;
// Resto do Algoritmo...

return a;
}

Aqui acrescenta apenas os ramos por ordem crescente, preciso de uma struct tipo

typedef struct {
    Vertice<TV,TR> vFila;
    Ramo<TV,TR> rFila;
} sFila

sugestões são bem apreciadas....

já pensei alterar para uma matriz de adjacencias, manipular com os algoritmos, e depois construir a nova arvore.

pelo menos seria mais facil para o ford-fulkerson

edit : Peço que usem o GeSHi. tofas  😁

[rAtOOn]

Já completei a Eulerização de um grafo (partido do principio que já e conexo, ainda nao testei uma situacao em que ele nao seja conexo)

Quanto ao Circuito de Euler, estou a testar uma abordagem recursiva, quando completar, coloco aqui.

Abraço.

[senito]

A mim falta-me completar esse algoritmo. Espero ter isso pronto hj. pra dps no fim-de-semana fazer o grafo e a análise de complexidade.

Abraço.

[rAtOOn]

A "Eulerização" do grafo ja está.

Bem como o metodo isEuler()

Finalmente o que falta: O caminho de Euler:

template<class TV,class TR>
void ListAdjGrafo<TV,TR>::CircuitoEuler(const TV & vInicio)
{
//ListAdjGrafo<TV,TR> *caminho;
TV vFim;
Vertice<TV,TR> * tempv = encontrar_vertice(vInicio);
Ramo<TV,TR> * t = tempv->apramo;

while(GrauVertice(tempv) > 0)
{
	vFim = t->apv->vconteudo;
	cout << "Inicio: " << vInicio << "Fim: " << vFim << endl;
	retirar_ramo(tempv, t);
	CircuitoEuler(vFim);
}
}

Era suposto funcionar, mas ja vi que quando existe um vertice de grau impar (unico no grafo) ele cria um ramo circular vOrigem = vDestino

falta implementar este teste no algoritmo (acho eu)...

Ja agora falta tambem assegurar que o vertice que inicia o calculo do caminho, é também o último! Isto já vai aumentar a complexidade....

Sugestões/Comentários são apreciados....

[saramgsilva]

para vos ajudar.... talves isto dê jeito  😉

no topico: http://www.portugal-a-programar.pt/index.php?showtopic=3158

Em 19/06/2006 às 00:21, Rui Carlos disse:

eu tenho uma biblioteca de funções para manipulação de árvores binárias, mas já é um pouco mais complexa do que aquilo que precisas (são árvores binárias de procura equilibradas)...

de qualquer forma podes fazer o download aqui

mais uns link's:

http://wiki.di.uminho.pt/wiki/pub/Education/MetodosProgramacaoII/f1.pdf

http://wiki.di.uminho.pt/wiki/pub/Education/MetodosProgramacaoII/TP.tgz

http://wiki.di.uminho.pt/wiki/pub/Education/MetodosProgramacaoII/slides_tp.pdf

se tiveres alguma dúvida concreta sobre o assunto é só dizeres

EDIT

quase me esquecia da wikipedia...

http://pt.wikipedia.org/wiki/%C3%81rvore_de_busca_bin%C3%A1ria

[rAtOOn]

A versão final ficou como se segue (Algoritmo recursivo c/backtracking)

template<class TV,class TR>
bool ListAdjGrafo<TV,TR>::CircuitoEuler(const TV & vInicio, const TV & vParagem, Stack<Ramo<TV,TR> *> &stR)
{
TV vFim;
Vertice<TV,TR> *v = encontrar_vertice(vInicio);
Ramo<TV,TR> *r = v->apramo;

// Criterio de Paragem
if (EulerVisitouTodosRamos(stR))	// Se nao tem ramos repetidos e se visitou todos
{
	cout << "Caminho de Euler:" << endl << vParagem;
	while(!stR.vazia())
	{
		stR.pop(r);
		cout << "-" << r->apv->vconteudo;
	}
	cout << endl << endl;
	return true;
}

while (r != NULL)
{
	if (! EulerVisitouRamo(stR, r))
		stR.push(r);
		vFim = r->apv->vconteudo;
		if (CircuitoEuler(vFim, vParagem, stR))
			return true;

		stR.pop(r);			// Backtracking
	}
	r = r->apr;
}
return false;
}

Ficou a funcionar sem estourar a stack ?

Nem precisa de ser um grafo eureliano, se não existir caminho, devolve False!

Leva como parametro por exemplo vertice inicio 1 e vertice final 1 (condição de caminho de Euler: acaba no vertice que começa) e uma stack para guardar o caminho que vai encontrando.

Optei por imprimir o caminho dentro, caso não o faça, leva uma stack com os ramos (atenção depois ao acesso aos membros de dados privados).