一直没好好刷刷 Graph 的题目，从Leetcode graph 套餐第一个题 310. Minimum Height Trees 开始吧。

题目

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

任何一个节点都可以当做root,问那个节点当root的时候，树最低。

基础版BFS

看到题目，第一个想法，就是把所有的节点都当做root跑一遍，看看高度，然后把高度最低的记下来。

使用 pair<int,int> 保存节点，第一个是节点，第二个是当前的深度。

class Solution {
public:
    int min_heigh(int n,int now, vector<unordered_set<int>> adj) {
        // pair 节点 据定点的距离
        pair<int, int > last = {-1,-1};
        queue<pair<int,int>> Q;
        vector<int> visited(n,0);
        
        Q.push({now,0});

        while(!Q.empty()){
            pair<int, int> v = Q.front();
            visited[v.first] = 1;
            Q.pop();

            // BFS 用queue
            for (int p : adj[v.first]) {
                if (visited[p] == 0) {
                    Q.push({ p,v.second + 1 });
                    last = { p,v.second + 1 };
                }
            }
        }
        return last.second;
    }

    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<int> used, min_group;
        vector<unordered_set<int>> adj(n);
        for (auto p : edges) {
            adj[p.first].insert(p.second);
            adj[p.second].insert(p.first);
        }
        int min = INT_MAX;
        for (int i = 0; i < n; i++) {
            used = {i};
            // 第i个点的高度
            int temp_i = min_heigh(n,i, adj);
            if (temp_i <= min) {
                if (temp_i < min) {
                    min = temp_i;
                    min_group.clear();
                }
                min_group.push_back(i);
            }
        }
        return min_group;
    }
};

本算法大概通过了56/65，然后就超时了....

应该是因为很多节点的高度被重复计算，所以应该换个思路来做。

BFS升级版

dicuss1
dicess2

目测 dicuss1 的思路就是 dicuss2

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        if (n == 1) {
            return{ 0 };
        }
        vector<int> leaves;
        vector<unordered_set<int>> adj(n);
        for (pair<int, int> p : edges) {
            adj[p.first].insert(p.second);
            adj[p.second].insert(p.first);
        }

        for (int i = 0; i < adj.size(); ++i) {
            if (adj[i].size() == 1) {
                leaves.push_back(i);
            }
        }
        // BFS the graph
        while (n>2) {
            n -= leaves.size();
            vector<int> newLeaves;
            for (int node : leaves) {
                for (int neighbor : adj[node]) {
                    adj[neighbor].erase(node);
                    if (adj[neighbor].size() == 1) 
                        newLeaves.push_back(neighbor);
                }
            }
            leaves = newLeaves;
        }
        return leaves;
    }
};

仔细思考一下这个问题，直观的回答这个问题，找出图中最长的路径，那么这条路径最中间的那一个或者那两个(长度可能是偶数)，就是答案。

但是找最长的路径，其实是一个np问题，很难直接算，第一个算法就尝试直接计算...所以直接超时了..

另外一个思路就是，从叶子开始，一圈一圈的，把最外边那一层的叶子扒掉，最后剩下的2个或者1一个，就是答案了。

这里有两种写法：
第一种就是不断剥离外边那一层，直到剩下最中间的，然后被删掉。
整个树被删光之前，留下的就是我们想要的答案。

while (true) {
    vector<int> newLeaves;
    for (int node : newLeaves) {
        for (int neighbor : adj[node]) {
            adj[neighbor].erase(node);
            if (adj[neighbor].size() == 1)
                leaves.push_back(neighbor);
        }
    }
    if (leaves.empty())
        return newLeaves;
    newLeaves = leaves;
}

还有目前用的郑重

while (n>2) {
    n -= leaves.size();
    vector<int> newLeaves;
    for (int node : leaves) {
        for (int neighbor : adj[node]) {
            adj[node].erase(neighbor);
            if (adj[neighbor].size() == 1) 
                newLeaves.push_back(neighbor);
        }
    }
    leaves = newLeaves;
}

本文由 mmmwhy 创作，最后编辑时间为: Sep 11, 2018 at 07:53 pm