323. 无向图中连通分量的数目

难度: 中等

来源: 无向图

---

你有一个包含 n 个节点的图。给定一个整数 n 和一个数组 edges ，其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。

返回 图中已连接分量的数目 。

示例 1:

输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
输出: 2

示例 2:

输入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
输出:  1

提示：

• 1 <= n <= 2000

• 1 <= edges.length <= 5000

• edges[i].length == 2

• 0 <= ai <= bi < n

• ai != bi

• edges 中不会出现重复的边

class Solution {
    public int countComponents(int n, int[][] edges) {

    }
}

分析与题解

---

• 深度优先搜索DFS

  这个题目是无向图的入门级别的题目, 一共有两种解法, 一个是深度优先搜索DFS; 一个是广度优先搜索BFS.

  这里先说一下深度优先搜索DFS.

  首先, 我们需要先构建图的邻接表 adj. 其实也就是构建一个二维数组,用来表示各个点直接的关系.

  

  代码如下所示.

  List<Integer>[] adj = new ArrayList[n];
  for(int i = 0; i < n; i++) {
      adj[i] = new ArrayList<Integer>();
  }
  // 需要进行双向添加,才能构建一个完整的邻接表
  for(int[] line : edges) {
      adj[line[0]].add(line[1]);
      adj[line[1]].add(line[0]);
  }
  

  然后, 我们就需要使用深度优先搜索DFS, 对邻接表中的每一个子数组进行深度递归搜索, 一边搜索同时需要一边记录已经搜索过的节点. 直到把这条边上的所有点都搜索完成即可.

  int components = 0;
  int[] visited = new int[n];
  
  ...
  
  for(int i = 0; i < n; i++) {
      if (visited[i] == 0) {
          components++;
          dfs(adj, visited, i);
      }
  }
  

  private void dfs(List<Integer>[] adjList, int[] visited, int startNode) {
      visited[startNode] = 1;
      int length = adjList[startNode].size();
      for(int i = 0; i < length; i++) {
          if(visited[adjList[startNode].get(i)] == 0) {
              dfs(adjList, visited, adjList[startNode].get(i));
          }
      }
  }
  

  整体的解题思路如下所示.

  class Solution {
      public int countComponents(int n, int[][] edges) {
          int components = 0;
          int[] visited = new int[n];
  
          List<Integer>[] adj = new ArrayList[n];
          for(int i = 0; i < n; i++) {
              adj[i] = new ArrayList<Integer>();
          }
          for(int[] line : edges) {
              adj[line[0]].add(line[1]);
              adj[line[1]].add(line[0]);
          }
          for(int i = 0; i < n; i++) {
              if (visited[i] == 0) {
                  components++;
                  dfs(adj, visited, i);
              }
          }
          return components;
      }
  
      private void dfs(List<Integer>[] adjList, int[] visited, int startNode) {
          visited[startNode] = 1;
          int length = adjList[startNode].size();
          for(int i = 0; i < length; i++) {
              if(visited[adjList[startNode].get(i)] == 0) {
                  dfs(adjList, visited, adjList[startNode].get(i));
              }
          }
      }
  }
  

  
  

  复杂度分析:

  • 时间复杂度: O(n)
  • 空间复杂度: O(n), 需要构建已经标记已经查询过的节点数组, 还有一个就是邻接表数组, 长度都是与图的数组成线性关系.

  结果如下所示.