邻接矩阵和邻接表

Question

波波老师，您好，问题在问号处。

1

// 向图中添加一个边
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;//这行代码表示什么意思？是不是说，纵向的边的编号w,横向的起始顶点的编号v,对应的元素=true,这个true表示相连

    m ++;
}

2 

// 向图中添加一个边
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 )//为什么要有v!=w这个判断呢？
        g[w].push_back(v);//w表示边，那么g[w]是不是表示这条边对应顶点v？而这个顶点是不是起始顶点呢

    m ++;
}

Answer 1

liuyubobobo 2019-10-27 13:56:49

1

表示顶点v和顶点w之间有边

2

如果没有这个判断，假设有自环边，这个自环边将存两次。比如如果1到1之间有自环边，没有 v != w 的判断的话，g[1]中就会存两个1，这是不对的。

不过，由于这个课程只处理简单图，不会有自环边，所以没有这个判断也没关系。

3

w 不表示边，w 表示顶点。g[v] 中包括 w，表示 v-w 两个顶点相连，即 v-w 之间存在边。

对于无向图，边没有起始点终止点的区分，因为没有方向，所以 g[v]中有w，g[w]中有v。

请再仔细理解一下邻接矩阵和邻接表的定义。我们的代码都是在实现原理。请一定要搞明白下面两页的 ppt，邻接矩阵为什么是这样的，邻接表为什么是这样的：

继续加油！

• 提问者 我有明珠一颗 #1

  非常感谢！