使用 BFS 在图中查找岛屿

引言

图是表示边和节点排列的基本数据结构。它们用于许多不同的领域，例如计算机网络和社交网络。在图论中，查找图中的孤岛是一个有趣的话题。在讨论图时，孤岛通常被称为连通分量或子图，其中每个节点都可以从其他所有节点访问。

广度优先搜索 (BFS) 是一种图遍历算法，它逐层探索图中的每个顶点。在进入下一层顶点之前，BFS 从指定的源顶点开始探索其邻居。由于此特性，BFS 适用于确定两个节点之间的最短路径或识别网络中的连通分量等任务。想象一下，一个由连接节点组成的网络被表示为一个图。在这种情况下，孤岛是相互连接但不连接到组外节点的节点集合。在这样的图中，我们可以使用 BFS 来探索和标记相关组件，以确定孤岛的数量。

代码

输出

代码解释

图示

• 该图在代码中表示为邻接列表。Graph 结构包括一个链表数组 (adjacencyList) 和顶点数 (numVertices)。数组的每个元素表示一个顶点，与其对应的链表记录了与其相邻的顶点。

节点创建

• Node 结构表示链表中的一个节点。建立具有指定数据值的新节点的任务由 createNode 函数完成。

图的构建

• 使用 createGraph 函数初始化一个具有预定顶点数的新图。分配图结构的内存，并使用 NULL 指针初始化邻接列表。

添加边

• 通过 addEdge 函数在两个顶点之间添加一条无向边。它通过在源和目标顶点处生成新节点来更新邻接列表。

广度优先搜索 (BFS)

• BFS 函数从指定的顶点 (startVertex) 开始并遍历 BFS。它逐层搜索相邻顶点，并使用队列跟踪已访问的顶点。先进先出 (FIFO) 原则指导遍历。

主函数

• 在 main 函数中构建了一个具有五个顶点的图，并添加边以显示顶点之间的连接。为了跟踪在 BFS 期间是否已访问过某个顶点，请使用 visited 数组。

孤岛识别

• 随后，主函数遍历所有顶点并对每个未探索的顶点执行 BFS。对于发现的每个连通分量（孤岛），将按照 BFS 期间访问的顺序打印顶点。

时间和空间复杂度

广度优先搜索 (BFS) 算法影响给定 C 代码的时间复杂度。在最坏的情况下，当所有顶点和边都被探索时，时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。这是因为 BFS 遍历每个顶点和边一次。在代码的特定示例中，其中顶点数由 V 表示，边数由 E 表示，时间复杂度可以认为是 O(V + E)。

用于实现 BFS 和描述图的数据结构在很大程度上决定了空间复杂度。图的邻接列表表示需要 O(V + E) 空间，其中 V 表示顶点数，E 是边数。BFS 队列是额外空间复杂度的来源，在最坏的情况下，其最大大小可能为 V。由于 BFS 遍历和图表示所需的空间，代码的总体空间复杂度为 O(V + E)。