Algoritmo

Buscou no Google?
Digitei algoritmo grafo acíclico:
http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/cycles-and-dags.html

Já busquei até já vi esse site que vc me indico cara mas eu presciso de uma explicação melhor esse tal portugol não consigo enteder…! já implementei minha classe grafo todinha kra to desde as 14:00 tentando fazer esse método mas não consigo cara já tenho as definições para achar o acíclico:

A busca em profundidade pode ser usada
para verificar se um grafo é acíclico ou
contém um ou mais ciclos.
Se uma aresta de retorno é encontrada
durante a busca em profundidade em G,
então o grafo tem ciclo.
Um grafo direcionado G é acíclico se e
somente se a busca em profundidade em G
não apresentar arestas de retorno.

meu método de profundidade é esse:

public void profundidade(int n)
	{
		
		visitado[n]=1;
		 
		for(int i=0;i<numVertices;i++)
		{
			if(matAdj[n][i]!=0 && visitado[i]==0)
			{
				 
				profundidade(i);
			}
		}
		
	}

tenho que implementar alguma coisa nela para conseguir achar o acíclico mas não consigo cara tah dificil…!

Cara isto em java como ficaria…?

Grafo-Acíclico (n, Adj)
1 o para  u ← 1  até  n  faça
2 oooo cor[u] ← branco
3 o para  r ← 1  até  n  faça
4 oooo se  cor[r] = branco
5 ooooooo então  x ← Terr-Acicl (r)
6 ooooooo então  se  x = 0  então devolva  0  e pare
7 o devolva

Na realidade você quer avaliar uma grafo e identificar se ele é ou não acíclico, correto?

Você poderá observar que a estrutura não é uma árvore porque os nós podem ter diferentes pais…

e também não são grafos porque não contém ciclos.

Por isso alguns autores consideram esta estrutura como intermediaria entre grafos e árvores.

Um explicação legal de DAG:

http://w3.ualg.pt/~hshah/algoritmos/aula4/aula4.htm

fw

Só porque eles PODEM ter mais de um pai, nao quer dizer que um caso particular não é uma arvore. Toda arvore é um grafo, e alguns grafos são arvores.

Mesmo que voce armazene uma arvore em uma estrutura de um digrafo, ela continua sendo arvore.

Um grafo pode perfeitamente nao conter ciclos.

A teoria já estudei bastante meu problema é fazer um método que verifique se um grafo é aciclíco e retorne um valor boolean ou qualquer outro verificando se é árvore já está de ótimo tamanho para min, eu não estou conseguindo de jeito algum, meu prof me passou esse método que recebe o vertice, mas seu vertice anterior já tentei usar esse método mas não deu certo.

public void verificaArvore(int v,int ant)
	{ 
		visitado[v]=1;
		int i;
		

		for(i=0;i<matAdj.length;i++)
		{
			if(matAdj[v][i]!=0)
			{
				if(visitado[i]==0)
				{
					verificaArvore(v,i);
				}
				
				else if(i!=ant)
				{
					System.out.print("Não é árvore");
				}
				
				
			}
			 
		}
	}

não está dando certo estou tentando fazer o meu mas está díficil…!

pra voce verificar se um grafo nao tem ciclo, voce TEM de usar busca em profudindade, como ja disseram.

E pra uma busca em profundidade funcionar, so tem duas maneiras: ou voce implementa um algoritmo recursivo, ou utiliza uma pilha para tal efeito.

Cara meu algoritmo de profundidade está aqui:

public void profundidade(int n)
	{
		
		visitado[n]=1;
		saida+="("+n+")"+"\n";
		for(int i=0;i<numVertices;i++)
		{
			if(matAdj[n][i]!=0 && visitado[i]==0)
			{
				 
				profundidade(i);
			}
		}
		
	}

Ele é recursivo esse array “visitado” marca os vertices visitados o tamanho desse array e determinano no meu método:

public void criaGrafo(int n)
	{
		numVertices=n;
		visitado= new int[n];
		matAdj= new int[n][n];
	}

A qual recebe do usuário a quantidade de vertices que ele quer quer o grafo contenha eu estou usando uma matriz de adjacência por isso tenho que fazer o array de já visitado, meu método profundidade está fincionando perfeitamente o problema e como vou fazer para verificar se o tal grafo é aciclíco estou agarrado nisso…

basta mudar para:

public boolean profundidade(int n)
 	{
 		if(visitado[n] == 1) return true;

 		visitado[n]=1;
 		saida+="("+n+")"+"\n";
 		for(int i=0;i<numVertices;i++)
 		{
 			if(matAdj[n][i]!=0 && visitado[i]==0)
 			{
 				 
 				if(profundidade(i)) return true;
                                
 			}
 		}
                return false;
 		
 	}

Pronto. Agora o metodo retorna um boolean. Se ele retornar true, é que tem ciclo, pois ele foi visitar alguem que ja havia sido visitado.

Verifiquei seu método cara sua idéia foi interessante mas não deu certo porque sempre o método vai retornar false;

public boolean verificaArvore(int n)
	  	{
	  		if(visitado[n] == 1) 
	  			return true;
	 
	  		visitado[n]=1;
	  		saida+="("+n+")"+"\n";
	  		for(int i=0;i<numVertices;i++)
	  		{
	  			if(matAdj[n][i]!=0 && visitado[i]==0)
	  			{
	  				 
	  				if(verificaArvore(i)) 
	  					return true;
	                                 
	  			}
	  		}
	         return false;//sempre passa por aqui
	  		
	  	}

Vo quebrando a cabeça uma hora eu consigo…

Tb tenho essa dúvida cara, vai testando uma hora deve da certo.

Obviamente faltou tirar do IF se ele ja havia sido visitado!! Esta ai

public boolean profundidade(int n)
  	{
  		if(visitado[n] == 1) return true;
 
  		visitado[n]=1;
  		saida+="("+n+")"+"\n";
  		for(int i=0;i<numVertices;i++)
  		{
  			if(matAdj[n][i]!=0)
  			{
  				 
  				if(profundidade(i)) return true;
                                 
  			}
  		}
                 return false;
  		
  	}