【知识点】图与图论入门

🕗 发布于 2024-12-07 05:59 图论 c++ 数据结构 算法图搜索算法

何为图论

见名知意，图论 (Graph Theory) 就是研究 图 (Graph) 的数学理论和方法。图是一种抽象的数据结构，由 节点 (Node) 和连接这些节点的 边 (Edge) 组成。图论在计算机科学、网络分析、物流、社会网络分析等领域有广泛的应用。

如下，这就是一个图，可以看到这个图有 $5$ 个顶点，分别编号为 ${0, 1, 2, 3, 4\}$ 。同时这个图有 $4$ 条边，例如，在顶点 $2$ 和顶点 $4$ 之间存在着一条边。

图的基本概念

在详细讲解图论和有关图论算法之前，先来了解一下在图论中的一些基本表述和规范。

图 (Graph)：图是一种由一组顶点和一组边组成的数据结构，记做 $G = (V, E)$ ，其中 $V$ 代表顶点集合， $E$ 代表边集合。
顶点 (Vertex)：顶点是图的基本单位，也称为节点。
边 (Edge)：一条边是连接两个顶点的线段或弧。可以是无向的，也可以是有向的。一条边可以记做为 $(u, v)$ 。在无向图中，若存在一条 $(u, v)$ ，表示可以从 $u$ 点直接走到 $v$ 点，反之亦然。但若在有向图中，存在一条边 $(u, v)$ ，表示可以从 $u$ 节点直接走向 $v$ 节点，如果不存在一条边 $v, u$ ，那么 $v$ 节点就没有办法直接走向 $u$ 节点。
无向图 (Undirected Graph)：图中的边没有方向，即 $(u, v)$ 和 $(v, u)$ 是同一条边。
有向图 (Directed Graph/ Digraph)：图中的边有方向，即 $(u, v)$ 和 $(v, u)$ 不是同一条边。
简单图 (Simple Graph)：表示含有重边（两个顶点之间的多条边）和自环（顶点到自身的边）的图。
多重图 (Multigraph)：允许有重边和自环的图。
边权 (Weight of an Edge)：一般表示经过这一条边的代价（代价一般是由命题人定义的）。

如下图，就是一个有向的简单图（通常来说，在有向图中边的方向用箭头来表示）：

如下图，就是一个无向的多重图，其中存在两条边可以从顶点 $5$ 到顶点 $2$ ：

与此同时，为了方便起见，对于无向图的处理，我们只需要在两个顶点之间建立两个方向相反的无向边就可以表示一个无向图，具体如下：

图的表示方法

在计算机中，图可以通过许多方式来构建和表示。总的可以分成图的邻接矩阵和邻接表两种方法（关于链式前向星本文不过多展开叙述，有兴趣的可以自行查阅相关文档）。

图的邻接矩阵 (Adjacency Matrix)

若一个图中有 $N$ 个顶点，那么我们就可以用一个 $\times N$ 的矩阵来表示这个图。我们一般定义，若矩阵的元素 $A_{i, j} \neq -\infty$ 表示从节点 $i$ 到 $j$ 有一条有向边，其中边的权值为 $A_{i, j}$ 。

假设存在一个有 $3$ 个顶点的图，并且有三条有向边 $E = \{(1, 2), (2, 3), (3, 2)\}$ ，那么就可以用邻接矩阵表示为：
$\begin{bmatrix} & \mathtt{1} & \mathtt{2} & \mathtt{3}\\ \mathtt{1} & 0 & 1 & 0 \\ \mathtt{2} & 0 & 0 & 1 \\ \mathtt{3} & 0 & 1 & 0 \end{bmatrix}$
画成可视化的图就长这个样子：

在 C++ 中，我们可以简单地用一个二维数组来表示：

// 定义一个矩阵。
int map[50][50];

