estou fazendo um trabalho que parte dele consiste em achar todos os possíveis caminhos a partir de um vértice até um outro determinado vértice, para isso estou usando um algoritmo quase idêntico a DFS como mostrado abaixo:
#include <iostream>
#include <list>
#include <algorithm> // função find
#include <stack> // pilha para usar na DFS
#include <vector>
using namespace std;
vector<int> aux;
class Grafo
{
int V; // número de vértices
list<int> *adj; // ponteiro para um array contendo as listas de adjacências
public:
Grafo(int V); // construtor
void adicionarAresta(int v1, int v2); // adiciona uma aresta no grafo
// faz uma DFS a partir de um vértice
void dfs(int v);
};
Grafo::Grafo(int V)
{
this->V = V; // atribui o número de vértices
adj = new list<int>[V]; // cria as listas
}
void Grafo::adicionarAresta(int v1, int v2)
{
// adiciona vértice v2 à lista de vértices adjacentes de v1
adj[v1].push_back(v2);
}
void Grafo::dfs(int v)
{
stack<int> pilha;
bool visitados[V]; // vetor de visitados
// marca todos como não visitados
for(int i = 0; i < V; i++)
visitados[i] = false;
while(true)
{
if(!visitados[v])
{
visitados[v] = true; // marca como visitado
pilha.push(v); // insere "v" na pilha
aux.push_back(v);
}
bool achou = false;
list<int>::iterator it;
// busca por um vizinho não visitado
for(it = adj[v].begin(); it != adj[v].end(); it++)
{
if(!visitados[*it])
{
//cout << *it << " ";
achou = true;
break;
}
}
if(achou){
v = *it; // atualiza o "v"
}
else
{
for(list<int>::iterator it1 = adj[v].begin(); it1 != adj[v].end(); it1++){
if(*it1==12){
for (int i = 0; i < (int)aux.size(); i++)
{
cout << aux[i] << endl;
}
cout << "****" <<endl;
}
}
// se todos os vizinhos estão visitados ou não existem vizinhos
// remove da pilha
aux.erase(aux.end()-1);
pilha.pop();
// se a pilha ficar vazia, então terminou a busca
if(pilha.empty())
break;
// se chegou aqui, é porque pode pegar elemento do topo
v = pilha.top();
}
}
}
int main()
{
int V = 13;
Grafo grafo(V);
// adicionando as arestas
grafo.adicionarAresta(0,1);
grafo.adicionarAresta(1,2);
grafo.adicionarAresta(2,11);
grafo.adicionarAresta(2,3);
grafo.adicionarAresta(3,4);
grafo.adicionarAresta(4,5);
grafo.adicionarAresta(4,7);
grafo.adicionarAresta(5,6);
grafo.adicionarAresta(6,10);
grafo.adicionarAresta(7,8);
grafo.adicionarAresta(8,9);
grafo.adicionarAresta(9,10);
grafo.adicionarAresta(10,11);
grafo.adicionarAresta(11,12);
grafo.dfs(0);
return 0;
}
A minha ideia é a seguinte, a cada vértice adicionado a pilha, também é adicionado a um vector aux, que armazena exatamente a mesma coisa que na pilha, mas uso ele por que posso acessar todas as posições na hora de imprimir um caminho, quando na pilha só posso acessar o topo, então vou armazenando os elementos, quando chega a hora de remover alguém da pilha, eu verifico se aquele elemento é adjacente ao que estou procurando (isso é feito da linha 73-82, só que por algum motivo pra esse grafo que está no teste não funciona, alguém pode me dar uma luz?
DFS
? Pode por na pergunta o que é isso, para pessoas que não lembram desses jargões?