Programa de grafos

Programação Java
#1

Olá,

Ainda não tive a disciplina de grafos na minha faculdade, e to um pouco perdida pra fazer um algoritmo aqui.

Preciso fazer um programa em java que receba como entrada o número de nós e o número de ligações entre esses nós.
Ai depois eu irei guardar num arquivo a ligações feitas, por exemplo, guardar a ligação que vai do nó 1 ao nó 2 desta forma: FROM 1; TO: 2; mas isto eu consigo.
O meu problema, está em como fazer pra guardar as ligações, pra gerar diferentes ligações, dados os nós e o número máximo de ligações.
Alguém pode clarear minhas ideias? hehe

#2

Você precisa de uma estrutura de dados para guardar grafos, é isso?

Há dois métodos para guardá-los, e os mais adequados dependem dos algoritmos que se deseja usar sobre eles.

Um deles é guardar a matriz ou a lista de adjacências - veja:

Para mais detalhes, comece a ler:

http://opendatastructures.org/versions/edition-0.1d/ods-java/node59.html

#3

Sim, eu preferia fazer uma matriz primeiro hehe.
Eu estava procurando e também encontrei a matriz de adjacencia, porém ainda não consigo pensar mto bem no código.

#4

é simples, vc pode implementar usando uma matriz booleana boolean[][] onde o numero de nos é o tamanho da matriz (x,y) dai é só verificar qual a conectividade dela e ir preenchendo as conectividades na matriz… Faça primeiro na mão, desenhe o grafo e preencha a matriz, fazendo isto vc terá uma ideia de como implementa-lo…

#5

exatamente isso que é meu problema, eu preciso que o programa gere a conectividade, ele deve escolher com qual no um no será ligado…

#6

Não entendi quem decide fazer a conectividade? vc ou o programa?

#7

o programa, ele deve decidir as ligações com qual nó será feito, ele deve dar vários tipos de ligações…

#8

Bem se não existe nenhum critério, só um numero de nós e um numero de conexões e o programa deve devolver todas as conexões possiveis, um algoritimo de força bruta resolve seu problema, digamos que vc use a logica das matrizes booleanas então cada true representa uma conexão no caso se tivesse por exemplo 2 nós e quisesse listar todas as possiveis conexões com o numero maximo de 1 conexão:

[1,0]
[0,0]

[0,1]
[0,0]

[0,0]
[1,0]

[0,0]
[0,1]

Isto no caso usando apenas 1 ligação, se for usar todas as possiveis iria preencher a matriz até todos ficarem 1(true), ou seu algoritimo simplismente vai preencher a matriz de true e false de todas as maneiras possiveis respeitando o numero maximo de ligações (a quantidade de “true” que ele pode ter)

#9