基本概念

图的基本概念

图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

图是一个二元组$G=(V(G),E(G))$，其中 $𝑉(𝐺)$ 是非空集，称为点集或阶，对于$V$中的每个元素，我们称其为 顶点 (vertex) 或 节点 (node)，简称点；$E(G)$为$V(G)$各结点之间边的集合，称为 边集 (edge set)。

常用$G=（V，E）$表示图。

图的种类

有向图、无向图和混合图

有向图指图中的边是有方向的，无向图则反之。如果一个图中既有无向边，也有有向边，则称为混合图。

若$G$为无向图，则$E$中的每个元素为一个无序二元组$(u,v)$。

若$G$为有向图，则$E$中的每个元素为一个有序二元组组$(u,v)$。设组$e=u→v$，则此时$u$称为$e$的起点（tail），$v$称为$e$的终点（head），$e$也叫做弧。

边通常用箭头表示，而箭头是从「尾」指向「头」的。

因此，起点是 tail，终点是 head。

加权图（赋权图）

即图中的边具有权值，也分为加权有向图和加权无向图。

如果所有的权值都是正数，也可以叫做正权图。

有限图和无限图

当$V$或$E$是无限集合时，称图为无限图；当$V$或$E$都是有限集合时，称图为有限图。

度

与一个顶点$v$关联的边的条数称作该顶点的 度 (degree)，记作$d(v)$。特别地，对于边 $(v,v)$，则每条这样的边要对 $𝑑(𝑣) $产生$2$的贡献。

在无向图中，连接该节点的边的条数即为该顶点的度数。

在有向图中，分为出度和入度，分别表示从该顶点出发的边的条数，和指向该节点的边的条数。

由度衍生出了以下概念：

孤立点：若$𝑑(𝑣) =0$，则称$v$为 孤立点 (isolated vertex)

叶节点（悬挂点）：若 $𝑑(𝑣) =1$，则称$v$为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)。

偶点：若 $2|d(v)$，则称 $v$ 为 偶点 (even vertex)

奇点：若$2 ∤𝑑(𝑣)$，则称$v$为 奇点 (odd vertex)。图中奇点的个数是偶数（详见握手定理)。

相邻

对于无向图，如果两个顶点间有边相连，则称这两个点是相邻的，而这条边分别和这两个点关联。其中，一个顶点的邻域是所有与它相邻的顶点构成的集合，记作$N(v)$；一个点集$S$的的邻域是所有与$S$中至少一个点相邻的点构成的集合，记作$N(S)$：

\[N(S) = \bigcup_{v \in S} N(v)\]

对于有向图，相邻的概念划分得更加具体。给定有向图中的边$e=u→v$：

对于$u$，我们称$u$邻接于$v$，这表示$u$是起点，是$v$的入邻点。
对于$v$，我们称$v$从$u$邻接，这表示$v$是终点，是$u$的出邻点。

对于邻点，入邻点的集合通常记作$N^-(v)$，出零点的集合通常记作$N^+(v)$。

简单图

若一个图中不存在自环和重边，则称其为简单图。

根据鸽巢原理，至少有两个顶点的简单无向图中，一定存在度相同的点。

自环

对于$E$中的边$e=(u,v)$，若$u=v$，则$e$被称作一个自环（Loop）。

自环即两个顶点是同一个点的边，尽管在理论看来定义它似乎多此一举，但它在实践中存在意义，如在状态机中表示状态不变。

重边

若$E$中存在两条完全相同的边，则它们是一组重边。

路径

途径：途径（Walk）是连接一连串顶点的边的序列，可以是有限或无线长度。

通常来说，途径的长度是组成途径的边的数量；如果是赋权图，则是边的权值之和。

迹：如果组成一条途径的边均不重复，则称这条途径为迹（Trail）。

路径：如果一条迹连接的所有点中没有重复的，则称这条迹是路径（Path）。

回路：如果一条迹的长度为k，连接的端点集合$V$中有$v_0=v_k$，则称这条迹是一条回路（circuit）。

