liuyubobobo老师，我想请问一下，关于addEdge函数。
来源：7-2 图的表示
路卍飞
2018-02-01
在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 ++;
}
1回答
-
方便起见，这个课程的代码中，是允许自环边的。只不过我们的测试用例的图，不包含自环边：）
在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，也是完全可以的：）
322018-02-01
相似问题