Advertisement

算法在图论中用于计算连通分量的数量(DFS、BFS、并查集)

阅读量:

题目:. - 力扣(LeetCode)

共有 n 个城镇,其中部分城镇之间存在直接联系,而另一些则不存在直接联系。若城镇 a 与城镇 b 存在直接连接,并且城镇 b 与城镇 c 同样存在直接连接,则城镇 a 与城镇 c 之间通过中间节点形成间接联系。

所谓省份,指的是由若干个相互之间通过直接或间接方式连接的城镇组成的一个集合,该集合内部不包含任何未与其他成员建立连接的城镇。

现提供一个大小为 n x n 的矩阵 isConnected ,其中矩阵中的元素 isConnected[i][j] = 1 表示第 i 个城镇与第 j 个城镇之间存在直接连接关系,而当 isConnected[i][j] = 0 则表示这两个城镇之间没有直接连接。

请计算该矩阵中所包含的省份总数。(即求解图结构中连通分量的数量)

深度搜索方法解析

对所有城市依次进行访问,当遇到尚未被访问的城市时,以该城市为起点开展深度优先搜索。借助矩阵 isConnected\textit{is

全部评论 (0)

还没有任何评论哟~