Ir ao conteúdo
  • Cadastre-se
Marcos Dario

Grafo desconexo nao orientado

Recommended Posts

Preciso fazer um programa em java para ller um arquivo de vertices, (tipo 1 2 3 4 5 6 7 8 ) , arestas (tipo 1 3, 2 3, 5 6, 5 7) e dar como resposta ,

1 2 3 

4

5  6 7

8

consegui abrir e ler o arquivo mas na hora de separar os pares só estou conseguindo ler as duplas uma vez, aí pode haver falhas alguem tem uma dica de algoritmo para resolver esse problema? o programa deve ler qualquer arquivo co mais ou menos numeros.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Grafos são complicados ... e a forma que você explicou foi mais ainda ...

Pelo que entendi você deveria receber um arquivo que tem a lista de Vertices e suas arestas ... mas o maior problema: você não postou o que você já fez ... 
 

Em todos os casos que utilizei Grafos, eu recebo algo como

Citação

VerticeOrigem, VerticeDestino, PesoAresta



Assim você consegue montar o Grafo sabendo que Vertice liga com quem ...

Compartilhar este post


Link para o post
Compartilhar em outros sites

exatamente, bastante confuso, rss. bom vamos lá, os grafos  são desconexos e sem peso ou direção, apenas devemos abrir o arquivo dizer quantos grafos tem e mostrá-los. 

 tipo assim. entrada 

1 2 3 4 5 6 7 8 9

1 2 

2 4

4 5

5 6 

8 9

9 5 

a resposta deve ser

 

  3   grafos

1 2 4 5 6 8 9

3

7

bom e o que eu fiz foi pouco apenas fiz a leitura do arquivo com BufferedReader li a primeira linha separadamente e coloquei todo o resto dentro de um arraylist, agora empaquei como uma mula. 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Acho que entendi ... a primeira linha mostra todos os Vertices ... as linhas subjacentes são as descrições das arestas ... como objetivo é apenas mostrar quais são os vértices que não estão sendo conectados no grafo, acredito que você pode fazer assim:

 

1- Coloca todos os vértices num List 

2- Pra cada aresta, haverá dois vértices ... apenas remova esses vertices da lista e inclua em uma outra lista de 'vértices utilizados' (Claro, se eles ainda estiverem na lista inicial, senão basta ignorar)

3- após remover todos os vértices, você tem a lista de todos que foram removidos e o que restou na lista inicial são os vértices que não tem conexão ... com isso você pode exibi-los tranquilamente ... 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×