サイクルを検出し、dfsを使用して印刷します

Question

私は、指定された頂点から開始して、無向パスでサイクルを検出して印刷しようとしています。今のところ、パスはベクトルに記録されています。コードは機能しているようですが、必要以上に頂点が1つ報告されています。

予想されるパスの1つは、-1,6,0,5,3で、-16,0,5,3,2が出力されますが、予想よりも1つ多い頂点があります。

おそらく誰かがこれをどのように修正できるか考えているかもしれません。

ありがとうございます！

#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

ありがとうございました。問題は解決されました。 push_backは、forループの後の行で発生する必要があります。それにもかかわらず、コードには、開始点に直接ジャンプすることを避けるために、特定の順序で隣接リストを作成する必要があるという問題があります。