图这种数据结构，在实际场景中被经常使用，也是笔者在上学时最不愿意”触摸”的并觉得特别高深莫测的理论，这里让我们一步步去剖析图这种数据结构。

图的几种表示方法

Edge List（弧表示法）

这种方法就是将图表示成为｜E｜edge的List或array，这里的list或array我们称之为edge list。为了表示一个edge，我们可以采用只具备两个参数的array，例如下面的表示方法：

  1. [ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],
  2. [3,8], [4,5], [4,9], [7,8], [7,9] ]

如果edge是有权重的，我们只需要为每个array添加上一个参数作为权重即可。
这种表示方法简单，但是如果我们想要去知道图中是否包含特定的edge的时候，我们需要去搜索整个edge list。

Adjacency Matrices（邻接矩阵法）

假设一个图中有V个点，那么采用Adjaceny Matrices的方法，就需要建立起一个VxV的0，1矩阵。row=i，column=j的地方为1的话表示edge（i，j）存在于图中，如果edge（i，j）有权重，那么只需要在edge（i，j）处填写上相应的权重值。这种图的长的就如下图一样
image.png
具体的表示方法是

[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

这种表示法非常简单、直接。但是，在邻接矩阵的所有 个元素中，只有 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。

Adjacency list

Adjacency list采用了adjacency matrices和edge list相结合的方式。对于每一个vertex i，存储其相对应的vertices adjacent。

image.png
其表示方法为

[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]

实际应用

在解决图的问题时，经常采用的方法还是BFS和DFS的方法，以下列举出几道图的力扣的问题。

207. 课程表

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]

输出: true

解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]

输出: false

解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

提示：

输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。

你可以假定输入的先决条件中没有重复的边。

1 <= numCourses <= 10^5

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/course-schedule

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先是我自己对于这道题的解法，效率并不是十分的高，基本思路就是要确保没一个点都不会回到其自身，在具体的实施过程中，是分别对每一个进行判断，如果期间过程中可能的小环路，暂且忽略，只要确保不是回到自身就可。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        if(numCourses == 0 || numCourses == 1)
            return true;

        map<int,vector<int>>graph;


        //make Adjacency list graph
        for(auto &index : prerequisites)
        {
            graph[index[0]].push_back(index[1]);
        }

        for(int i = 0; i < numCourses; i++)
        {
            stack<int>dfs;
            vector<bool>flag(numCourses, false);
            dfs.push(i);

            while(!dfs.empty())
            {
                int tmp  = dfs.top();
                dfs.pop();
                if(flag[tmp] == true)
                {
                    if(tmp == i)
                        return false;
                    else
                        continue;
                }
                else
                    flag[tmp] = true;

                vector<int>tmpvec = graph[tmp];

                for(auto &val : tmpvec)
                    dfs.push(val);
            }
        }

        return true;
    }
};

现在贴出来别人对于这道题的解法
BFS
BFS uses the indegrees of each node. We will first try to find a node with 0 indegree. If we fail to do so, there must be a cycle in the graph and we return false. Otherwise we set its indegree to be -1 to prevent from visiting it again and reduce the indegrees of its neighbors by 1. This process will be repeated for n (number of nodes) times.

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g = buildGraph(numCourses, prerequisites);
        vector<int> degrees = computeIndegrees(g);
        for (int i = 0; i < numCourses; i++) {
            int j = 0;
            for (; j < numCourses; j++) {
                if (!degrees[j]) {
                    break;
                }
            }
            if (j == numCourses) {
                return false;
            }
            degrees[j]--;
            for (int v : g[j]) {
                degrees[v]--;
            }
        }
        return true;
    }
private:
    typedef vector<vector<int>> graph;

    graph buildGraph(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g(numCourses);
        for (auto p : prerequisites) {
            g[p.second].push_back(p.first);
        }
        return g;
    }

    vector<int> computeIndegrees(graph& g) {
        vector<int> degrees(g.size(), 0);
        for (auto adj : g) {
            for (int v : adj) {
                degrees[v]++;
            }
        }
        return degrees;
    }
};

DFS
For DFS, in each visit, we start from a node and keep visiting its neighbors, if at a time we return to a visited node, there is a cycle. Otherwise, start again from another unvisited node and repeat this process. We use todo and done for nodes to visit and visited nodes.

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g = buildGraph(numCourses, prerequisites);
        vector<bool> todo(numCourses, false), done(numCourses, false);
        for (int i = 0; i < numCourses; i++) {
            if (!done[i] && !acyclic(g, todo, done, i)) {
                return false;
            }
        }
        return true;
    }
private:
    typedef vector<vector<int>> graph;

    graph buildGraph(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph g(numCourses);
        for (auto p : prerequisites) {
            g[p.second].push_back(p.first);
        }
        return g;
    }

    bool acyclic(graph& g, vector<bool>& todo, vector<bool>& done, int node) {
        if (todo[node]) {
            return false;
        }
        if (done[node]) {
            return true;
        }
        todo[node] = done[node] = true;
        for (int v : g[node]) {
            if (!acyclic(g, todo, done, v)) {
                return false;
            }
        }
        todo[node] = false;
        return true;
    }
};

参考资料

https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs
https://blog.csdn.net/woaidapaopao/article/details/51732947