对上一个问题的补充。

Question

补充： 我的意思是原本无权图DensGraph中，如果a和b相连，直接就return了，如下：

void addEdge( int v, int w )
{
    if( hasEdge( v, w ) )
        return;
    //...
}

而在这个基础上修改成有权图的时候，为什么不继续保持当v和w之间有边就直接返回，而是要先删除原来的边，然后再重新连上一条边：

void addEdge( int v, int w, Weight weight )
{
    if( hasEdge( v, w ) )
        delete g[v][w];
        if( !directed )
            delete g[w][v];
    m--;
    //...
}

我在自己写的时候，在Edge.h里面加入了一个change函数来修改边的权值。所以如果两个顶点之间已经有边的话，就替换成新的权值。如下

void addEdge( int v, int w, Weight weight )
{
    if( hasEdge( v, w ) )
    {
        g[v][w]->change( weight );
            if( !directed )
                delete g[w][v]->change( weight );
        return;
    }
    //...
}

最后，那个没有带模板参数的代码是在视频中的。

补充：那个先删除边的是在您课程的邻接矩阵里的。邻接表没有。这个不能回复真麻烦- -！

Answer 1

liuyubobobo 2017-07-11 01:15:18

大赞！你的思路是没有问题的。而且其实比先删除边再增加边的性能效率高。这是因为减少了内存操作！

btw: 你摘取的addEdge先删除边的代码是哪里摘的？我怎么记得我在这个课程里实现的有权图邻接表的实现是允许重边的？你的这两种实现，都建立在我们要处理的图，可能有重边，而我们的算法，不需要重边这样的基础！切记！

• 提问者 易萧 #1

  那个先删除边的代码是您视频里面的啊。文件里的我基本没看。都是照着您视频里面做的。非常感谢！