- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
两三个星期没有发布新文章了,今天再来讲一个新的数据结构:图.
见名知意,图论 (Graph Theory) 就是研究 图 (Graph) 的数学理论和方法。图是一种抽象的数据结构,由 节点 (Node) 和 连接这些节点的 边 (Edge) 组成。图论在计算机科学、网络分析、物流、社会网络分析等领域有广泛的应用.
如下,这就是一个图,可以看到这个图有 \(5\) 个顶点,分别编号为 \(\{0, 1, 2, 3, 4\}\)。同时这个图有 \(4\) 条边,例如,在顶点 \(2\) 和 顶点 \(4\) 之间存在着一条边.
在详细讲解图论和有关图论算法之前,先来了解一下在图论中的一些基本表述和规范.
如下图,就是一个有向的简单图(通常来说,在有向图中边的方向用箭头来表示):
如下图,就是一个无向的多重图,其中存在两条边可以从顶点 \(5\) 到顶点 \(2\):
与此同时,为了方便起见,对于无向图的处理,我们只需要在两个顶点之间建立两个方向相反的无向边就可以表示一个无向图,具体如下:
在计算机中,图可以通过许多方式来构建和表示。总的可以分成图的邻接矩阵和邻接表两种方法(关于链式前向星本文不过多展开叙述,有兴趣的可以自行查阅相关文档).
图的邻接矩阵 (Adjacency Matrix) 。
若一个图中有 \(N\) 个顶点,那么我们就可以用一个 \(N \times N\) 的矩阵来表示这个图。我们一般定义,若矩阵的元素 \(A_{i, j} \neq -\infty\) 表示从节点 \(i\) 到 \(j\) 有一条有向边,其中边的权值为 \(A_{i, j}\).
假设存在一个有 \(3\) 个顶点的图,并且有三条有向边 \(E = \{(1, 2), (2, 3), (3, 2)\}\),那么就可以用邻接矩阵表示为:
画成可视化的图就长这个样子:
在 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 等问题.
对于下面这个无向图不连通图,顶点 \(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;
}
更多关于图论的算法,请持续关注后续更新.
最后此篇关于【知识点】图与图论入门的文章就讲到这里了,如果你想了解更多关于【知识点】图与图论入门的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
两三个星期没有发布新文章了,今天再来讲一个新的数据结构:图。 何为图论 见名知意,图论 (Graph Theory) 就是研究 图 (Graph) 的数学理论和方法。图是一种抽象的数据结
前言:这又是一篇关于数据结构的文章。 今天来讲一下线段树和线段树的基本应用。线段树 (Segment Tree),是一种非常高效且高级的数据结构,其主要用于区间查询和与区间更新相关的问题,
前几天谈论了许多关于数论和数据结构的东西,这些内容可能对初学者而言比较晦涩难懂(毕竟是属于初高等算法/数据结构的范畴了)。今天打算来讲一些简单的内容 - STL 标准模板库。 STL 标准
以下内容来源于于我开源的 JavaGuide (Java学习&&面试指南,Github 130k star,370人共同参与爱完善), 万字总结,质量有保障! 这
恶意软件是病毒、蠕虫、特洛伊木马以及其他有害计算机程序的总称,并且很早就一直存在。而恶意软件随着时间的失衡不断发展演变,黑客利用它来进行破坏并获取敏感信息。而阻止和打击恶意软件占据了信息安全专业人
我是一名优秀的程序员,十分优秀!