检测周期并使用dfs进行打印

Question

我试图从给定顶点开始检测并在无向路径中打印循环。到目前为止，路径被记录在一个向量中。该代码似乎工作，但还有一个顶点报告比它应该是。

对于给定的例子，一个预期的路径是：-1,6,0,5,3，它们也输出：-1,6,0,5,3,2，但是还有一个顶点比预期的更多。

也许有人有一个想法如何解决这个问题。

在此先感谢！

#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循环后面发生一行。尽管如此，代码存在的问题是必须按照某个顺序创建邻接列表以避免直接跳回到起点。