~DFS Ponto-a-Ponto~

//Consiste num Grafo, representado por suas aretas pelo qual o algoritmo faz a busca em profundidade de um nó //inicial até um final, imprimindo a ordem da busca

struct no
{
    int info;
    struct no *proximo;
};

class pilha
{
    struct no *topo;
public:
    pilha();
    void push(int);
    int pop();
    bool isVazia();
    void mostrar();
};

pilha::pilha()
{
    this->topo = NULL;
}

void pilha::push(int v)
{
    no *p = new no;
    p->info = v;
    p->proximo = NULL;
    if(topo!=NULL)
    {
        p->proximo = topo;
    }
    topo = p;
}

int pilha::pop()
{
    struct no *temp;
    int valor;
    if(topo!=NULL)
    {
        temp = topo;
        topo = topo->proximo;
        valor = temp->info;
        delete temp;
    }
    return valor;
}

bool pilha::isVazia()
{
    return (topo == NULL);
}

void pilha::mostrar()
{
    struct no *p = topo;
    if(topo!=NULL)
    {
        cout<<"\npilha:\n";
        while(p!=NULL)
        {
            cout<<p->info<<endl;
            p = p->proximo;
        }
    }
}

class Grafo
{
private:
    int n;
    int **A;
public:
    Grafo(int size = 2);
    ~Grafo();
    bool isConectado(int, int);
    void insereAresta(int x, int y);
    int DFS(int , int);
};

Grafo::Grafo(int size)
{
    int i, j;
    if (size < 2) n = 2;
    else n = size;
    A = new int*[n];
    for (i = 0; i < n; ++i)
        A[i] = new int[n];
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            A[i][j] = 0;
}

Grafo::~Grafo()
{
    for (int i = 0; i < n; ++i)
        delete [] A[i];
    delete [] A;
}

bool Grafo::isConectado(int x, int y)
{
    return (A[x][y] == 1);
}

void Grafo::insereAresta(int x, int y)
{
    A[x][y] = A[y][x] = 1;
}

void Grafo::DFS(int x, int chegada)
{
    pilha s;
    bool *visitado = new bool[n+1];
    int i;
    for(i = 0; i <= n; i++)
        visitado[i] = false;
    s.push(x);
    visitado[x] = true;
    if(x == chegada) return;
    cout << "DFS comecando de ";
    cout << x << " para "<< chegada << " : " << endl;
    while(!s.isVazia())
    {
        int k = s.pop();
        if(k == chegada)
        {
            break;
        }
        cout<<k<<" ";
        for (i = n; i >= 0 ; --i)
            if (isConectado(k, i) && !visitado[i])
            {
                s.push(i);
                visitado[i] = true;
            }
    }
    cout<<endl;
    delete [] visitado;
}