liuyubobobo老师，我想请问一下，关于addEdge函数。

Question

在addEdge函数中，不先判断一下v和w是否相等再进行下面的操作吗？g[v][w]=true;和g[v].push_back(w);中如果v和w相等的话不就相当于添加了自环边了吗？不知道是不是我理解有误。还有为什么要在稠密图中允许添加自环边，而在稀疏图中加上v!=w这句不允许添加自环边呢？先谢谢老师耐心的回答。：） 

SparseGraph类：  

  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 ++;

    }

DenseGraph类：

    void addEdge( int v , int w ){

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

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

        if( hasEdge( v , w ) )

            return;

        g[v][w] = true;

        if( !directed )

            g[w][v] = true;

        m ++;

    }

Answer 1

liuyubobobo 2018-02-01 12:04:15

方便起见，这个课程的代码中，是允许自环边的。只不过我们的测试用例的图，不包含自环边：）

在SparseGraph中，判断一下v != w，是为了不加入重边。如果v == w，并且我们不判断v != w，我们就会在g[v]这个vector中放入两个v（或者说在g[w]这个vector中放入两个w，因为v == w）；

但是在DenseGraph中没有这个问题，因为DenseGraph中g是一个二维数组。g[v][v]（或者g[w][w]）中只能放一个元素true或者false。如果v == w，赋值g[v][w] = true后再赋值g[w][v] = true，只是把这个位置的元素覆盖一下而已，不会加入重边。

当然在DenseGraph中判断一下v != w，也是完全可以的：）

• 提问者 路卍飞 #1

  非常感谢！

• 提问者 路卍飞 #2

  非常谢谢liuyubobobo老师！：）：）：）