图的表示方法：
邻接表
邻接矩阵

有向图/无向图/带权重的图

图的遍历模板：

可以用dfs和bfs来遍历，跟树或者其他的遍历是一样的。只不过需要借一个标志位来记录遍历过的点

// 记录被遍历过的节点, 以防止有环图的遍历死机
bool[] visited;
// 记录从起点到当前节点的路径
bool[] onPath;

/* 图遍历框架 */
def traverse(Graph graph, int s)：
    if visited[s]：
        return;

    visited[s] = true;

    onPath[s] = true;
    for neighbor in graph.neighbors(s):
        traverse(graph, neighbor)
    
    onPath[s] = false;

代码跟回溯很像。毕竟都属于dfs系列的。

797. 所有可能的路径

这是一个无向图，所以不需要visited来标记。

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> onePath;
        tranverse(0, onePath, graph);
        return ret;
    }
    void tranverse(int index, vector<int>& onePath, vector<vector<int>>& graph) {
        onePath.push_back(index);
        if (index == graph.size() - 1) {
            ret.push_back(onePath);
        }

        for (auto item : graph[index]) {
            tranverse(item, onePath, graph);
        }
        onePath.pop_back();
    }
private:
    vector<vector<int>> ret;
};

有向图的环检测

我们以207. 课程表为例子。这个题目要求课程有先修的要求，问是否能够完成课程。实际上这个题目如果把每个课程当作节点，依赖关系作为边，那么就是问图是否存在环而已。因此可以直接套用图的遍历模板来解决这个问题。

首先我们要把问题转换为图，可以转换为邻接表或者邻接矩阵
然后调用模板遍历，看onPath是否有访问过的点，如果有，则说明有环
剪枝的条件，如果点遍历过，那么就不需要再遍历一遍了，如果已经有环的存在了，就直接返回了。

class Solution {
public:
    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto& edge : prerequisites) {
            int from = edge[1];
            int to = edge[0];
            graph[to].push_back(from);
        }
        return graph;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 构造图
        vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
        // 遍历图
        vector<bool> visited(numCourses);
        vector<bool> onPath(numCourses, false);
        for (int i = 0; i < numCourses; i++) {
            tranverse(i, graph, onPath, visited);
            if (isCycle) {
                return !isCycle;
            }
        }
        return true;
    }
    void tranverse(int index, vector<vector<int>>& graph, vector<bool>& onPath, vector<bool>& visited) {
        if (onPath[index] == true) {
            isCycle = true;
        }
        if (visited[index] || isCycle) {
            return;
        }
        visited[index] = true;
        onPath[index] = true;
        for (auto item : graph[index]) {
            tranverse(item, graph, onPath, visited);
        }
        onPath[index] = false;
    }
private:
    bool isCycle = false;
};

这个题目还有一种方式是拓扑排序的方式，这个在拓扑排序的章节会通过210. 课程表 II题目来说明。

对于图的遍历，有dfs和bfs两种方式。上面的所有方式都是dfs的，那么bfs能够处理呢？

利用bfs来处理有向图的方式，需要借助入度，出度的概念。

所谓入度：有向图中某点作为图中边的终点的次数之和。

所谓出度：有向图中某点作为图中边的起点的次数之和。

我们首先找到入度为0的点A，如果找不到，那么必然是有环的图。然后遍历A点的所有子节点，将其子节点的入度减一，然后重复查找入度为0
的点，重复上面的操作。最后如果没有入度为0的点，则说明存在环，如果所有的点都遍历完毕，说明不存在环。

下面我们用bfs的算法来解决207. 课程表的问题

首先创建图graph，并初始化每个节点的入度
然后将所有入度为0的点push到队列中
依次弹出入度为0的点，然后将其所有的子节点入度-1
再次将入度为0的点push到队列中，递归处理完所有的节点
检查每个点的入度，如果有点的入度不等于0，则说明存在环

class Solution {
public:
    vector<vector<int>> buildGrap(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto edge : prerequisites) {
            graph[edge[1]].push_back(edge[0]);
        }
        return graph;
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph = buildGrap(numCourses, prerequisites);
        vector<int> indegree(numCourses);
        for (auto edge : prerequisites) {
            indegree[edge[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        int count = 0;
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            count++;
            for (auto item : graph[curr]) {
                indegree[item]--;
                if (indegree[item] == 0) {
                    q.push(item);
                }
            }
        }
        if (count == numCourses) {
            return true;
        }
        return false;
    }
};