0

我坚持iterator为图形实现 C++，它由邻接表表示。所以，我的想法是我的迭代器应该使用DFS 算法遍历图形。例如，for ++ 迭代器转到当前顶点的下一个未访问的顶点（就像在简单的 DFS 中一样）。

我的图顶点和迭代器模板很简单：

template < typename VType, typename EType >
struct vertex {
    typedef vertex < VType, EType > graph_vertex;
    vertex (string _name, VType _v_data): name(_name), v_data(_v_data) { }
    typedef pair < graph_vertex* , EType > ve;  

    vector <ve> adj; //adjacency list [ graph_vertex, edge_value ]
    string name;    
    VType v_data;
    bool marked;  // for DFS
};

template < typename VType, typename EType >
class dfs_iterator {
    public:
        dfs_iterator();
        dfs_iterator( graph_vertex* start );
        ~dfs_iterator();
        dfs_iterator(const dfs_iterator& that);

        dfs_iterator& operator = (const dfs_iterator& that) {
            val = that.val;
        }
        dfs_iterator& operator ++ () { } // read down
        dfs_iterator& operator -- () { } // read down
        VType operator * () { return val->v_data; };

        bool operator == (const dfs_iterator& that) const { return val == that.val; }
        bool operator != (const dfs_iterator& that) const { return !(*this == that); }
    private:
        graph_vertex* val;
    };

我认为的事情：

在struct vertex应该是：

  • 指向graph_vertex*顶点的指针，它被迭代（++'ed）到
    这个（当前）顶点（从当前顶点返回）。我会命名graph_vertex* predecessor_vertex;

  • successor() 和前任() 函数，它们将返回指向graph_vertex*下一个/上一个（用于 DF 搜索）顶点的指针。

    pseudocode successor(CURR_VERT):
    for every graph_vertex VERT in CURR_VERT->ADJ LIST do {
           if ( VERT not marked )
                return VERT;
           return successor (predecessor_vertex);
    }
pseudocode predecessor(CURR_VERT):
     return CURR_VERT->predecessor_vertex;

    如果我以正确的方式思考，现在我得到了一个++and--用于我的 dfs_iterator （++/-- 的重载函数应为存储在迭代器中的当前顶点返回 successor()/previous() （当然，更改marked当前顶点的标志)

但我不明白如何处理这种情况，当用户为一个图创建大量迭代器时，graph_vertex信息将损坏，因为marked标志将无法正确响应（一个迭代器可以更改它，然后第二个无法迭代此顶点） . 我应该在每个迭代器中而不是在顶点中存储特殊vector的标志吗？marked或以某种方式复制此信息以graph_vertex标记？我应该为此迭代器重载其他一些运算符吗？

请给我一些关于我的代码和此类实现的提示。我的想法正确吗？

// 实际上，我找不到有关此类图形迭代器的任何信息，而且我是 C++ 新手。

4

1 回答 1

2

与算法相关的所有内容都应该在迭代器中，而不是在图中。更准确地说，您的迭代器不应修改图的状态。想想你在const图表上使用的迭代器。没有什么能阻止您在迭代器中使用少量数据结构。例如，一种天真的方法是替换

bool marked; // for DFS

通过迭代器本身的映射在您的类顶点中。

std::map<struct vertex*, bool> visited_vertices

于 2013-05-07T13:05:15.393 回答