[数据结构与算法]leetcode-图

797-所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

方法一：图的深度优先搜索

我们可以使用深度优先搜索的方式求出所有可能的路径。具体地，我们从 0号点出发，使用栈记录路径上的点。每次我们遍历到点 n?1，就将栈中记录的路径加入到答案中。

特别地，因为本题中的图为有向无环图（DAG），搜索过程中不会反复遍历同一个点，因此我们无需判断当前点是否遍历过。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> stk;

    void dfs(vector<vector<int>>& graph, int x, int n) {
        if (x == n) {
            ans.push_back(stk);
            return;
        }
        for (auto& y : graph[x]) {
            stk.push_back(y);
            dfs(graph, y, n);
            stk.pop_back();
        }
    }

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

1. 时间复杂度：O（n×2^n），其中n为图中点的数量。我们可以找到一种最坏情况，即每一个点都可以去往编号比它大的点。此时路径数为 O(2^n)，且每条路径长度为 O(n)，因此总时间复杂度为 O(n×2^n)。
2. 空间复杂度：O（n），其中n 为点的数量。主要为栈空间的开销。注意返回值不计入空间复杂度。

207-课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

方法一：深度优先搜索

看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。
具体来说，我们首先可以把课程看成「有向图」中的节点，节点编号分别是 0, 1, …, numCourses-1，把课程之间的依赖关系看做节点之间的有向边。

比如说必须修完课程 1 才能去修课程 3，那么就有一条有向边从节点 1 指向 3。

所以我们可以根据题目输入的 prerequisites 数组生成一幅类似这样的图：

如果发现这幅有向图中存在环，那就说明课程之间存在循环依赖，肯定没办法全部上完；反之，如果没有环，那么肯定能上完全部课程。
算法步骤如下：

1.构建邻接表
2.遍历图中每一个节点
3.判断是否存在环

class Solution {
public:
    vector<vector<int>>edges;
    bool hasCycle=false;
    vector<bool>visited;
    vector<bool>onPath;
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        buildGraph(numCourses,prerequisites);
        visited.resize(numCourses,false);
        onPath.resize(numCourses,false);
        for(int i=0;i<numCourses;++i)
        {
            traverse(edges,i);
        }
        return !hasCycle;
    }
    //建表
    void buildGraph(int numCourses, vector<vector<int>>& prerequisites)
    {
        edges.resize(numCourses);
         for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
        }
    }
    //遍历图
    void traverse(vector<vector<int>>&edges,int s)
    {
        if(onPath[s])
            hasCycle=true;
        if(visited[s]||onPath[s])
            return;
        visited[s]=true;
        onPath[s]=true;
        for(auto x:edges[s])
            traverse(edges,x);
        onPath[s]=false;

    }
};

1. 时间复杂度: O(n+m)，其中n 为课程数，m 为先修课程的要求数。这其实就是对图进行深度优先搜索的时间复杂度。
2. 空间复杂度: O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)。在深度优先搜索的过程中，我们需要最多O(n) 的栈空间（递归）进行深度优先搜索，因此总空间复杂度为O(n+m)。