环：对于一条回路，如果$v_0=v_k$是集合$V$中唯一重复出现的点对，则称这条回路是一个环。

子图

对于图$G=（V，E）$，若存在另一张图$H=(V',E')$满足$V' ⊆V$且$E'⊆E$，则称$H$是$G$的子图。

导出子图（诱导子图）

若$H$是$G$的子图，$E'$包含且仅包含$E$中两个顶点都在$V'$中的边，则称$H$是$G$的导出子图。

导出子图由点决定，即在已知原图$G$和导出子图的点集$V'$的情况下，就可以确定$E'$。

生成子图（支撑子图）

若$H$是$G$的子图，且$V=V'$，则称若$H$是$G$的生成子图。

显然，对于任意图$G$都有：$G$是自身的子图、支撑子图和导出子图。

连通性

对于有向图和无向图，连通性的定义有所区别。

无向图

对于无向图$G=（V，E）$，其中$u,v∈𝑉$，若存在一条途径使得$v_0=u$，$v_k=v$，则称$u$和$v$是连通的。

如果无向图$G$满足任意两个顶点均连通，则称$G$是连通图，称$G$具有连通性。

若$H$是$G$的一个连通子图，且不存在连通图$F$满足$𝐻 ⊊𝐹 ⊆𝐺$，则称$H$是$G$的一个连通分量（极大连通子图）。

有向图

对于有向图$G=（V，E）$，其中$u,v∈𝑉$，若存在一条途径使得$v_0=u$，$v_k=v$，则称$u$可达$v$的。

如果有向图$G$满足任意两个顶点均两两互相可达，则称$G$是连通图，称$G$是强连通的。

如果有向图$G$不是强连通的，但将所有边替换为无向边后，得到一张连通图，则称$G$是弱连通的。

和无向图一样，有向图有弱连通分量（极大弱连通子图），和强连通分量（极大强连通子图）。

图的存储

在代码中，一般使用邻接表、邻接矩阵或类表示。

在本篇中，规定$n$表示图的端点数目，$m$表示图的边数目，$d^+(u)$表示点$u$的出度。

朴素存储

参考代码

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
  int u, v;
};

int n, m;
vector<Edge> e;
vector<bool> vis;

bool find_edge(int u, int v) {
  for (int i = 1; i <= m; ++i) {
    if (e[i].u == u && e[i].v == v) {
      return true;
    }
  }
  return false;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = 1; i <= m; ++i) {
    if (e[i].u == u) {
      dfs(e[i].v);
    }
  }
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1, false);
  e.resize(m + 1);

  for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v;

  return 0;
}

朴素存储即直接存边，使用一个数组存储所有的边，每个元素包括边的起点、终点和权值（如果存在）。

朴素存储的复杂度如下：

查询是否存在某条边：$O(m)$
遍历一个点的所有出边：$O(m)$
遍历整张图：$O(nm)$
空间复杂度：$O(m)$

朴素存储的遍历效率较低，通常不会使用。

邻接矩阵

参考代码

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<bool>> adj;

bool find_edge(int u, int v) { return adj[u][v]; }

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int v = 1; v <= n; ++v) {
    if (adj[u][v]) {
      dfs(v);
    }
  }
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1);
  adj.resize(n + 1, vector<bool>(n + 1));

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u][v] = true;
  }

  return 0;
}

邻接矩阵使用$n \cdot n$的二维数组表示图结构，这是从节点的角度来表示图的思路。

其中，g[u][v]为1表示存在$u$到$v$的边，为0表示不存在。如果是带边权的图，可以在g[u][v]中存储$u$到$v$的边权。

邻接矩阵的复杂度如下：

查询是否存在某条边：$O(1)$
遍历一个点的所有出边：$O(n)$
遍历整张图：$O(n^2)$
空间复杂度：$O(n^2)$

邻接矩阵只适用于没有重边（或重边可忽略）的情况，显著优点是查询某条边只需要$O(1)$时间。

邻接矩阵在稀疏图上表现较差，空间浪费的问题非常严重，因此一般只会在稠密图上使用。

