稀疏图迭代器的时间复杂度及入参检测

来源：7-3 相邻结点迭代器

ych_1997

2021-06-25

稀疏图添加元素的代码如下，我们课程代码是允许添加平行边的（如果做限制就加大了时间复杂度）

private:
    int n, m;       // 节点数和边数
    bool directed;  // 是否为有向图

    // 向图中添加一个边
    void addEdge( int v, int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        g[v].push_back(w);
        if( v != w && !directed )
            g[w].push_back(v);

        m ++;
    }

addEdge(v, w) 参数可能存在以下可能

1） v = 0, v = 1;
2） v = 1, v = 0;
3） 1）及 2）任意重复输入

如果需要以下代码严格的O(E)复杂度，是不是需要控制入参类似0 1 组合仅能出现一次？我认为可以在读文件的时候进行合并0 1组合。亦或将O(E) 的复杂度的语义跟 O(m)既包含平行边的复杂度 统一起来即可。我理解的对吗？

    // O(E)
    for( int v = 0 ; v < N ; v ++ ){
        cout<<v<<" : ";
        SparseGraph::adjIterator adj( g1 , v );
        for( int w = adj.begin() ; !adj.end() ; w = adj.next() )
            cout<<w<<" ";
        cout<<endl;
    }