Codigo para saber si este grafo es conexo

[verakra]

ESTE ES MI CODIGO LE INGRESO UNA MATRIZ DE NxN de un GRAFO NO DIRIGIDO, LO QUE NECESITO QUE ME AYUDEN ES COMO HAGO PARA RECORRER ESA MATRIZ Y DECIR SI EL GRAFO ES CONEXO O NO


TEORIA GRAFO CONEXO
un grafo es conexo si existe un camino de un nodo hacia cualquier otro nodo del grafo

Código (java) [Seleccionar] Expandir


package matriz_adyacencia;



/**
*
* @author PAPAYO
*/
public class Matriz_Adyacencia {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Matriz_de_adyacencia matriz = new Matriz_de_adyacencia(5);
               
       
        matriz.agregar(0, 1);
        matriz.agregar(0, 1);
        matriz.agregar(0, 2);
        matriz.agregar(0, 3);
       
        matriz.agregar(1, 0);
        matriz.agregar(1, 0);
        matriz.agregar(1, 4);
       
        matriz.agregar(2, 0);
        matriz.agregar(2, 3);
        matriz.agregar(2, 4);
       
        matriz.agregar(3, 0);
        matriz.agregar(3, 2);
       
        matriz.agregar(4, 1);
        matriz.agregar(4, 2);
        matriz.agregar(4, 4);
        matriz.agregar(4, 4);
       
       
       
        matriz.imprimir();
       
       
       
       

    }
       
       
    }

Código (java) [Seleccionar] Expandir

package matriz_adyacencia;

public class Matriz_de_adyacencia {
   
    public int n;
    public int[][] matriz;
   
    /**
     * Constructor de clase
     * @param n numero de nodos
     */
    public Matriz_de_adyacencia(int n) {
        this.n = n;
        matriz = new int[this.n][this.n];
        //se inicializa matriz en 0
        for(int i=0; i< n; i++){
            for(int j=0; j< n; j++){
                matriz[i][j] = 0;
            }           
        }
    }
   
    public void agregar(int i, int j){
        matriz[i][j] += 1;
    }
   
    public void remover(int i, int j){
        if(matriz[i][j]>0)
            matriz[i][j] -= 1;
    }
   
    public void imprimir(){
        for(int i=0; i< n; i++){
            for(int j=0; j< n; j++){
                System.out.print( matriz[i][j] + "  " );       
            }
            System.out.println("");
           
        } 
    }
   
 

   
}

ESPERO QUE ME AYUDEN GRACIASS

[K-YreX]

Voy a comentarte la parte teórica de los grafos y cómo se relaciona esto con la matriz de adyacencia del correspondiente grafo. Primero 3 definiciones:

• Matriz de adyacencia: matriz en la que para cada i y para cada j, M[j] = 0 si no existe un camino del vértice i al vértice j y M[j] = 1 si sí que existe un camino del vértice i al vértice j.
  
  • Grafo conexo: grafo que para todo vértice Vi, existe j != i tal que Vi está conectado con Vj. Dicho de otra manera, un grafo conexo no tiene ningún vértice aislado.
    
  • Grafo completo: grafo que tiene todos los vértices conectados con todos los vértices. Dicho de otra manera puedes ir directamente desde cualquier vértice a cualquier otro vértice.
    Ahora viene la relación de estos grafos con su matriz de adyacencia:
    
  • Un grafo es conexo si en su matriz de adyacencia no existe ningún índice <i> tal que la fila <i> y la columna <i> estén compuestas únicamente por 0 (ambas al mismo tiempo, fila y columna). En grafos no dirigidos bastaría con comprobar una de las dos, la fila o la columna.
    
  • Un grafo es completo si en su matriz de adyacencia sólo existen 0 en la diagonal principal.
    
    Con todos estos datos creo que ya puedes implementarlo tú en tu programa. Espero que todas las explicaciones sean claras y sobre todo, correctas. Suerte

[verakra]

