无向图中的连通分量数

Question

我正在讨论一些图形算法(这不是功课;我只是在研究算法和数据结构)并且我有一个问题.假设我有以下无向图:

var graph = {
    9: [19, 26],
    13: [19, 5],
    17: [],
    26: [11, 18],
    18: [9],
    19: [],
    23: [24],
    24: [],
    11: [],
    18: []
};

该图基本上如下所示:

此图表中有多少个连接组件？从图中看,它看起来有3个组件.但是如果我实际上实现了算法(迭代每个顶点,并且如果该顶点未被发现则使用该顶点作为起始点来执行bfs .此外,bfs将标记它遇到的任何顶点,如发现的那样).

如果我开始9,我最终发现以下节点:[19, 26, 11, 18].但是,13由于它不在19邻接列表中,因此未被发现.但是,19在13邻接列表中.这就是我最终得到一个额外组件的原因.

它是否正确？实际上是否有4个单独的组件,如果是这样,我对连接组件的理解是错误的吗？

Answer 1

问题是，对于无向图的邻接表表示，您必须

(1)使用对称邻接表，即当放入新边时ab，添加b到，adjlist[a] 反之亦然

或者

(2) 每次寻找边的存在时，遍历所有顶点的邻接表。

由于 (2) 效率极低，因此您通常会选择 (1)。这也是一般使用的 adj 列表的约定。如果我看到你的调整列表，我会假设该图是有向的。