算法练习——省份数量

2021年1月7日每日一题为547. 省份数量,这一题是关于图结构的算法,题设难度为中等,该题主要是要找出不相连的节点数量,一组相连或者间接相连的节点为一个省份,因此我们需要遍历这个图即可,无论是深度优先还是广度优先都能够实现。这题如果理解了深度优先和广度优先算法将会变得非常简单,题解里面包含了深度优先遍历和广度优先遍厉以及并查集方法,下面附上题解和代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int findCircleNum(int[][] isConnected) {
// 找到相连的点,利用广度优先遍历
boolean[] visit = new boolean[isConnected.length];
int ret = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(0);
for (int i = 0; i < isConnected.length; i++) {
if (!visit[i]) {
queue.offer(i);
// 遍历相连节点 [xxx]
while (!queue.isEmpty()) {
int j = queue.poll();
visit[j] = true;
for (int k = 0; k < isConnected.length; k++) {
if (isConnected[j][k] == 1 && !visit[k]) {
queue.offer(k);
}
}
}
ret++;
}
}
return ret;
}
}

在做这题的时候刚开始没有理解到这个省份的意思,只是想到这里要用图的遍历算法,于是写下了上述代码中到[xxx]部分,一方面没理解到题述省份的意思,另一方面对图的遍历算法不熟悉,在学习图的时候也是仅仅过了一遍,大概跟着学习资料理解了一下思路,很有必要再去回顾一下图和树的遍历算法,感觉对于今后的练习帮助会比较大。