Entonces tendría que hacer otro ciclo que me vaya comparando los componentes de cada fila y de cada columna y que me diga si es cero o uno, y que los guarde en algun lado?

entonces tengo que crear otra funcion void recorrergrafo y que esa misma me diga si es conexo o no?

[K-YreX]

Yo crearía directamente una función:

Código (java) [Seleccionar] Expandir


public static boolean esConexo(matrizDeAdyacencia){
    // compruebas si es conexo
    // retornas el resultado
}
Y la forma de hacerlo depende como te he dicho antes de si el grafo es dirigido o no. Si sabemos como precondición del ejercicio que el grafo no es dirigido bastaría con comprobar filas o columnas (una de las dos). Si el grafo es dirigido o podría ser dirigido, entonces debemos comprobar filas y columnas. Te pongo una forma de hacerlo en pseudocódigo para grafos no dirigidos. Luego te queda que lo implementes en java.

Código [Seleccionar] Expandir


matriz[N][N]
i := 0
mientras conexo and i < N
    conexo = (matriz[i][0] != 0)
    j := 1
    mientras !conexo and j < N
        conexo = (matriz[i][j] != 0)
        j := j + 1
    fin mientras
    i := i + 1
fin mientras

[verakra]

SUPONGO QUE ASI ESTARIA BUENO, AHORA SOLO FALTA LLAMAR LA FUNCION EN EL mAIN Y LISTO CREERIA YO, O FALTA alguna cosa?

otra cosa que no tengo muy clara, SI RETORNA FALSE=NO CONEXO Y SI RETORNA TRUE=CONEXO?

Y COMO PUEDO COMPROBARLO SI ME FUNCION, SUPONIENDO QUE TENGO TODO EL CODIGO HECHO

Código (java) [Seleccionar] Expandir

public  boolean esConexoo(){
      boolean esConexoo=true;
      for(int i=0;i<matriz.length;i++){
          for(int j=0;j<matriz.length;j++){
              if(i!=j && matriz[i][j]==0){
                  esConexoo = false;
                  break;
              }
         
          }
      }
     
       System.out.println(esConexoo);
       return false;
  }

[verakra]

BUENO YA COMPILE Y TODO PERFECTO, PERO LA MATRIZ QUE LE INGRESE ES DE UN GRAFO CONEXO , ENTONCES NO ENTIENDO PORQUE SALIO EL FALSE, ME PERDI EN ESTA PARTE , que hize mal o pase por alto alguna cosa?

Código (java) [Seleccionar] Expandir

package matriz_adyacencia;



/**
*
* @author USUARIO
*/
public class Matriz_Adyacencia {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Matriz_de_adyacencia matriz = new Matriz_de_adyacencia(5);
         Matriz_de_adyacencia Conexion  =  new Matriz_de_adyacencia(5);
               Conexion.esConexoo();
           System.out.println(Conexion.esConexoo() );
       
        matriz.agregar(0, 1);
        matriz.agregar(0, 1);
        matriz.agregar(0, 2);
        matriz.agregar(0, 3);
       
        matriz.agregar(1, 0);
        matriz.agregar(1, 0);
        matriz.agregar(1, 4);
       
        matriz.agregar(2, 0);
        matriz.agregar(2, 3);
        matriz.agregar(2, 4);
       
        matriz.agregar(3, 0);
        matriz.agregar(3, 2);
       
        matriz.agregar(4, 1);
        matriz.agregar(4, 2);
        matriz.agregar(4, 4);
        matriz.agregar(4, 4);
       
     
       
       
     
       
       
        matriz.imprimir();
       
       
       
       

    }
       
       
    }

Código (java) [Seleccionar] Expandir

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package matriz_adyacencia;


public class Matriz_de_adyacencia {
   
    public int n;
    public int[][] matriz;
   
    /**
     * Constructor de clase
     * @param n numero de nodos
     */
    public Matriz_de_adyacencia(int n) {
        this.n = n;
        matriz = new int[this.n][this.n];
        //se inicializa matriz en 0
        for(int i=0; i< n; i++){
            for(int j=0; j< n; j++){
                matriz[i][j] = 0;
            }           
        }
    }
   