// 将所有的边初始化为负无穷大。
for (int i=1; i<=50; i++)
    for (int j=1; j<=50; j++)
        map[i][j] = -0x7f7f7f7f;

// 建边，其中所有的边权为1。
map[1][2] = map[2][3] = map[3][2] = 1;

图的邻接表 (Adjacency List)

邻接表本质上就是用链表表示图。数组的每个元素表示一个顶点，元素的值是一个链表，链表中存储该顶点的所有邻接顶点。假设存在一个有 $4$ 个顶点的图，并且有四条有向边 $E = \{(1, 2), (2, 3), (3, 2), (3, 4)\}$ ，那么就可以用邻接表表示为：

画成可视化的图就长这个样子：

在 C++ 中，我们可以使用 STL模板库中的 vector 来实现：

#include <vector>
vector<int> G[50];  // 建图。
G[1].push_back(2);
G[2].push_back(3);
G[3].push_back(2);
G[3].push_back(4);

一般情况下，推荐使用邻接表的方式来存图，因为使用邻接矩阵比较浪费空间。在顶点数量非常多但边非常少的图中， $N^2$ 的时空复杂度会导致 MLE 或 TLE 等问题。

图的各种性质

度数 (Degree)：一个顶点的度是连接该顶点的边的数量。在有向图中，有 入度 (Indegree) 和 出度 (Outdegree) 之分（具体例子见后文）。
路径 (Path)：从一个顶点到另一个顶点的顶点序列，路径上的边没有重复。
回路 (Cycle)：起点和终点相同的路径。
连通图 (Connected Graph)：任意两个顶点之间都有路径相连的无向图。
强连通图 (Strongly Connected Graph)：任意两个顶点之间都有路径相连的有向图。

对于下面这个无向图不连通图，顶点 $1$ 的度数为 $1$ ；顶点 $2$ 的度数为 $2$ ；顶点 $3$ 的度数为 $1$ ；顶点 $4$ 的度数为 $0$ 。同时，由于 $4$ 号顶点没有度数，所以该顶点没有办法到达任何一个其他的顶点，所以这个图是一个不连通图：

如下图，就是一个有向不强连通图。其中，顶点 $1$ 的入度为 $0$ ，出度为 $2$ ；顶点 $2$ 的入度为 $1$ ，出度也为 $1$ ；顶点 $3$ 的入度为 $2$ ，但出度为 $0$ 。由于顶点 $1$ 和顶点 $2$ 可以走到顶点 $3$ ，但顶点 $3$ 没有办法走到顶点 $1$ 或顶点 $2$ ，因此下面的图不是一个强连通图：

对于下图来说， $1\to 2\to 3\to 4$ 是一条从顶点 $1$ 到顶点 $4$ 的路径。 $2\to 3\to 4 \to 2\to 3$ 就不是一个路径，因为相同的边 $(2, 3)$ 被多次走到了。 $1\to 2\to 3\to 1$ 就是一个回路，因为这个路径的起点和终点相同：

图的遍历

图通常采用 深度优先搜索/ 广度优先搜索 这两个算法来遍历。其中深度优先算法是最常见的遍历算法。

对于一个用 邻接矩阵 保存的图，其深度优先搜索遍历的 C++ 代码如下：

int vis[105], map[105][105];

void dfs(int node){
    if (vis[node]) return ;
    vis[node] = 1;
    cout << node << endl;
    for (int i=1; i<=n; i++)
        if (map[node][i] != -0x7f7f7f7f)
            dfs(i);
    return ;
}

// 函数调用：dfs(1); 表示从1号顶点开始遍历。

对于一个用 邻接表 保存的图，其深度优先搜索遍历的 C++ 代码如下：

#include <vector>
vector<int> G[105];
int vis[105];

void dfs(int node){
    if (vis[node]) return ;
    vis[node] = 1;
    cout << node << endl;
    for (int to : G[node])
        dfs(to);
    return ;
}

