当前位置: 首页 > 工具软件 > p2p-graph > 使用案例 >

261. Graph Valid Tree

沙小白
2023-12-01

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

判断一个图是不是一颗树,这个问题就得转换为两个充要条件了:

        1. 图的vertex n 和边 edge必须满足 vertex -1 = edges

        2. 所有的vertex都必须联通的。

        第一点可以通过 vertex-1 == edges 来判断。

        第二个充要条件就得遍历图,并且记录下顶点数目来判断了。 而遍历图,基本都是用BFS的办法,和遍历树差不多,一层层的往下遍历。

       但是遍历图的时候有个和树不一样的点,无向图的边界(0, 1) 中0的邻居是1, 1的邻居是0. 当我们用遍历树的办法遍历图的时候,会发现很多节点重复遍历并有可能形成一个环。

    注意到这点,就得有个办法去记录已经遍历过的顶点,当遍历有个邻居A的邻居B已经被访问过了,就不用再去访问B了。

    步骤如下:

                        a) 用queue来记录访问的顶点,并依次的出队列。

                        b)每次出队列的顶点就得把该顶点的邻居节点push到队列里了。比如A的邻居是B,C,D,E

                             i). push 邻居节点到队列之前,必须检查下该顶点是不是已经访问过了。

                                        1)访问过了,那就调到下个邻居节点。

                                        2) 没有访问过,那么就push进队列。

                         c) 重复这个动作直到队列为空。

        这道题目有个小坑,没有给出每个顶点的邻居顶点。

        得把输入的二维数组转换下为顶点:邻居顶点的格式:

              1) 用一个unordered_map来表示顶点以及邻居顶点

                     比如: 0 {1, 2, 3}   2{0, 1}

      unordered_map<int , vector<int>>  constructGraph(vector<vector<int>>& edges) {
        unordered_map<int, vector<int>> graphic;
        
        for(auto &edge: edges) {
            graphic[edge[0]].push_back(edge[1]);
            graphic[edge[1]].push_back(edge[0]);
        }
        
        return graphic;
    }

拿到了想要的数据后,接下来就按照上述的步骤做。

        queue<int> myqueue;
        unordered_set<int> accessedVertex;
        vector<int> nodesInGraph;
        
        //unordered_map<int vertex, vector<int> neighbers>
        unordered_map<int , vector<int>> graph = constructGraph(edges);
        
        myqueue.push(graph.begin()->first);
        accessedVertex.insert(graph.begin()->first);
        
        while(!myqueue.empty()) {
            int vertex = myqueue.front();
            myqueue.pop();
            

            nodesInGraph.push_back(vertex);
            
            
            for(auto &neighber: graph[vertex]) {
                if(accessedVertex.find(neighber) != accessedVertex.end())
                    continue;
                else {
                    myqueue.push(neighber);
                    accessedVertex.insert(neighber);
                }
            }

最后拼接起来的代码如下:

class Solution {
public:
    unordered_map<int , vector<int>>  constructGraph(vector<vector<int>>& edges) {
        unordered_map<int, vector<int>> graphic;
        
        for(auto &edge: edges) {
            graphic[edge[0]].push_back(edge[1]);
            graphic[edge[1]].push_back(edge[0]);
        }
        
        return graphic;
    }
    
    bool validTree(int n, vector<vector<int>>& edges) {
        // Tree have two property 
        // 1. vertex n edge n-1
        // 2. every node must be connected
        if(n ==0)
            return false;
        
        if(edges.size() == 0 && n ==1)
            return true;
        
        if(edges.size() != n -1)
            return false;
        
        
        queue<int> myqueue;
        unordered_set<int> accessedVertex;
        vector<int> nodesInGraph;
        
        //unordered_map<int vertex, vector<int> neighbers>
        unordered_map<int , vector<int>> graph = constructGraph(edges);
        
        myqueue.push(graph.begin()->first);
        accessedVertex.insert(graph.begin()->first);
        
        while(!myqueue.empty()) {
            int vertex = myqueue.front();
            myqueue.pop();
            

            nodesInGraph.push_back(vertex);
            
            
            for(auto &neighber: graph[vertex]) {
                if(accessedVertex.find(neighber) != accessedVertex.end())
                    continue;
                else {
                    myqueue.push(neighber);
                    accessedVertex.insert(neighber);
                }
            }
        }
        
        return nodesInGraph.size() == n;
    }
};

总结下我犯的错误把

     1. 构建节点和邻居节点的时候按照有向图来构建了。 比如(0, 1)边,构建出来的邻居map应该是 顶点0的邻居是1, 同时顶点1的邻居是0. 我只考虑到了 顶点0的邻居是1,没有考虑到顶点1 的邻居也是0.

     2. 什么时候去检查邻居的顶点是不是已经访问过了。

            第一次检查的地方是顶点出队列的时候, 比如顶点A出队列,然后判断该顶点是不是已经访问过。 这样肯定是不对的,因为会造成队列里有很多重复的顶点在里面。

           正确的地方是元素入栈之前去检查,这样就能保证队列里的元素都是没有访问过的。

 类似资料:

相关阅读

相关文章

相关问答