关于邻接表的问题

Question

//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).老师您能不能给一个小数据量来跑一遍？

Answer 1

liuyubobobo 2021-04-11 17:48:53

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

继续加油！：）

• 提问者 慕移动9586716 #1

  老师，如果有0-1-2 这个图。三个节点，两条边。使用 hasEdge 可以看到：
  "hasEdge(0, 1) 返回 true"这个不应该是g[v].size() ==1,此时for( int i = 0 ; i < g[v].size() ; i ++ )，只循环了一遍，即：g[0][0] ==w,如果再循环就是：1 < 1(不满足条件）所以hasEdge(0, 1）不应该是返回Flase嘛？
  是我的理解不对嘛？

• liuyubobobo 回复 提问者 慕移动9586716 #2

  g[0] 里有一个元素，所以 g[0].size() == 1。g[0] 里的这个元素就是 1没所以 g[0][0] == 1。所以直接返回了 true。用代码实际运行这个测试用例试试看？

• 提问者 慕移动9586716 回复 liuyubobobo #3

  老师，邻接表是由多个链表组成的吧，所以这里的g[v][i] ==w;   i是自增的，这是对链表访问的形式，是这样理解的吧？

点开查看后面1条评论