无向图中连通分量的数量

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个独立组件吗？如果是这样，我的连通分量的理解是否错误？

- Vivin Paliath

---

我想知道这个问题为什么会被踩...它非常合理。 - Vivin Paliath

该图表并不特别适合其他问题。 - Ind Oubt

Answer 1

问题在于对于无向图的邻接表表示，你必须要么使用对称的邻接表，即在插入新边ab时，将b添加到adjlist[a]中，并将a添加到adjlist[b]中；或者每次查找边的存在性时遍历所有顶点的邻接表。由于（2）效率极低，通常会选择（1）。这也是一般使用的邻接表约定。如果我看到你的邻接表，我会假设该图是有向的。

- us2012

Answer 2

你可以更改你的邻接表表示方式，你的表示是“有向”的，但你的图片是无向的。对于边（a,b）的图形 {a: [b], b:[a]}。

- marcadian