    public void agregar(int i, int j){
        matriz[i][j] += 1;
    }
   
    public void remover(int i, int j){
        if(matriz[i][j]>0)
            matriz[i][j]-= 1;
    }
   
    public void imprimir(){
        for(int i=0; i< n; i++){
            for(int j=0; j< n; j++){
               
               
                System.out.print( matriz[i][j] + "  " );       
           
            }
            System.out.println("");
           
        } 
    }

   public  boolean esConexoo(){
       boolean conexoo=true;
       for(int i=0;i<matriz.length;i++){
           for(int j=0;j<matriz.length;j++){
               
               if(i!=j && matriz[i][j]==0){
                   conexoo = false;
                break;
           
           }


       }
       
           
       
   }
       System.out.println(conexoo);
        return false;

}
}

   


   

[K-YreX]

Primero de todo te recomiendo quitar el mensaje de la función <esConexo()>. Es mejor que la función sólo retorne un resultado y luego decidir tú si mostrarlo por pantalla o no. Respecto a tu duda de true/false. Piensa que vas a utilizar esta función:

Código (java) [Seleccionar] Expandir


public static void main(String[] args){
    Matriz_de_adyacencia matriz = new Matriz_de_adyacencia[5][5];
    // dar valores a la matriz de adyacencia

    if(esConexo(matriz))
        System.out.println("El grafo es conexo");
    else
        System.out.println("El grafo no es conexo");
}
Entonces si preguntamos si es conexo, la función tendrá que devolver <true> si sí que es conexo y false si no es cierto que sea conexo. En tu caso estás devolviendo siempre <false> porque has puesto <return false>.

Además de todo lo anterior, me parece que esa función que has implementado no es del todo correcta. En el momento que una casilla es 0, se cambia el valor de <conexo> a <false> y con que una casilla sea 0 el grafo no deja de ser conexo. Esa función sería correcta si se encargara de determinar si el grafo es completo, no conexo.

[verakra]

me has dejado mas perdido desde que arranque, me dices una cosa y luego otra , no logro entender que es lo que me quieres decir , solo necesito saber que correcciones hago puntualmente, porque tus explicaciones no me quedan muy claras

[K-YreX]

me has dejado mas perdido desde que arranque, me dices una cosa y luego otra , no logro entender que es lo que me quieres decir , solo necesito saber que correcciones hago puntualmente, porque tus explicaciones no me quedan muy claras

Pero si te digo cambia esto por esto y no entiendes por qué lo haces, es lo mismo que no avanzar. El objetivo es que entiendas el problema y seas capaz de encontrar la solución por ti mismo.
Te expliqué lo que era un grafo conexo y un grafo completo, te comenté las características de la matriz de adyacencia de un grafo conexo y de un grafo completo y te puse un pseudocódigo de cómo identificar un grafo conexo.
No me has entendido, no pasa nada. Prefiero hacer otro intento para explicártelo en vez de darte la solución. Me he dado cuenta de que yo te he puesto dos códigos en los que trato a la función <esConexo()> como una función de la clase principal y no de la clase <Matriz_de_adyacencia>, fallo mío. Igual eso te ha confundido más. Empiezo otra vez:

Aquí tienes un ejemplo de una matriz de adyacencia de un grafo conexo (ya que ninguna fila ni ninguna columna está compuesta únicamente de 0) y no dirigido (ya que la matriz es simétrica respecto a la diagonal principal):

Código [Seleccionar] Expandir


0  1  1  0  1
1  0  1  0  1
1  1  0  1  0
0  0  1  0  1
1  1  0  1  0
Y aquí tienes un ejemplo de una matriz de adyacencia de un grafo completo (ya que los únicos 0 están en la diagonal principal) y no dirigido (ya que la matriz es simétrica también respecto a la diagonal principal):

Código [Seleccionar] Expandir


