Java Program to Find the Number of Provinces

“省份数量”问题涉及查找表示为无向图节点的城市组。一个城市组，或称省份，包括直接或间接连接的城市。这个 Java 程序使用深度优先搜索 (DFS) 或并查集等算法来高效地识别和计数这些连通分量。

示例

输入

表示城市连接的 4x4 邻接矩阵

1 1 0 0

1 1 0 0

0 0 1 1

0 0 1 1

输出

2 个省份。

解释

2 个省份的输出表示两个连接的城市组。第一组由城市 0 和 1 组成，而第二组由城市 2 和 3 组成。这两个组完全隔离，形成两个不同的省份。

深度优先搜索 (DFS) 遍历方法

算法

步骤 1：初始化跟踪结构： 创建一个大小为 n（城市数量）的已访问 数组，初始化为 false。此数组用于跟踪已探索过的城市。将 provinceCount 变量设置为 0，用于计算省份数量。

步骤 2：遍历每个城市： 循环遍历所有城市（0 到 n-1）。如果一个城市未被访问，则表示发现了一个新省份。

步骤 2.2：处理已处理的城市： 在开始 DFS 之前，检查该城市是否已被标记为已访问。如果城市已被访问，则表示它已属于先前发现的省份，因此无需再次为该城市启动 DFS。跳过已标记为已访问的任何城市的 DFS 步骤。

步骤 3：使用 DFS 探索连接： 从当前城市开始深度优先搜索 (DFS)。在 DFS 过程中，将当前城市标记为已访问。探索与当前城市直接连接的所有城市。对于每一个未访问的连接城市，递归地执行 DFS。

步骤 3.1：跟踪连接的城市： 在 DFS 遍历过程中，维护一个列表或计数器，用于记录当前省份中已访问的所有城市。这有助于理解哪些城市属于同一个省份，并确保该连通分量中的所有城市都被标记为已访问。一旦当前城市的 DFS 完成，该连通分量中的所有城市都已计算在内。

步骤 4：计算省份： 在完成一个城市及其连接城市的 DFS 后，将 provinceCount 加 1，表示已找到一个完整的省份。

步骤 4.1：优化不连接的城市： 在 DFS 过程中标记一个城市及其连接城市为已访问后，添加一个检查以识别完全不连接的城市（在邻接 矩阵 中没有连接的城市）。如果一个城市未连接到任何其他城市，则将其视为自己的省份。

步骤 5：为剩余城市重复： 继续遍历所有城市。对于已访问的城市，跳过 DFS 步骤。

步骤 5.1：处理边缘情况： 完成所有城市的迭代后：检查由于邻接矩阵中缺少连接而仍未访问的城市。确保算法能够优雅地处理空矩阵或单个城市等情况，并返回正确的省份数量（分别为 0 或 1）。

步骤 6：返回结果： 循环完成后，返回 provinceCount 作为省份总数。

让我们在 Java 程序中实现上述方法。

文件名：NumberOfProvinces.java

输出

 
2   

复杂度分析

时间复杂度

时间复杂度为 O(n²)，其中 n 是城市的数量。这是因为邻接矩阵有 n² 个元素。每个城市都被访问一次。DFS 检查该城市的所有连接，由于遍历期间的嵌套迭代，导致总体二次方复杂度。

空间复杂度

空间复杂度为 O(n)，其中 n 是城市的数量。这包括用于跟踪已探索过的城市的 visited 数组，以及 DFS 的递归调用栈，在最坏情况下其深度可达 n。邻接矩阵本身已作为输入提供。

方法 2：并查集算法

算法

步骤 1：初始化父节点和秩数组： 父节点数组：每个城市最初都是自己的领导者。因此，每个城市的父节点最初都是它自己。这有助于跟踪每个城市所属的集合（或省份）。

parent[i] = i 对于每个城市 i。

秩数组：此数组通过将较小的树附加到较大的树上来优化联合操作，从而减小树的深度。这确保了并查集结构保持平衡。

rank[i] = 1 对于每个城市 i。

步骤 2：联合城市： 我们遍历邻接矩阵 (isConnected[i][j]) 以检查哪些城市已连接。如果两个城市 i 和 j 已连接（即 isConnected[i][j] == 1），我们执行联合操作将它们分组到同一个集合（省份）中。联合操作通过更新其根（领导者）城市来合并两个集合。目标是将两个城市链接起来，使它们共享同一个领导者。

