Implementando um Grafo
Boa tarde pessoal.
Tenho q implementar um grafo q até q é simples. Ele deve fazer o seguinte: receber duas entradas representando dois nós do grafo e deve dizer se o segundo nó é alcançável a partir do primeiro e tb dizer se ele é cíclico.
Pelo oq eu li nos tutoriais daki, as linhas/colunas são os vértices dos grafos e um só vai ser alcançável através do outro se naquela linha/coluna o valor for 1, mas oq eu não estou conseguindo é implementar essa ultima parte, por isso peço a ajuda de vcs.
Tutorial q usei: http://javafree.uol.com.br/artigo/874259/GRAFOS-04-Usando-Matriz-de-Adjacencias.html
Eu já fiz esse código das matrizes, agora quero saber como dizer se um é alcançável através do outro
package grafos;
import javax.swing.JOptionPane;
public class Grafos {
public static void main(String[] args) {
int m[][] = {{0, 0, 0}, {0, 0, 0}};
for (int linha = 0; linha < m.length; linha++) {
for (int coluna = 0; coluna < m[linha].length; coluna++) {
m[linha][coluna] = Integer.parseInt(JOptionPane.showInputDialog("Digite os numeros"));
}
}
for (int linha = 0; linha < m.length; linha++) {
for (int coluna = 0; coluna < m[linha].length; coluna++) {
System.out.print(m[linha][coluna] + "\t");
}
System.out.println();
}
}
}
Jhensen
Curtidas 0
Respostas
André Camargo
11/09/2012
Tu precisa encontrar a linha e coluna do primeiro nó para apartir dessa posição andar uma linha para baixo vendo se encontra o segundo elemento.
GOSTEI 0
Jhensen
11/09/2012
[quote="AndreCamargo"]Tu precisa encontrar a linha e coluna do primeiro nó para apartir dessa posição andar uma linha para baixo vendo se encontra o segundo elemento.
Obrigado pela ajuda amigo, já até implementei a parte de achar o primeiro nó, veja como ficou.
package grafos;
import javax.swing.JOptionPane;
public class Grafos {
public static void main(String[] args) {
int m[][] = {{0, 0, 0}, {0, 0, 0}};
for (int linha = 0; linha < m.length; linha++) {
for (int coluna = 0; coluna < m[linha].length; coluna++) {
m[linha][coluna] = Integer.parseInt(JOptionPane.showInputDialog("Digite os vertíces"));
if(m[linha][coluna] == 1){
System.out.print("O grafo 1 na linha " + linha);
System.out.print("está ligado a coluna " + coluna);
}
}
}
}
}
GOSTEI 0
André Camargo
11/09/2012
Tudo bom!
Pelo que eu entendi agora tu precisa encontrar o grafo A no teu grafo, e deslocando apartir da posição do A uma casa em linhas e colunas e verificar se encontra o grafo C é isso?
GOSTEI 0
Jhensen
11/09/2012
[quote="AndreCamargo"]Tudo bom!
Pelo que eu entendi agora tu precisa encontrar o grafo A no teu grafo, e deslocando apartir da posição do A uma casa em linhas e colunas e verificar se encontra o grafo C é isso?
Isso.
Por exemplo, eu tenho 3 grafos, A,B,C. E quero saber por exemplo se eu posso acessar o grafo C através do grafo A.
Na verdade o conceito principal do progama é dizer se os grafos estão conectados.
Para dois grafos é moleza, só fazer aquele código acima, o meu problema msm é mais de dois grafos
GOSTEI 0
André Camargo
11/09/2012
[quote="Jhensen"][quote="AndreCamargo"]Tudo bom!
Pelo que eu entendi agora tu precisa encontrar o grafo A no teu grafo, e deslocando apartir da posição do A uma casa em linhas e colunas e verificar se encontra o grafo C é isso?
Isso.
Por exemplo, eu tenho 3 grafos, A,B,C. E quero saber por exemplo se eu posso acessar o grafo C através do grafo A.
Na verdade o conceito principal do progama é dizer se os grafos estão conectados.
Para dois grafos é moleza, só fazer aquele código acima, o meu problema msm é mais de dois grafos GOSTEI 0
Jhensen
11/09/2012
[quote="AndreCamargo"][quote="Jhensen"][quote="AndreCamargo"]Tudo bom!
Pelo que eu entendi agora tu precisa encontrar o grafo A no teu grafo, e deslocando apartir da posição do A uma casa em linhas e colunas e verificar se encontra o grafo C é isso?
Isso.
Por exemplo, eu tenho 3 grafos, A,B,C. E quero saber por exemplo se eu posso acessar o grafo C através do grafo A.
Na verdade o conceito principal do progama é dizer se os grafos estão conectados.
Para dois grafos é moleza, só fazer aquele código acima, o meu problema msm é mais de dois grafos GOSTEI 0
Jhensen
11/09/2012
Bom dia!
Então, eu to implementanto, mas não estou conseguindo guardar a linha e coluna em outra matriz.
Eu tava fazendo assim, mas obviamente isso está errado, pq ele tá adicionando toda a outra matriz e não só as linas e colunas onde tem o numero 1, dentro dessa nova matriz q eu crie.
Descobrindo como resolve isso, já resolve 50% dos meus problemas.
:-P
package grafos;
import javax.swing.JOptionPane;
public class Grafos {
public static void main(String[] args) {
int m[][] = {{0, 0, 0}, {0, 0, 0}};
int h[][] = {{0, 0, 0}, {0, 0, 0}};
for (int linha = 0; linha < m.length; linha++) {
for (int coluna = 0; coluna < m[linha].length; coluna++) {
m[linha][coluna] = Integer.parseInt(JOptionPane.showInputDialog("Digite os vertíces"));
if(m[linha][coluna] == 1){
h[linha][coluna]= m[linha][coluna];
GOSTEI 0
Jhensen
11/09/2012
Acho q conseguir fazer.
Agora só falta dizer se ele é cíclico ou não, quer dizer, se ele faz um ciclo.
É dizer se ele vai de A até C e de C até A.
Vc tem alguma sugestão para me ajudar?
package grafos;
import javax.swing.JOptionPane;
public class Grafos {
public static void main(String[] args) {
int m[][] = {{0, 0, 0}, {0, 0, 0}};
int h[][] = {{0, 0, 0}, {0, 0, 0}};
JOptionPane.showMessageDialog(null, "Digite 1 para os vértices que estão conectados");
for (int linha = 0; linha < m.length; linha++) {
for (int coluna = 0; coluna < m[linha].length; coluna++) {
m[linha][coluna] = Integer.parseInt(JOptionPane.showInputDialog("Vértice" + coluna, linha));
if (m[linha][coluna] == 1) {
h[linha][coluna] = m[linha][coluna];
}
}
}
for (int linha = 0; linha < m.length; linha++) {
for (int coluna = 0; coluna < h[linha].length; coluna++) {
if (h[linha][coluna] == 1) {
System.out.println("Os grafos \t" + linha + coluna + "\t estão conectados");
}
}
System.out.println();
}
}
}
GOSTEI 0