关于邻接表的问题

首页课程实战体系课手记专栏慕课教程

关于邻接表的问题

来源：7-2 图的表示

慕移动9586716

2021-04-11

//bobo老师您好！
// 验证图中是否有从v到w的边
bool hasEdge( int v , int w ){

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

    for( int i = 0 ; i < g[v].size() ; i ++ ) //(1).这里的g[v].size()是指一共有多少条边嘛？
        if( g[v][i] == w )  //(2).这里我不能理他这样做的目的是什么？
            return true;
    return false;
}

(3).老师您能不能给一个小数据量来跑一遍？

写回答

1回答

liuyubobobo

liuyubobobo

2021-04-11

1）

g[v].size() 表示和 v 链接的变有多少个。

2）

g[v][i] == w 说明 v 和 w 是相连的。

3）

我没有特别理解你想要什么数据。任意一个图都可以。

比如：

0-1-2 这个图。三个节点，两条边。你应该使用 hasEdge 可以看到：

hasEdge(0, 1) 返回 true

hasEdge(1, 0) 返回 true

hasEdge(1, 2) 返回 true

hasEdge(2, 1) 返回 true

hasEdge(0, 2) 返回 false

hasEdge(2, 0) 返回 false

继续加油！：）

1

4

liuyubobobo

回复

慕移动9586716

我没有理解你说的什么叫 i是自增的；什么叫"对链表访问的形式"。邻接表可以由多个链表组成。课程中的代码是由多个动态数组构成的（vector）。第四小节开始，我们就会实际从文件中读取数据来创建一个图，届时可以使用这个数据实际运行，来理解这个代码。

2021-04-13

共4条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

关于邻接矩阵和邻接表

回答 1

关于添加和删除

回答 1

邻接矩阵和邻接表

回答 1

老师，邻接表不考虑边的重复添加嘛

回答 1

关于图的邻接表实现

回答 1

打开慕课网App查看更多内容