按秩合并： 此步骤确保将较小的树附加到较大树的根上，以保持平衡结构。

步骤 3：查找每个城市的根： 为了确定一个城市属于哪个集合，我们使用查找操作。此操作会跟踪城市的父节点（领导者），最终到达其集合的根（即其父节点是它自己的城市）。

路径压缩： 在查找操作期间，我们通过使每个城市直接指向其根来优化结构。这会减小树的深度，从而加快将来的查找操作。

步骤 4：计算唯一省份的数量： 处理完所有城市后，我们需要计算存在多少个唯一的集合（省份）。一个省份是由共享同一根的城市定义的。要计算唯一的省份，我们为每个城市执行查找操作，并计算有多少个唯一的根（领导者）。

步骤 5：返回结果： 唯一根的总数对应于省份的数量。这是我们的最终结果，它告诉我们存在多少个不连接的城市组（省份）。

文件名：NumberOfProvinces.java

输出

 
2   

复杂度分析

时间复杂度

并查集方法的近似时间复杂度为 O(n²)，其中 n 是城市的数量。这是因为我们需要处理具有 n² 个元素的邻接矩阵。由于路径压缩和按秩合并，联合和查找操作的时间复杂度接近常数。

空间复杂度

并查集方法的空间复杂度为 O(n)，其中 n 是城市的数量。这包括父节点数组和秩数组所需的空间，每个数组的大小都为 n。此外，邻接矩阵作为输入提供，这也占用了空间，但不属于算法的复杂度。

使用 BFS 方法

算法

步骤 1：初始化： 给定一个表示城市及其连接的邻接矩阵。我们需要跟踪哪些城市已被访问，以避免重复计算同一个省份。为此，我们使用一个 visited 数组，其中每个元素都表示一个城市是否已被访问。

步骤 1.1：开始计算省份： 我们初始化一个 provinceCount 变量为 0。此变量将用于跟踪我们找到的省份数量。

步骤 2：遍历每个城市： 我们循环遍历图中的每个城市。如果一个城市尚未被访问，则表示我们遇到了一个新的省份，因此我们从该城市开始执行 BFS 来探索这个新省份。

步骤 3：从当前城市执行 BFS： 对于每个未访问的城市，我们启动 BFS 搜索。BFS 算法探索与起始城市直接或间接连接的所有城市（从而识别整个连通分量）。在 BFS 过程中，我们在 visited 数组中标记每个已访问的城市。

步骤 3.1：跟踪连接的城市： 在 BFS 遍历过程中，我们维护一个队列来探索与起始城市连接的所有城市。每次我们从队列中取出一个城市时，我们都会在 visited 数组中将其标记。这确保属于同一省份的城市被分组在一起，并且不会在将来的 BFS 遍历中被重新访问。每个城市都被处理一次，确保高效地探索省份内的所有直接和间接连接。

步骤 4：探索所有连接： BFS 使用队列。我们入队起始城市，并开始探索其所有连接的城市。每次我们从队列中取出一个城市时，我们都会检查其连接。如果一个城市已连接（即邻接矩阵中存在 1）并且尚未被访问，我们会将其入队并标记为已访问。

步骤 5：增加省份计数： 在完成一个城市的 BFS 遍历（及其所有连接的城市）后，我们将 provinceCount 加 1，因为我们找到了一个新省份。

步骤 6：为所有城市重复： 我们继续处理所有城市。如果一个城市已被访问，则跳过该城市的 BFS，因为它属于先前发现的省份。

步骤 7：返回结果： 遍历完所有城市后，provinceCount 的值将代表图中省份（连通分量）的总数。然后我们返回 provinceCount。

让我们在 Java 程序中实现上述方法。

文件名：NumberOfProvinces.java

输出

 
2   

复杂度分析

时间复杂度

程序的 time complexity 为 O(n²)，其中 n 是城市的数量。这是因为对于每个城市，我们都使用邻接矩阵检查它与其他所有城市的关系，这会导致每个城市进行 O(n) 次检查，从而导致总体复杂度为 O(n²)。

空间复杂度

程序的 space complexity 为 O(n)，其中 n 是城市的数量。这包括用于 visited 数组的空间，该数组用于跟踪哪些城市已被探索。此外，BFS 中使用的队列在最坏情况下需要与城市数量成比例的空间。