邻接表

参考代码

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<vector<int>> adj;

bool find_edge(int u, int v) {
  for (int i = 0; i < adj[u].size(); ++i) {
    if (adj[u][i] == v) {
      return true;
    }
  }
  return false;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i]);
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1);
  adj.resize(n + 1);

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
  }

  return 0;
}

邻接表使用数组+vector来表示图结构：使用一个数组存储所有点，数组的每个元素是一个存储对应点出边的vector。

邻接表的复杂度如下：

查询是否存在某条边：$O(d^+(u))$，如果事先进行了排序就可以使用做到$O(\log (d^+(u))$
遍历一个点的所有出边：$O(d^+(u))$
遍历整张图：$O(m+n)$
空间复杂度：$O(m)$

邻接表在点数较少的图中需要快速查询一条边是否存在时，表现较为劣势，这种情况可以使用邻接矩阵。

除此以外，邻接表是一种较为通用的方法，尤其适用于需要对一个点的所有出边进行排序的场合。

链式前向星

参考代码

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<bool> vis;
vector<int> head, nxt, to;

void add(int u, int v) {
  nxt.push_back(head[u]);
  head[u] = to.size();
  to.push_back(v);
}

bool find_edge(int u, int v) {
  for (int i = head[u]; ~i; i = nxt[i]) {  // ~i 表示 i != -1
    if (to[i] == v) {
      return true;
    }
  }
  return false;
}

void dfs(int u) {
  if (vis[u]) return;
  vis[u] = true;
  for (int i = head[u]; ~i; i = nxt[i]) dfs(to[i]);
}

int main() {
  cin >> n >> m;

  vis.resize(n + 1, false);
  head.resize(n + 1, -1);

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    add(u, v);
  }

  return 0;
}

链式前向星本质是链表实现的邻接表，使用链表存储每个点的出边。

链式前向星的复杂度如下：

查询是否存在某条边：$O(d^+(u))$
遍历一个点的所有出边：$O(d^+(u))$
遍历整张图：$O(m+n)$
空间复杂度：$O(m)$

链式前向星的缺陷在于不能快速询问一条边是否存在，也不能在方便地对一个点的出边进行排序。

链式前向星依赖一个存储每个点的入口（即其出边链表的首个节点）的整型数组和一个存边的结构体数组实现。
其中，结构体的定义如下：

struct Edge{
    int to;   //这条边的终点在点数组中的索引
    int next;  //同一起点的上一条边在边数组中的索引
    int w;    //（如果存在）这条边的权重
}edge[MAXM];    

其中edge的大小由题目规定的边的最大数目决定。

对于无向图，edge数组的大小应该开到边的最大数目*2。

为了便于存储，定义以下方法新增边：

void add_edge(int u,int v,int w){
    //u表示边的起点，v表示边的终点，w表示边的权值（如果存在
    cnt++;   //cnt是边的总数目，也是当前边的索引；
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].w=w;
    head[u]=cnt;
}

对于无向图，应该调用两次add_edge()方法，即add_edge(u,v)和add_edge(v,u)。

需要注意，cnt和head都应该手动初始化为$0$ :

int head[MAXM];
memset(head,0,sizeof(head));

int cnt=0;

遍历出边时，方法和遍历链表一致：

// 遍历点 u 的所有出边
for (int i = head[u]; i != 0; i = edge[i].next) {
    int v = edge[i].to;
    int weight = edge[i].w;
    // 在这里处理边 (u, v)
}

树的基本概念

主要概念见树基础 - OI Wiki，此处只整理其它理论的前置或引用内容。

生成树

生成树是一个针对连通图的特定子图，它保留了原图的所有点，同时保证没有任何环。

其中，最小生成树仅针对带边权的图，指在所有生成树中边权和最小的一个。

推论与定理

握手定理

给定任意图$G=（V，E）$，由于图每条边实际上都由两个顶点连接而成，因此任意图的度数之和必定为$2E$，奇点的个数必定为偶数，记作：

\[∑deg(V)=2|E|\]