Fórum Implementando um Grafo #568558

11/09/2012

0

Java

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

Jhensen

Responder

Posts

13/09/2012

André Camargo

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

Gostei + 0

14/09/2012

Jhensen

[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);
                
                    
                }
            }

        }
}
}
Claro q ainda falta bastante coisa, mas o básico é isso. Meu problema continua sendo como dizer se por exemplo: temos os grafos A,B,C como dizer se o grafo C é assecível pelo grafo A. Vc teria alguma sugestão para poder me ajudar?
Responder

Gostei + 0

14/09/2012

André Camargo

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

Gostei + 0

14/09/2012

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
Responder

Gostei + 0

14/09/2012

André Camargo

[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
Assim, tu precisa percorrer a matriz até encontrar o grafo a, ao encontrar tu precisa guardar em qual linha e qual coluna ele está, depois precisa simplesmente acrescentar um na linha e um na coluna verificando se encontra o outro grafo.
Responder

Gostei + 0

14/09/2012

Jhensen

[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
Assim, tu precisa percorrer a matriz até encontrar o grafo a, ao encontrar tu precisa guardar em qual linha e qual coluna ele está, depois precisa simplesmente acrescentar um na linha e um na coluna verificando se encontra o outro grafo. Obrigado pela ajuda amigo, irei implementar oq vc sugeriu e posto aki.
Responder

Gostei + 0

17/09/2012

Jhensen

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. 
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];
Descobrindo como resolve isso, já resolve 50% dos meus problemas. :-P
Responder

Gostei + 0

17/09/2012

Jhensen

Acho q conseguir fazer. 

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();
        }


    }
}
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?
Responder

Gostei + 0

Utilizamos cookies para fornecer uma melhor experiência para nossos usuários, consulte nossa política de privacidade.

Aceitar