c++ - 未加权有向图 dfs_iterator operator++ C++

Question

我正在构建图形（未加权，定向）类，该类接受dfs_iterator并bfs_iterator具有++移动到下一个值、*获取当前顶点==和!=比较顶点的操作。我正在用 C++ 实现代码。图形类是使用邻接列表实现的，它具有私有成员和vector<VType> vertices成员vector<list<size_t>> adj_list函数、、、、、add_vertex(vertex)等add_edge(index1, index2)，并且在图形类中remove_edge(index1, index2)，我实现了执行、、、、操作的类。下面是我试图实现的代码。get_vertex(index)has_edge(index1, index2)get_neighbors(index)dfs_iterator++*==!=

class graph {
private:
   std::vector<VType> vertices;
   std::vector<std::list<std::size_t>> adj_list;
public:
//... other member function implementations ...//
  class dfs_iterator {
  private:
        std::vector<std::list<std::size_t >> adjList;     // to hold the adj_list of graph class 
        std::vector<VType> vertexProp;               //to hold the vertices of graph class
        std::size_t index;                                // to keep track of current index
        std::list<std::size_t>::iterator li_it;           // to handle the list of each adjList[index]
  public:
     dfs_iterator(std::vector<std::list<std::size_t >> adj_list_, std::vector<VType> vertex_props_, std::size_t start_idx) {
            this->adjList = adj_list_;
            this->vertexProp = vertex_props_;
            this->index = start_idx;
            this->li_it = adjList[index].begin();

        };

        VType &operator*() {
            return vertexProp[index];
        };

        dfs_iterator &operator++() {               // explanation in the description below
            if (this->li_it != adjList[index].end()) { // iterating over the depth until we hit the leaf with zero elements
               this->index = *li_it;              // jumping to index of list element
               li_it = adjList[index].begin();    // changing the li_it to new list
            } else {                             
              /*  have to handle the cases where we hit the end and search from a new branch of the parent and keep doing all the possible paths are closed. */
            }
            return *this;
        };
    };

    dfs_iterator dfs_begin(std::size_t vertex_idx) {
        return dfs_iterator(adj_list, vertices, vertex_idx);
    };

    dfs_iterator dfs_end(std::size_t vertex_idx) {
        return dfs_iterator(adj_list, vertices, vertex_idx);;
    };
  }
}

现在，我的*操作按预期工作，但++操作员几乎没有问题。如果我的邻接列表如下所述：

**index. list_of_neighbours/edges**
   0. {4, 2, 6, 8}
   1. {3, 5}
   2. {}
   3. {7}
   4. {3}
   5. {}
   6. {}
   7. {8}
   8. {}

在做

    string delim = "";
    for (auto it = graph.dfs_begin(0); it != graph.dfs_end(8); ++it) {
        cout << delim << *it;
        delim = " -> ";
    }
    cout << "\n";

我的输出是：

Traversing the graph in depth first fashion:
0 -> 4 -> 3 -> 7

正如预期的那样。但是，如果在第0th 索引中，而不是{4, 2, 6, 8}我的邻居列表是{2, 4, 6, 8}，那么我operator++在检查 index 中的列表时2，它已经死了，它应该退出进一步进行并从第 th 索引的2nd 项目开始0，即4和 dfs 0 -> 4 -> 3 -> 7。

我正在寻找任何可以帮助我进一步进行的建议或提示。打开以回答进一步的查询。

标签： c++graphdepth-first-search