algorithm - 无向图中的连通分量数

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 列表的约定。如果我看到您的 adj 列表，我会假设该图是定向的。

Answer 2

您可以更改邻接列表表示，您的表示是“有向的”，但您的图片是无向的。对于边（a，b）图{a：[b]，b：[a]}