dfs.cpp

#include "iostream"
#include "stack"
#include "vector"
using namespace std;

// matriz de adjacencia
vector< vector<int> > grafo;

// vertices visitados
vector<bool> visitado;

// conteudo dos vertices
vector<int> valor;

// pilha de controle do caminho percorrido
stack<int> caminho;

// somatorio dos nivels | arestas
int nivel = 0;

// somatorio dos custos
int custo = 0;

// valor buscado
int busca;

int getVerticeFilho( int pai ){// busca um vertice filho
	
	for( int cont=0; cont < grafo[pai].size(); cont++ ){// retorna o primeiro filho nao visitado

		if( grafo[pai][cont] != 0 && visitado[cont] == false ) 
			return cont; 	

	}

	// nao tem filho
	return -1; 
}

void dfs( int verticeAtual ){//	busca em profundidade

	// debug
	printf("Vertice: %d | nivel: %d | custo: %d |\n", verticeAtual, nivel, custo );

	// busca se o vertice atual tem filho
	int verticeFilho = getVerticeFilho( verticeAtual );

	// marca o vertice atual como vistado
	visitado[verticeAtual] = true;

	if( valor[verticeAtual] == busca ){// dfs termina aqui

		printf("alvo encontrado no vertice %d\n", verticeAtual );
	
	}else if( verticeFilho != -1 ){// caso tenha algum filho
		
		// guarda o vertice atual caso precise voltar
		caminho.push( verticeAtual );

		// incrementa o contador de custo, pois está aprofundadando
		custo += grafo[verticeAtual][verticeFilho];

		// incrementa o contador de nivel, pois está aprofundando
		nivel++;

		// executa o mesmo algoritmo no vertice filho
		dfs( verticeFilho );

	}else if( !caminho.empty() ){// caso tenha algum vertice pai

		// pega o pai
		int verticePai = caminho.top();

		// remove da pilha, pois vai para ele
		caminho.pop();

		// decrementa o contador de custo, pois está voltando
		custo -= grafo[verticePai][verticeAtual];

		// decrementa o contador de nivel, pois está voltando
		nivel--;

		// executa o mesmo algoritmo no vertice pai
		dfs( verticePai );

	}else{// nao encontrou em nenhum vertice o valor buscado

		printf("valor pertence a nenhum vertice do grafo\n");
	}

}

int main( void ){

	// quantidade de vertices
	int quantVertice = 4;
	
	// construindo um gafo vazio
	for( int cont=0; cont < quantVertice; cont++ ){
		grafo.push_back(vector<int>( quantVertice, 0 ) );
		visitado.push_back(0);
	}
	

	// adicionando as arestas do grafo
	grafo[0][1] = 10;
	grafo[1][2] = 20;
	grafo[0][2] = 11;
	grafo[2][3] = 50;

	// valores que cada vertice guarda
	valor = {10, 25, 30, 42};
	
	// buscar o vertice que contem o valor 50
	busca = 50;
	
	// partindo do vertice zero
	dfs( 0 );

	return 0;
}