0

iterator隣接リストで表されるグラフ用のC++ の実装に行き詰まっています。したがって、イテレータはDFS アルゴリズムを使用してグラフを通過する必要があるという考えです。例として、++ のイテレータは、現在の頂点の次の未訪問の頂点に移動します (単純な 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*この (現在の) 頂点に反復 (++) された頂点へのポインター
    (現在の頂点から戻るため)。私はそれに名前を付けますgraph_vertex* predecessor_vertex;

  • graph_vertex*successor() および predecessor() 関数。次/前の (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;

    正しい方法で考えると、dfs_iterator の++andを取得しました--( ++/-- のオーバーロードされた関数は、イテレーターに格納されている現在の頂点の successor() / predecessor() を返します (そしてもちろん、marked現在の頂点のフラグを変更します) )

しかし、状況に対処する方法がわかりません。ユーザーが 1 つのグラフに対して多数の反復子を作成すると、フラグが正しく応答しないgraph_vertexため、情報が破損markedします (1 つの反復子はそれを変更できますが、2 つ目はこの頂点を反復処理できません)。 . 頂点ではなく、各反復子に特殊なフラグvectorを格納する必要がありますか? markedまたは、この情報を何らかの方法で複製してgraph_vertexフラグを立てますか? この iterator の他の演算子をオーバーロードする必要がありますか?

私のコードとそのような実装に関するヒントを教えてください。私は正しい方法で考えていますか？

// 実際には、そのようなグラフ イテレータに関する情報を見つけることができず、C++ は初めてです。

4

1 に答える 1

2

アルゴリズムに関連するものはすべて、グラフではなくイテレータにある必要があります。より正確には、イテレータはグラフの状態を変更すべきではありません。constグラフで使用されるイテレータについて考えてみてください。イテレータでいくつかのデータ構造を使用することを妨げるものは何もありません。たとえば、素朴なアプローチは置き換えることです

bool marked; // for DFS

イテレータ自体のマップによってクラスの頂点に。

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

于 2013-05-07T13:05:15.393 に答える