All possible paths in graphs

Question

All possible paths in graphs

Navigation

#1 by (1 votes)

2

I'm doing a work that starts from it, it's all about finding all possible paths from one vertex to another vertex, so I'm using an algorithm almost identical to DFS as shown below:

#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;
}

My idea is as follows, with each vertex added to the stack, is also added to an aux vector, which stores exactly the same thing as the stack, but I use it because I can access all the positions at the time of printing one path, when on the stack I can only access the top, so I'm storing the elements, when it comes time to remove someone from the stack, I check if that element is adjacent to what I'm looking for (this is done from line 73-82, for some reason for that graph that is in the test does not work, can someone give me a light?

c++ grafo

asked by anonymous 28.06.2017 / 02:50

1 answer

Working with sound in .NET Error copying files between servers [closed]

score 1 · Accepted Answer

I found the answer after a while, if anyone has the same difficulty here is the solution:

// C++ program to print all paths from a source to destination.
#include<iostream>
#include <list>
using namespace std;

// A directed graph using adjacency list representation
class Graph
{
    int V;    // No. of vertices in graph
    list<int> *adj; // Pointer to an array containing adjacency lists

    // A recursive function used by printAllPaths()
    void printAllPathsUtil(int , int , bool [], int [], int &);

public:
    Graph(int V);   // Constructor
    void addEdge(int u, int v);
    void printAllPaths(int s, int d);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int u, int v)
{
    adj[u].push_back(v); // Add v to u’s list.
}

// Prints all paths from 's' to 'd'
void Graph::printAllPaths(int s, int d)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];

    // Create an array to store paths
    int *path = new int[V];
    int path_index = 0; // Initialize path[] as empty

    // Initialize all vertices as not visited
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function to print all paths
    printAllPathsUtil(s, d, visited, path, path_index);
}

// A recursive function to print all paths from 'u' to 'd'.
// visited[] keeps track of vertices in current path.
// path[] stores actual vertices and path_index is current
// index in path[]
void Graph::printAllPathsUtil(int u, int d, bool visited[],
                              int path[], int &path_index)
{
    // Mark the current node and store it in path[]
    visited[u] = true;
    path[path_index] = u;
    path_index++;

    // If current vertex is same as destination, then print
    // current path[]
    if (u == d)
    {
        for (int i = 0; i<path_index; i++)
            cout << path[i] << " ";
        cout << endl;
    }
    else // If current vertex is not destination
    {
        // Recur for all the vertices adjacent to current vertex
        list<int>::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
            if (!visited[*i])
                printAllPathsUtil(*i, d, visited, path, path_index);
    }

    // Remove current vertex from path[] and mark it as unvisited
    path_index--;
    visited[u] = false;
}

// Driver program
int main()
{
    // Create a graph given in the above diagram
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(2, 0);
    g.addEdge(2, 1);
    g.addEdge(1, 3);

    int s = 2, d = 3;
    cout << "Following are all different paths from " << s
         << " to " << d << endl;
    g.printAllPaths(s, d);

    return 0;
}

Source: GeeksForGeeks