0  1  1  1  1
1  0  1  1  1
1  1  0  1  1
1  1  1  0  1
1  1  1  1  0

Ahora vamos a ver cómo funciona tu función:

Código (java) [Seleccionar] Expandir


public boolean esConexoo(){
    boolean conexoo = true; // supones que el grafo es conexo
    for(int i = 0; i < matriz.length; i++){ // para cada fila i...
        for(int j = 0; j < matriz.length; j++){ // ...recorremos cada columna j y...
            if(i != j && matriz[i][j] == 0){ // ...si no estamos en la diagonal principal y esa casilla tiene un 0...
                conexoo = false; // ...el grafo deja de ser conexo
                break; // y dejamos de comprobar columnas para esa fila y pasamos a la siguiente fila
            }
        }
    }
    System.out.println(conexoo); // mostramos el resultado de la funcion
    return false; // y retornamos siempre false
}

Cuál es el problema de esta función? Que en cuanto se cumplen las dos condiciones del <if>, se determina que la matriz no es conexa y eso no es cierto. Esa función sería correcta si su función fuese determinar si un grafo es o no completo. Además como consejo personal y que es una buena práctica te recomiendo quitar el <System.out.println(conexoo)> porque es mejor no mostrar el resultado por pantalla dentro de la propia función. Es mejor retornar el resultado y aprovecharlo fuera de la función como indico aquí:

Código (java) [Seleccionar] Expandir


public static void main(String[] args){
    Matriz_de_adyacencia matriz = new Matriz_de_adyacencia[5][5];
    // dar valores a la matriz de adyacencia

    if(matriz.esConexo())
        System.out.println("El grafo es conexo");
    else
        System.out.println("El grafo no es conexo");
}

Te explico también porque es mejor no poner el mensaje dentro de la función. Imagina que tienes 50 grafos (es decir, 50 matrices) en un vector y quieres guardar en otro vector sólo los que son conexos. Tendrías que hacer un bucle para las 50 matrices y si se cumple que es conexo, guardarla en otro vector. Para realizar ese cálculo seguramente no te interese mostrar por pantalla cada resultado, no? Por eso es mejor no mostrar mensajes dentro de la función.
Y el último problema de tu función que he citado un poco más arriba es la última línea: <return false>. La "gracia" de la función es devolver <true> cuando el grafo es conexo y devolver <false> cuando no lo es. Si devuelves siempre <false> pues no tendrá mucho sentido. Entonces para devolver <true> o <false> dependiendo de lo que valga la variable <conexoo> lo que tienes que hacer es devolver la propia variable: <return conexoo>. Así cuando <conexoo> valga <true>, estarás retornando <true> y cuando <conexoo> valga <false>, estarás retornando <false>.

Para intentar dejarlo lo más claro posible te explico ahora el pseudocódigo que te puse anteriormente en otro mensaje:
PD: Lo he modificado un poco para hacerlo más fácil de entender aunque un poco menos eficiente. El original seguirá estando en el otro mensaje que puse anteriormente.

Código [Seleccionar] Expandir


matriz[N][N]
i := 0
conexo = true // suponemos que el grafo es conexo
mientras conexo and i < N // mientras siga siendo conexo y no se acaben las filas, para cada fila...
    conexo = false // ...suponemos que no es conexo y empezamos a comprobar cada columna de esa fila...
    j := 0
    mientras !conexo and j < N // ...mientras siga sin ser conexo y no se acaben las columnas...
        conexo = (matriz[i][j] != 0) // ...si la casilla vale 0, sigue sin ser conexo (false) pero si es distinto de 0, vale true para pasar a la siguiente fila directamente
        j := j + 1
    fin mientras
    i := i + 1
fin mientras
return conexo // ...cuando acabas de recorrer toda la matriz devuelves el valor de <conexo> ya sea true o false

Espero que con esta explicación te haya quedado un poco más claro. Si tienes alguna duda sobre una parte específica de todo lo explicado puedes citar esa parte y exponer tu duda para poder centrarme en aclararte esa parte.