图论，从入门到出门（？

图论部分简介

图论 ( Graph theory) 是数学的一个分支，图是图论的主要研究对象。图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

参考资料

图论 - 维基百科

更加详细全面的算法竞赛图论知识汇总——图论 - OIwiki

图的基本概念

概述

图是由顶点的有穷非空集合和顶点之间边的集合组成的，通常用 G(V, E) 表示。其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。
~~（怎么这么晦涩难懂~~
通俗地来讲，图就是有一堆点，这些点之间有一些线连接。点就是顶点（Vertex），线就是边（Edge）。比如这样↓

这个图就是一个由 6 个顶点和 7 条边组成的图。

图论的基本术语

在图论中，有一些基本的术语，这些术语是理解图论的基础。

顶点的度：一个顶点的度是指与这个顶点相连的边的条数。对于无向图，顶点的度等于与这个顶点相连的边的条数；对于有向图，顶点的度等于以这个顶点为起点的边的条数。
顶点的入度：指以这个顶点为终点的边的条数。
顶点的出度：指以这个顶点为起点的边的条数。
路径：路径是指图中的一条边的序列，这条边连接了图中的一系列顶点。路径的长度是指路径上边的条数。
简单路径：简单路径是指路径中不包含重复顶点的路径。
边权：边权是指边上的权值。
点权：点权是指顶点上的权值。
环：环是指路径的起点和终点相同的路径。
无环图：一个图是无环图，当且仅当这个图不包含环。
自环：自环是指起点和终点相同的环。
有向无环图（DAG）：一个图是有向无环图，当且仅当这个图是有向图且不包含环。
连通图：如果图中任意两个顶点之间都存在路径，那么这个图就是连通图。
生成树：一个连通图的生成树是一个包含图中所有顶点的树，且包含图中所有顶点的最小连通子图。
最小生成树：一个连通图的最小生成树是一个包含图中所有顶点的树，且包含图中所有顶点的最小连通子图。
图的邻接矩阵：一个图的邻接矩阵是一个矩阵，矩阵的行和列分别对应图中的顶点，矩阵中的元素表示对应顶点之间是否有边。
图的邻接表：一个图的邻接表是一个表，表中的每一项对应图中的一个顶点，表中的每一项包含一个顶点和与这个顶点相连的顶点的列表。

（以下内容可以以后再了解）

连通分量：无向图的极大连通子图称为连通分量。
强连通图：如果有向图中任意两个顶点之间都存在路径，那么这个图就是强连通图。
强连通分量：有向图的极大强连通子图称为强连通分量。
森林：一个图的森林是一个不包含环的图。
有向树：一个有向图是有向树，当且仅当这个图是有向无环图且是强连通图。
无向树：一个无向图是无向树，当且仅当这个图是无向连通图且是无环图。
图的割点：一个图的割点是指去掉这个顶点后，图的连通度增加的顶点。
图的桥：一个图的桥是指去掉这条边后，图的连通度增加的边。
点双连通分量：一个图的点双连通分量是指一个图的极大点双连通子图。
边双连通分量：一个图的边双连通分量是指一个图的极大边双连通子图。
强连通分量：有向图的极大强连通子图称为强连通分量。
最短路径：一个图中两个顶点之间的最短路径是指这两个顶点之间的路径中边的权值之和最小的路径。
最短路径树：一个图中一个顶点到其他所有顶点的最短路径构成的树。

图的类型

图的类型有很多，常见的有：

无向图：边没有方向的图。
有向图：边有方向的图。
无向完全图：任意两个顶点之间都有边的无向图。
有向完全图：任意两个顶点之间都有方向的边的有向图。
无向简单图：没有重边和自环的无向图。
有向简单图：没有重边和自环的有向图。
无向连通图：任意两个顶点之间都有路径的无向图。
有向连通图：任意两个顶点之间都有路径的有向图。
无向树：无向连通图且无环的图。
有向树：有向连通图且无环的图。

~~（这俩内容加起来怎么这么多~~

图的存储方式

图的存储方式有很多，常见的有：