// 函数调用：dfs(1); 表示从1号顶点开始遍历。

广度优先搜索的方式也类似：

#include <queue>
vector<int> G[105];
int vis[105];

void bfs(int node){
    queue<int> que;
    que.push(node);
    while(!que.empty()){
        int t = que.front();
        cout << t << endl;
        que.pop();
        for (int to : G[node]){
        if (!vis[to]) {
                vis[to] = 1;
                que.push(to);
            }
        }
    }
    return ;
}

// 函数调用：bfs(1); 表示从1号顶点开始遍历。

对于判断无向图的连通性，我们只需要从任意一个点开始跑一遍深搜或者广搜就行了。如果所有顶点的 vis 都被标记了，则证明图是联通的，否则图就是不连通的。

例题讲解

P3916 图的遍历

模板题目，从每一个顶点开始用深搜遍历一遍就可以了。但从每一个点考虑能走到的最大点比较麻烦，一个更优的解决办法是反向建边，从最大的点开始遍历，这样子就可以一次性计算出多个结果。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int N = 10005;
int n, m, ans, vis[N];
vector<int> G[N];

void dfs(int node, int d){
    if (vis[node]) return ;
    vis[node] = d;
    ans = max(node, ans);
    for (int to : G[node]) 
        dfs(to, d);
    return ;
}

int main(){
    cin >> n >> m;
    for (int i=0, u, v; i<m; i++){
cin >> u >> v;
        G[v].push_back(u);  // 反向建边。
    }
    for (int i=n; i>=1; i--) dfs(i, i);
    for (int i=1; i<=n; i++) 
        cout << vis[i] << ' ';
    return 0;
}

P5318 【深基18.例3】查找文献

也是一道模板题目，正常遍历即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100005;

int n, m;
int vis1[MAXN], vis2[MAXN];
queue<int> que;
vector<int> G[MAXN];

void dfs(int node, int current){
    vis1[node] = 1;
    cout << node << ' ';
    if (current == n) return ;
    for (int i=0; i<G[node].size(); i++){
        if (vis1[G[node][i]]) continue;
        dfs(G[node][i], current+1);
    }
    return ;
}

void dfs(int node){
    vis2[node] = 1;
    que.push(node);
    while(que.size()){
        int t = que.front();
        cout << t << " ";
        for (int i=0; i<G[t].size(); i++){
            if (vis2[G[t][i]]) continue;
            vis2[G[t][i]] = 1;
            que.push(G[t][i]);
        }
        que.pop();
    }
    return ;
}

int main(){
    cin >> n >> m;
    for (int i=0; i<m; i++){
        int t1, t2;
        cin >> t1 >> t2;
        G[t1].push_back(t2);
    }
    for (int i=1; i<=n; i++) 
        sort(G[i].begin(), G[i].end());
    dfs(1, 0), cout << endl, dfs(1);
    return 0;
}

番外 - 图的常见算法

更多关于图论的算法，请持续关注后续更新。

深度优先搜索 (DFS)：适用于遍历图和检测图中的回路。
广度优先搜索 (BFS)：适用于寻找最短路径（无权图）。
Dijkstra 算法：适用于加权图中寻找单源最短路径。
Bellman-Ford 算法：适用于有负权边的图中寻找单源最短路径。
Floyd-Warshall 算法：适用于寻找所有顶点对之间的最短路径。
Kruskal 算法：用于求解最小生成树 (MST - Minimum Spanning Tree)。
Prim 算法：另一种求解最小生成树的方法。
拓扑排序 (Topological Sorting)：适用于有向无环图 (DAG)，用于任务调度等应用。
Tarjan 算法：用于求解图中的强连通分量、割点、桥。

原文地址：https://blog.csdn.net/Macw07/article/details/144280264

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Linux vi/vim
下一篇：P4645 [COCI2006-2007#3] BICIKLI(Tarjan+topsort求到某点的方案数）

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14