Jump to content

Algoritmos de grafos


senito

Recommended Posts

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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ê  ?

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Link to comment
Share on other sites

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  😄

Link to comment
Share on other sites

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

Link to comment
Share on other sites

  • 2 weeks later...

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 😁

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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  😁

Link to comment
Share on other sites

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....

Link to comment
Share on other sites

  • 2 weeks later...

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

Link to comment
Share on other sites

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).

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.