• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Jeust

Algoritmo de Tarjan - a maldição continua

5 mensagens neste tópico

Eu já percebi o algoritmo de Tarjan para componentes fortemente conexas (scc), mas tenho uma dúvido quanto às conclusões que posso tirar sobre ele.

Aplicando o algoritmo a um vertice, v0, e com ele deduzindo o grupo em que se insere v0 (se ele houver), mas também há nós que não se inserem no dito grupo... Podemos concluir alguma coisa acerca desses nós orfãos, para além que não pertencem ao grupo de componentes fortemente conexas de v0?

Estarão eles limitados à sua orfandade, ou poderão fazer eles parte de outros grupos?

obrigado pela atenção, e desculpem a lógica retorcida do problema... :$

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Parece-me que queres resolver este problema.

Com um algoritmo que calcule as componentes fortemente conexas de um grafo, obtens uma lista de componentes. Cada vértice pertence a apenas uma das componentes, mesmo que seja uma componente de tamanho 1 (com apenas esse vértice).

Eu gostava de ter colocado um algoritmo para calcular as componentes fortemente conexas no meu artigo da revista programar, mas não tive tempo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Obrigada :D

Yap é esse mesmo o problema... mas eu estou a aplica-lo a java :P

E caso não seja indiscrição, que método é que gostarias de pôr? O dos dois dfs's?

abraços

p.s. - heyyyy a invadir o meu tópico  :rant_01:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu não sei como o algoritmo de Tarjan funciona (embora tenha uma ideia). Eu costumo usar o "método dos dois dfs". Acho que é simples de perceber como funciona e simples de implementar de cabeça sem ser preciso consultar os apontamentos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora