种类

• 有向图

  

• 无向图

  

• 无权图

  

• 加权图

  

基本概念

• 度 与点相连边的个数

  有向图分 出度（出边数）入度（入边数）

• 路径

存储

二维数组

使用二维数组存储点与边

邻接表

使用Vector存储 适合描述点多边少的图

在图论和计算机科学中，**邻接表（英语：adjacency list）**是表示了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集。

如果是无向图，那么每条边由两个结点组成，分别代表边的两个端点；如果是有向图，那么每条边是一个结点对，分别代表边的始点和终点。

图的遍历

Graph traversal

拓扑排序

DFS算法

using Graph = vector<vector<int>>;  // 邻接表

struct TopoSort {
  enum class Status : uint8_t { to_visit, visiting, visited };

  const Graph& graph;
  const int n;
  vector<Status> status;
  vector<int> order;
  vector<int>::reverse_iterator it;

  TopoSort(const Graph& graph)
      : graph(graph),
        n(graph.size()),
        status(n, Status::to_visit),
        order(n),
        it(order.rbegin()) {}

  bool sort() {
    for (int i = 0; i < n; ++i) {
      if (status[i] == Status::to_visit && !dfs(i)) return false;
    }
    return true;
  }

  bool dfs(const int u) {
    status[u] = Status::visiting;
    for (const int v : graph[u]) {
      if (status[v] == Status::visiting) return false;
      if (status[v] == Status::to_visit && !dfs(v)) return false;
    }
    status[u] = Status::visited;
    *it++ = u;
    return true;
  }
};