邻接矩阵：一个图的邻接矩阵是一个矩阵，矩阵的行和列分别对应图中的顶点，矩阵中的元素表示对应顶点之间是否有边。
代码 be like ↓
```
int G[MAXN][MAXN]; // 邻接矩阵
```
邻接矩阵的含义是，$G[i][j] = 1$ 表示顶点 $i$ 和顶点 $j$ 之间有边，$G[i][j] = 0$ 表示顶点 $i$ 和顶点 $j$ 之间没有边。如果图是带权图，那么$ G[i][j]$ 的值就是边的权值。例如，当边权值为 $w$ 时，$G[i][j] = w$。
邻接矩阵的优点是查询两个顶点之间是否有边的时间复杂度是 $O(1)$，缺点是存储空间复杂度是 $O(n^2)$，其中 $n$ 是顶点的个数。由于占用空间较大，邻接矩阵通常用于顶点较少的图，或者边的个数接近顶点个数的平方的图，也就是稠密图。 ~~实际做题时怎么方便建图怎么来（~~
具体使用其遍历图时be like ↓
```
//假如当前点是u
for (int v = 1; v <= n; v++) //n是顶点个数
{
  if (G[u][v])//u和v之间有边
  {
      // do something
  }
}
```
邻接表：一个图的邻接表是一个表，表中的每一项对应图中的一个顶点，表中的每一项包含一个顶点和与这个顶点相连的顶点的列表。
代码 be like ↓
```
vector<int> G[MAXN]; // 邻接表
```
邻接表的含义是，$G[i]$ 是一个列表，列表中的元素表示与顶点 $i$ 相连的顶点。换句话说，使用 vector 存储的邻接表是一个二维 vector 数组，其中第一维也就是 [MAXN] 所对应的这一维代表是哪个顶点，然后在这一行的 vector 后面紧跟着的元素就是这个点出去后可以到达的点。如果图是带权图，那么列表中的元素是一个 pair类型，pair 的第一个元素是顶点，第二个元素是边的权值。例如，当边权值为 $w$ 时，$G[i]$ 中的元素是 $(j, w)$。代码中的 vector<int>G[MAXN] 可以换成 vector<pair<int, int>>G[MAXN]，需要考虑的各种权值较多时，可以使用 struct 结构体来存储，实际做题时也比较常用。
邻接表的优点是存储空间复杂度是 $O(n + m)$，其中 $n$ 是顶点的个数，$m$ 是边的个数。由于占用空间较小，邻接表通常用于顶点较多的图，或者边的个数远小于顶点个数的图，也就是稀疏图，实际上还是取决于怎么方便处理问题怎么来。~~或者是无脑用邻接表~~
具体使用其遍历图时be like ↓
```
//假如当前点是u
for (int i = 0; i < G[u].size(); i++)
{
  int v = G[u][i];//v是u的一个邻接点
  // do something
}
```
当然作为基于 STL 的容器，vector 也可以使用迭代器来遍历，但是实际上并不常用，因为迭代器的写法比较繁琐，而且在图论中并不常用。~~（迭代器是什么？）~~
但是在我们亲爱的C++11标准中，引入了 for 循环的新写法，可以方便地遍历 vector，代码如下：
```
//假如当前点是u，使用其实现Dijkstra算法的松弛操作为例
for (auto v : G[u])
{
  if (dis[v.first] > dis[u] + v.second)
  {
      dis[v.first] = dis[u] + v.second;
      que.push({dis[v.first], v.first});
  }
}
```
链式前向星：链式前向星是邻接表的一种优化，链式前向星的优点是可以方便地处理有向图和无向图，以及有向图的反向图，在网络流问题中极为方便，并且由于不基于 STL 容器，常数较小，不过实际上差别不大。~~（真遇到毒瘤卡常题可以大骂出题人）（图论应该不会有卡常的吧不会吧不会吧）~~ ~~（图论还卡常疑似有些……）~~
代码 be like ↓
```
struct Edge {
  int to, next,val;
} edge[MAXN];
int head[MAXN], tot;
void init() {
  memset(head, -1, sizeof(head));
  tot = 0;
}
void addedge(int u, int v, int w) {
  edge[tot].to = v;
  edge[tot].val = w;
  edge[tot].next = head[u];
  head[u] = tot++;
}
```
链式前向星的含义是，head[i] 是一个指针，指向以顶点 $i$ 为起点的第一条边。edge[i].to 是一个顶点，表示边的终点。edge[i].next 是一个指针，指向以顶点 $i$ 为起点的下一条边。edge[i].val 是边的权值。
具体使用其遍历图时be like ↓
```
for (int i = head[u]; ~i; i = edge[i].next) //next是指向下一条边的指针
{
  int v = edge[i].to;//v是u的一个邻接点
  int w = edge[i].val;//v和u之间的边权
  // do something
}
```
~~（实在理解不了可以记住）~~
~~（记不住可以不用）~~
~~（等到了做题时遇到不得不用链式前向星的情况而自己又不会的时候，以后就记住了）~~
~~（但是这种情况也不算常见）~~

