图算法遇到的问题

问题列表

• 星型图的中心点?
• 图中是否存在环, 图中是否存在冗余连接, 如何找出冗余连接?
• 有向图中的环, 有向图去掉冗余变成树?
• 无向图中所有的环?
• 图中任意两个点是否相连?
• 图中不相连的块有几个?
• 图中最长路径是哪个?
• 以哪个节点为根可以得到高度最低的树?
• 拓扑排序?
• 无根树转为有根树?
• 最小生成树?
• 单源最短路径?
• 多源最短路径?
• 欧拉图, 一笔画成?
• 二分图?
• 连通分量?
• 有向无环图从节点 A 到 B 的所有可能路径?
• 强联通分量
• 双拓扑排序
• 桥(Tarjan算法)

寻找可能路径

广度优先搜索

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        queue<vector<int>> q;
        vector<int> v;
        v.push_back(0);
        q.push(v);
        while(! q.empty()){
            int size = q.size();
            for(int i =0; i < size; i++){
                vector<int> cur = q.front();
                q.pop();
                int id = cur[cur.size() - 1];
                if(id == graph.size() - 1){
                    ans.push_back(cur);
                    continue;
                }
                for(int next : graph[id]){
                    vector<int> tmp = cur;
                    tmp.push_back(next);
                    q.push(tmp);
                }
            }
        }
        return ans;
    }
};

之前一直以为广度优先搜索只能对节点进行入列和出列, 但是上面那个是对路径进行出列和入列, 比较巧妙, 代码也很简洁. 对节点进行出列和入列也能实现, 就是麻烦点:

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        unordered_map<int, vector<vector<int>>> m;
        queue<int> q;
        q.emplace(0);
        m[0] = {{0}};
        int endVertex = graph.size() - 1;
        vector<vector<int>> res;

        vector<int> visited(graph.size(), 0);

        while(! q.empty()) {
            int len = q.size();

            for (int i = 0; i < len; ++i) {

                int currVertex = q.front();
                q.pop();

                for (int j = 0; j < graph[currVertex].size(); ++j) {

                    int adjacentVertex = graph[currVertex][j];
                    vector<vector<int>> newPath(m[currVertex]);
                    for (auto &np: newPath) {
                        np.push_back(adjacentVertex);
                    }

                    if (adjacentVertex == endVertex) {
                        res.insert(res.end(), newPath.begin(), newPath.end());
                    } else {
                        m[adjacentVertex].insert(m[adjacentVertex].end(), newPath.begin(), newPath.end());
                        q.push(adjacentVertex);
                    }
                }

                m.erase(currVertex);
            }
        }

        return res;
    }
};

深度优先搜索

class Solution {
public:

    void dfs(int start, int end, vector<int>& path, vector<vector<int>>& res, vector<vector<int>>& graph) {
        if (start == end) {
            res.push_back(path);
            return;
        }

        for (auto& counterpart : graph[start]) {
            path.push_back(counterpart);
            dfs(counterpart, end, path, res, graph);
            path.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> res;
        vector<int> path;
        path.push_back(0);
        dfs(0, graph.size()-1, path, res, graph);
        return res;
    }
};

本文来自：https://blog.duhbb.com

本文链接地址：图算法遇到的问题，英雄不问来路，转载请注明出处，谢谢。

有话想说：那就赶紧去给我留言吧。