Arquivo Discussoes de Programacao e Tecnologia 
FIZ UM MÉTODO PARA PEGAR A GRAU DE UM GRAFO
public void grau(int v)
{
int i,j;
int cont=0;
for(i=v;i<matAdj.length;i++)
{
for(j=0;j<matAdj.length;j++)
{
if(matAdj[i][j]!=0)
{
cont++;
}
}
}
numGrau=cont;
cont=0;
}
mas não está dando certo alguém tem uma idéia de como eu posso fazer?
Não seria o grau de um nó?
O grau de um nó é dado pelo numero de arestas que chegam nesse nó.
O método para descobrir esse grau depende de como foi sua implementação, se foi por matriz de adjacencia ou por matriz de incidencia.
No caso da matriz de adjacencia, basta somar o numero de valores diferentes de zero na linha do nó.
0 1 2 3 4 5
0 0 1 0 0 0 1
1 1 0 0 0 0 1
2 0 0 0 0 1 0
3 0 1 0 0 0 0
4 0 0 0 0 0 0
5 0 0 0 1 0 0
No caso, o nó 1 tem grau 2.
Neste caso, é mais facil usar a implementacao com listas (Lista de adjacencias). Assim o grau de um nó é o numero de elementos em sua lista.
:idea:
for(j=0;j<matAdj[v].length;j++)
{
if(matAdj[v][j]!=0)
{
cont++;
}
}
Acho que vc deve tirar o for mais externo... pq senão ele pega a linha seguinte tb e calcula...
Ele só tem q pegar a linha do vertice v passado como parâmetro.
Obs.: a matriz de adjacencia sempre é uma matrix quadrada.
:idea:
Cara é isso mesmo que vc falow eu estou usando uma matriz de adjacencia e minha ideia e tipo essa sua mesmo, mas tah díficil, vo deixar o código todo para vc verificar minha duvida soh soh no grau, hehe tava viajandu grau do grafo desde já agradeço sua dica de qualquer forma vc já me ajudou..!
Classe mainimport javax.swing.JOptionPane;
import javax.swing.JTextArea;
public class GRAFOMAIN
{
public static GRAFO chama = new GRAFO();
public static void main(String args[])
{
int grafo;
int i;
int continuar=JOptionPane.YES_NO_CANCEL_OPTION;
int continuar2=JOptionPane.YES_NO_CANCEL_OPTION;
int continuar3=JOptionPane.YES_NO_CANCEL_OPTION;
int continuar4=JOptionPane.YES_NO_CANCEL_OPTION;
int continuar5=JOptionPane.YES_NO_CANCEL_OPTION;
int continuar6=JOptionPane.YES_NO_CANCEL_OPTION;
int vetrticeAresta[]= new int [3];
String sair;
int chave=0;
boolean valida=true;
boolean valida2=false;
boolean valida3=false;
while(valida2==false)
{
while(valida!=false)
{
try
{
if(chave==0)
{
grafo=Integer.parseInt(JOptionPane.showInputDialog(null,"Dígite o tamanho do grafo ","Os dados estão na matriz x|x ",JOptionPane.WARNING_MESSAGE));
chama.criaGrafo(grafo);
valida=false;
}
}catch(Exception e)
{
JOptionPane.showMessageDialog(null,"Somente dígitar números inteiros ","Atenção",JOptionPane.ERROR_MESSAGE);
sair=JOptionPane.showInputDialog(null,"Deseja sair ?\nDígite sim para sair\nDígite qualquer tecla para continuar ");
if(sair.equalsIgnoreCase("sim"))
{
System.exit(0);
}
valida=true;
}
}
valida=true;
while(valida!=false)
{
try
{
while(valida3==false)
{
for(i=0;i<vetrticeAresta.length;i++)
{
if(i==0)
vetrticeAresta[i]=Integer.parseInt(JOptionPane.showInputDialog(null,"Dígite o 1º ponto ","ARESTA",JOptionPane.WARNING_MESSAGE));
else if(i==1)
vetrticeAresta[i]=Integer.parseInt(JOptionPane.showInputDialog(null,"Dígite o 2º ponto ","ARESTA",JOptionPane.WARNING_MESSAGE));
else if(i==2)
vetrticeAresta[i]=Integer.parseInt(JOptionPane.showInputDialog(null,"Dígite o peso","PESO",JOptionPane.WARNING_MESSAGE));
}
chama.addAresta(vetrticeAresta[0],vetrticeAresta[1], vetrticeAresta[2]);
continuar3=JOptionPane.showConfirmDialog(null,"Deseja adicionar mais uma aresta ou peso ?");
if(continuar3==JOptionPane.NO_OPTION)
valida3=true;
}
valida3=false;
valida=false;
}catch(Exception e)
{
JOptionPane.showMessageDialog(null,"O valor que você dígitou não pode ser colocado na matriz ");
valida=true;
sair=JOptionPane.showInputDialog(null,"Deseja sair ?\nDígite sim para sair\nDígite qualquer tecla para continuar ");
if(sair.equalsIgnoreCase("sim"))
{
System.exit(0);
}
}
}
valida=true;
continuar5=JOptionPane.showConfirmDialog(null,"Deseja retirar alguma aresta ?");
if(continuar5==JOptionPane.YES_NO_OPTION)
{
retAresta();
}
continuar=JOptionPane.showConfirmDialog(null,"Deseja fazer a impresão ?");
if(continuar==JOptionPane.YES_OPTION)
{
impresao();
}
//**************************************
continuar4=JOptionPane.showConfirmDialog(null,"Deseja verificar o grau do respectivo vértice ?");
if(continuar4==JOptionPane.YES_OPTION)
{
grau();
}
//***************************************
continuar6=JOptionPane.showConfirmDialog(null,"Deseja verificar se algum vertice\ntem o caminho de euler ?");
if(continuar6==JOptionPane.YES_NO_OPTION)
{
caminhoEuler();
}
//***************************************
continuar2=JOptionPane.showConfirmDialog(null,"Deseja voltar a todas opções ?");
if(continuar2==JOptionPane.NO_OPTION)
{
valida2=true;
}
else
{
valida=false;
chave=1;
}
}//fim do while pricipal
}//fim do método main
public static void retAresta()
{
int retVet[]= new int [2];
int i;
for(i=0;i<retVet.length;i++)
{
retVet[i]=Integer.parseInt(JOptionPane.showInputDialog(null,"Dígite o "+(i+1)+"º ponto","RETIRAR ARESTA",JOptionPane.WARNING_MESSAGE));
}
chama.remAresta(retVet[0],retVet[1]);
}
public static void impresao()
{
JTextArea texto = new JTextArea(5,5);
texto.setText(chama.imprimePares());
JOptionPane.showMessageDialog(null,texto,"Impressão",JOptionPane.WARNING_MESSAGE);
}
public static void grau()
{
int pesGrau;
pesGrau=Integer.parseInt(JOptionPane.showInputDialog(null,"Dígite o vertice que vc deseja verificar o grau "));
chama.grau(pesGrau);
JOptionPane.showMessageDialog(null,"Este vertice tem grau "+chama.getNumGrau());
}
public static void caminhoEuler()
{
if(chama.caminhoEuler()==true)
{
JOptionPane.showMessageDialog(null,"Existe caminho de euler ","Atenção",JOptionPane.WARNING_MESSAGE);
}
else
JOptionPane.showMessageDialog(null,"Não existe caminho de euler ","Atenção",JOptionPane.WARNING_MESSAGE);
}
}
import javax.swing.JOptionPane;
import javax.swing.JTextArea;
public class GRAFO
{
private int matAdj[][];
private int numVertices;
private int numGrau;
private int visitado[];
public void criaGrafo(int n)
{
numVertices=n;
matAdj= new int[n][n];
}
public void addAresta(int vi,int vj,int peso)
{
matAdj[vi][vj]=peso;
matAdj[vj][vi]=peso;
}
public void remAresta(int vi,int vj)
{
matAdj[vi][vj]=0;
matAdj[vj][vi]=0;
}
public String imprimePares()
{
String saida="";
int i,j;
saida+="E = {";
for(i=0;i<matAdj.length;i++)
{
for(j=0;j<matAdj.length;j++)
{
if(matAdj[i][j]!=0)
{
saida+="("+i+","+j+")";
}
}
}
saida+="}";
return saida;
}
public int grau(int v)
{
int i,j;
int cont=0;
for(i=v;i<matAdj.length;i++)
{
for(j=0;j<matAdj.length;j++)
{
if(matAdj[i][j]!=0)
{
cont++;
}
}
}
numGrau=cont;
return cont;
}
public int getNumGrau()
{
return numGrau;
}
public boolean caminhoEuler()
{
int cont,i;
cont=0;
for(i=0;i<=numVertices;i++)
{
if(grau(i)%2!=0)
cont++;
}
return (cont<=2);
}
}
Cara usei sua idéia e deu certo to em dúvida de como implementar um método que faça a busca em profundidade vc tem alguma idéia ?
Sua busca em profundidade tem qual objetivo?? achar um nó específico? Ou somar “alguma coisa”?
:idea:
Tipo cara, um vertice é escolhido como ponto de partida da busca, do vertice inicial visitamos um vizinho ainda não visitado até que todos os vertices tenham sido visitados
estou pensando em um algoritimo que fala isso saiu este:
public void profundidade(int v)
{
int i;
visitado[v]=1;
System.out.println(v);
for(i=0;i<numVertices;i++)
{
if(matAdj[v][i]!=0 && visitado[i]==0)
profundidade(v);
}
}
mas falta algo estou quebrandu a cabeça aki
já vi desse cara naum sei o que ele passa como parametros