détecter le cycle et imprimer en utilisant dfs

Question

J'essaie de détecter et d'imprimer un cycle dans un chemin non dirigé, à partir d'un sommet donné. Jusqu'à présent, le chemin est enregistré dans un vecteur. Le code semble fonctionner, mais il y a un autre sommet signalé qu'il devrait être.

Pour l'exemple donné, un chemin attendu serait: -1,6,0,5,3 qui mettra également: -1,6,0,5,3,2 mais il y a un autre sommet que prévu. Peut-être que quelqu'un a une idée de comment cela peut être corrigé.

Merci d'avance!

#include <vector> 
#include <iostream> 


class Vertex 
{ 
public: 
    Vertex() {}; 
    Vertex(int x, int y, bool visited) : _x(x), _y(y){} 
    int _x; 
    int _y; 
}; 


class Edge 
{ 
public: 
    Edge(Vertex* from, Vertex* to): _from(from), _to(to){} 
    Vertex* _from; 
    Vertex* _to; 
}; 

class MyGraph 
{ 

public: 
void addVertex(int x, int y, bool visited); 
void addEdge(Vertex* vp1, Vertex* vp2); 

bool dfs(int v, int p); 

std::vector<std::vector<int>> g; 
bool* visited; 
std::vector<Edge> edges; 
std::vector<Vertex> vertices; 
std::vector<int>path; 

}; 


void MyGraph::addVertex(int x, int y, bool visited) 
{ 
    Vertex v = Vertex(x, y, visited); 
    this->vertices.push_back(v); 
} 


void MyGraph::addEdge(Vertex* vp1, Vertex* vp2) 
{ 
    Edge e = Edge(vp1, vp2); 
    this->edges.push_back(e); 
} 


bool MyGraph::dfs(int v, int p) 
{ 

    visited[v] = true; 

    this->path.push_back(p); 

    for (int i = 0; i < (int)g[v].size(); i++) 
    { 
     if (!visited[g[v][i]]) 
     { 
      dfs(g[v][i], v); 
      return true; 
     } 
     if (g[v][i] != p) 
     { 
      return true; 
     } 
    } 

    this->path.pop_back(); 
    return false; 

} 

int main(int argc, char** argv) 
{ 
    MyGraph mg; 

    mg.addVertex(3, 0, false); 
    mg.addVertex(0, 1, false); 
    mg.addVertex(2, 1, false); 
    mg.addVertex(0, 2, false); 
    mg.addVertex(1, 2, false); 
    mg.addVertex(3, 2, false); 
    mg.addVertex(0, 0, false); 


    mg.g.resize(mg.vertices.size()); 

    mg.g[0].push_back(5); 
    mg.g[0].push_back(6); 

    mg.g[1].push_back(2); 
    mg.g[1].push_back(3); 
    mg.g[1].push_back(6); 

    mg.g[2].push_back(1); 

    mg.g[3].push_back(2); 
    mg.g[3].push_back(4); 
    mg.g[3].push_back(5); 
    mg.g[3].push_back(6); 

    mg.g[4].push_back(3); 
    mg.g[4].push_back(5); 

    mg.g[5].push_back(0); 
    mg.g[5].push_back(3); 
    mg.g[5].push_back(4); 

    mg.g[6].push_back(0); 
    mg.g[6].push_back(1); 
    mg.g[6].push_back(3); 


    // expected path: 6,0,5,3 
    mg.visited = new bool[mg.vertices.size()]{false}; 

    std::vector<int> pppath; 
    std::cout << mg.dfs(6, -1) << std::endl; 

    for (auto n : mg.path) 
    { 
     std::cout << n << ","; 
    } 

    return 0; 

} 

Answer 1

Merci de votre participation. Le problème a été résolu. Le push_back doit arriver une ligne plus tard dans la boucle for. Néanmoins, le code a le problème que la liste d'adjacence doit être créée sur un certain ordre pour éviter de revenir directement au point de départ.