赞
踩
只要存在环,就不是一个数。
进行 BFS 遍历。
定义一个二维数组 graph[][] 用来存储边的信息,如 graph[2][7] 表示结点 2 和结点 7 之间存在边。
定义一个一维数组 visited[] 用来存储结点已处理信息,如 visited[3] = true,表示结点 3 已经处理过。
从结点 0 开始进行 BFS,假设当前遍历到的结点为 cur:
1、visited[cur] = true 标记当前结点已处理;
2、找出 cur 的所有邻接结点;
3、依次把 cur 和邻接结点的边都给去掉,同时把邻接结点也设置为 true。
如果在第 3 步之前,发现 cur 的一个邻接结点的 visited[naborNode] 已经为 true ,说明存在环。
解释:如果 visited[naborNode] 为 true,说明 naborNode 是前面某个结点的邻接节点,而 cur 也是前面某个节点的邻接节点,加上 cur 和 naborNode 又是连在一起的,于是形成了环。
BFS 结束后,如果是合法的树结构,此时应该已经处理完所有节点,如果还存在某个节点 visited[node] == false,说明连通分量不为 1。
class Solution { public boolean validTree(int n, int[][] edges) { //构建邻接矩阵 int[][] graph = new int[n][n]; //有边的元素设置为1,没有边的元素设置为0 for (int[] edge : edges) { // graph[3][4] == 1 表示 3 和 4 是连接的 graph[edge[0]][edge[1]] = 1; graph[edge[1]][edge[0]] = 1; } //进行BFS Queue<Integer> queue = new LinkedList<>(); //从第一个节点开始搜索,这样就不会漏掉无边图的情况 queue.add(0); boolean[] visited = new boolean[n]; while (!queue.isEmpty()) { Integer cur = queue.poll(); visited[cur] = true; //获取邻接点 for (int i = 0; i < n; i++) { //查看当前节点的邻接点 if (graph[cur][i] == 1) { if (visited[i]) { // cur 的邻接节点居然被处理过 // 说明 cur 和 i 在前面有一个共同的父结点 // 加上 cur 和 i 又是连在一起的 // 说明存在环 return false; } visited[i] = true; //涂黑访问过的节点 graph[cur][i] = 0; graph[i][cur] = 0; queue.add(i); } } } //判断是否为单连通分量 for (int i = 0; i < n; i++) { if (!visited[i]) { // 居然还有一个节点没有被访问过,说明不是图 return false; } } return true; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。