图的遍历

图的遍历是指从图中的一个顶点出发，访问图中所有顶点的过程。图的遍历有两种方式：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）：深度优先搜索是一种用于遍历或搜索树或图的算法。从图中的一个顶点出发，沿着一条路径一直走到底，直到不能再走为止，然后回溯到上一个节点，再走另一条路径，直到所有的顶点都被访问过。深度优先搜索通常使用递归的方式实现。
广度优先搜索（BFS）：广度优先搜索是一种用于遍历或搜索树或图的算法。从图中的一个顶点出发，先访问这个顶点，然后访问这个顶点的所有邻接点，再访问这些邻接点的所有邻接点，依次类推，直到所有的顶点都被访问过。广度优先搜索通常使用队列的方式实现。

对于基于三种方式建图的图，深度优先搜索和广度优先搜索的代码如下：

bool vis[MAXN];//vis是一个bool数组，表示顶点是否被访问过

$DFS$ be like ↓

//邻接表be like ↓
void dfs(int u)
{
    vis[u] = true;
    for (int i = 0; i < G[u].size(); i++)//可以用auto
    {
        int v = G[u][i];
        if (!vis[v])
            dfs(v);
    }
}

//邻接矩阵be like ↓
void dfs(int u)
{
    vis[u] = true;
    for (int v = 1; v <= n; v++)//n是顶点个数
    {
        if (G[u][v] && !vis[v])//u和v之间有边
            dfs(v);
    }
}

//链式前向星be like ↓
void dfs(int u)
{
    vis[u] = true;
    for (int i = head[u]; ~i; i = edge[i].next) //next是指向下一条边的指针
    {
        int v = edge[i].to;//v是u的一个邻接点
        if (!vis[v])
            dfs(v);
    }
}

$BFS$ be like ↓

//邻接表be like ↓
queue<int> que;
void bfs(int u)
{
    que.push(u);
    vis[u] = true;
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        for (int i = 0; i < G[u].size(); i++)//可以用auto
        {
            int v = G[u][i];
            if (!vis[v])
            {
                vis[v] = true;
                que.push(v);
            }
        }
    }
}

//邻接矩阵be like ↓
queue<int> que;
void bfs(int u)
{
    que.push(u);
    vis[u] = true;
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        for (int v = 1; v <= n; v++)//n是顶点个数
        {
            if (G[u][v] && !vis[v])//u和v之间有边
            {
                vis[v] = true;
                que.push(v);
            }
        }
    }
}

//链式前向星be like ↓
queue<int> que;
void bfs(int u)
{
    que.push(u);
    vis[u] = true;
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        for (int i = head[u]; ~i; i = edge[i].next) //next是指向下一条边的指针
        {
            int v = edge[i].to;//v是u的一个邻接点
            if (!vis[v])
            {
                vis[v] = true;
                que.push(v);
            }
        }
    }
}

深度优先搜索和广度优先搜索的时间复杂度都是 $O(n + m)$，其中 $n$ 是顶点的个数，$m$ 是边的个数。深度优先搜索和广度优先搜索的区别在于，深度优先搜索是一种递归的方式，适合于递归的问题，而广度优先搜索是一种队列的方式，适合于迭代的问题。

图的应用

图论的应用非常广泛，包括但不限于最短路径、拓扑排序、最小生成树、网络流、二分图、最小费用最大流、二分图匹配、强连通分量、最小割、无向图的割点和桥等问题。图论的应用非常重要，是图论的一个重要研究方向，也是算法竞赛中的一个重要内容，具体举例be like ↓（非按难度排序）

最短路径：最短路径是指图中两个顶点之间的最短路径，最短路径问题是图论中的一个重要问题，包括但不限于 Dijkstra 算法、Floyd 算法、SPFA 算法等问题。
拓扑排序：拓扑排序是指一个有向无环图的所有顶点的一种线性序列，使得对于图中的每一条边 $(u, v)$，$u$ 在序列中都出现在 $v$ 的前面。拓扑排序问题是图论中的一个重要问题，包括但不限于 Kahn 算法等问题。
最小生成树：最小生成树是指一个连通图的生成树中边的权值之和最小的生成树，最小生成树问题是图论中的一个重要问题，包括但不限于 Prim 算法、Kruskal 算法等问题。
网络流：网络流是指在网络中流动的流量，网络流问题是指在网络中流动的流量的问题。网络流问题是图论中的一个重要问题，包括但不限于最大流、最小割、二分图匹配等问题。
二分图：二分图是指一个图的顶点可以分成两个不相交的集合，并且图中的每条边都连接一个集合中的顶点和另一个集合中的顶点。二分图问题是图论中的一个重要问题，包括但不限于匈牙利算法等问题。
最小费用最大流：最小费用最大流是指在网络中流动的流量的费用最小的最大流，最小费用最大流问题是图论中的一个重要问题，包括但不限于 SPFA 算法等问题。
二分图匹配：二分图匹配是指一个二分图中的边的一个子集，使得图中的每个顶点都至多与一个边相连。二分图匹配问题是图论中的一个重要问题，包括但不限于匈牙利算法等问题。
强连通分量：强连通分量是指有向图中的极大强连通子图，强连通分量问题是图论中的一个重要问题，包括但不限于 Tarjan 算法等问题。
最小割：最小割是指一个连通图的割集中边的权值之和最小的割集，最小割问题是图论中的一个重要问题，包括但不限于 Ford-Fulkerson 算法等问题。
无向图的割点和桥：无向图的割点是指去掉这个顶点后，图的连通度增加的顶点，无向图的桥是指去掉这条边后，图的连通度增加的边。无向图的割点和桥问题是图论中的一个重要问题，包括但不限于 Tarjan 算法等问题。

图论算法

首先图论作为一个无论是在算法竞赛还是计算机科学抑或是数学领域都是有着重要地位的一个极大的分支，其内容极多且艰深，简单如最短路算法，复杂如网络流算法，以及各种结合其他算法和数据结构的问题 ~~(牛鬼蛇神)~~ 。图论是一个非常庞大的领域，这里只是简单地介绍一些常见的图论算法，以及一些常见的图论问题。

（按理来说，接下来应该展开讲很多很多东西，但是，这里只是一个简单的入门，并且在这节课我只负责基础知识和拓扑排序，所以接下来庞大的算法部分就只有一个拓扑排序了。）

拓扑排序

拓扑排序的概念

拓扑排序是指一个有向无环图的所有顶点的一种线性序列，使得对于图中的每一条边 $(u, v)$，$u$ 在序列中都出现在 $v$ 的前面。拓扑排序问题是图论中的一个重要问题，拓扑排序的应用非常广泛，包括但不限于课程安排、任务安排、依赖关系等问题。抑或是在有向图中求解最长路径问题以及找出环等问题。

在最开始，我们也提到过了环的概念，环是指路径的起点和终点相同的路径。在拓扑排序中，如果一个图中存在环，那么这个图就无法进行拓扑排序。但是正因为这个特性，拓扑排序可以用来判断一个图是否是有向无环图（DAG）。

拓扑排序的算法

拓扑排序的算法有很多种，其中最常见的是 $Kahn$ 算法。$Kahn$ 算法是一种基于 $BFS$ 的拓扑排序算法，其基本思想是：

从图中找出一个入度为 $0$ 的顶点，将这个顶点加入拓扑排序的结果中。
将这个顶点从图中删除，同时将这个顶点的所有邻接点的入度减 $1$。
重复上述过程，直到所有的顶点都被加入拓扑排序的结果中。
对于含有环的图，拓扑排序的结果的个数一定小于顶点的个数，因为环中的顶点的入度不为 $0$，永远无法加入拓扑排序的结果中。

$Kahn$ 算法的代码 be like ↓

vector<int> G[MAXN]; // 邻接表
int in[MAXN]; // 入度
vector<int> ans; // 存储拓扑排序的结果
bool TopoSort(int n)
{
    queue<int> que;
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0)
            que.push(i);
    }
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        ans.push_back(u);
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            in[v]--;
            if (in[v] == 0)
                que.push(v);
        }
    }
    return ans.size() == n;
    //如果拓扑排序的结果的个数等于顶点的个数，那么这个图是有向无环图
}

拓扑排序的时间复杂度是 $O(n + m)$，其中 $n$ 是顶点的个数，$m$ 是边的个数。

已有 4 条评论

11 访客

2024-07-16 22:23 回复

沙发

Android 13 / QQ浏览器
coolarec"> coolarec 访客

2024-07-16 22:53 回复

好多东西

Linux / QQ浏览器
1. NagoriYuuuki"> NagoriYuuuki 博主
  
  @coolarec 2024-07-17 09:29 回复
  
  已经少讲好多了（
  
  Windows 10 / Microsoft Edge
Nina 访客

2024-10-26 16:34 回复

第一次对中文感到如此陌生

Windows 10 / Microsoft Edge