- 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的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我想填充 3D 等高线图 (contour3(X,Y,Z)),就像 2D 等高线填充图 (contourf(X,Y,Z))。但我无法弄清楚如何实现这一目标。 contour3 和 surf 的组合不是
我有一个 c3.js 折线图,表示 2 个值的演变。我需要折线图的工具提示是饼图(工具提示 = 另一个 c3.js 图形)。 这是我成功的: http://jsfiddle.net/owhxgaqm/
我有具有结构的 Pandas 数据框: A B 0 1 1 1 2 1 2 3 4 3 3 7 4 6 8 如何生成 Seaborn Violin 图,每列作为其自己的单独
我正在使用 D3DXSPRITE 方法将我的 map 图 block 绘制到屏幕上,我刚刚添加了一个缩放功能,当您按住向上箭头时会放大,但注意到您现在可以看到图 block 之间的间隙,这是一些屏幕截
今天我们开始学习目前学习到的最难最复杂的数据结构图。 简单回顾一下之前学习的数据结构,数组、单链表、队列等线性表中数据元素是一对一关系,而树结构中数据元素是一对多关系,而图结构中数据元素则是多对
1、系统环境如下图: 2、为该系统添加一块新的虚拟硬盘,添加后需重启虚拟机,否则系统不识别;如下图,/dev/sdc 是新添加的硬盘; 3、fdisk /dev/sdc为新硬盘创建分区:
1、nagios简介 nagios是一款开源的电脑系统和网络监视工具,能有效监控windows、linux和unix的主机状态,交换机路由器等网络设置,打印机等。在系统或服务状态异常时发
越来越多人开始习惯用手机上网,浏览网页、查看邮件···移动化已经成为互联网发展必然趋势,包括facebook在内的很多互联网公司都将移动广告作为下一个淘金地
1.图片处理 1.圆角图片 复制代码 代码如下: /** * 转换成圆角 * &n
Microsoft SQL Server Management Studio是SQL SERVER的客户端工具,相信大家都知道。我不知道大伙使用导入数据的情况怎么样,反正我最近是遇到过。主要是因为没
debian6系统: 首先先安装mysql吧: 打开终端(root)用户登入 apt-get purge mysql-server-5.5 安装完成后: 默认情况下Mysql只允许本地登录
fedora16英文环境下支持中文输入法的方法 fedora16英文环境下支持FCITX的中文输入法: $ im-chooser 就会出现选择界面,选择第二个就行了。
Net预编译命令 C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727\aspnet_compiler.exe -? 显示说明 我们需要选择的命令为&n
有的时候电脑出现一些故障有的时候通过将其修改bios设置的方法来解决故障,那么在bios上设置能不能将电脑恢复出厂设置呢?其实也是可以的。方法也很简单的,只要会进入电脑的bios懂的上面英文的意思就
笔者曾介绍过Deepin 将对龙芯进行全面支持,打造最优美龙芯电脑桌面。现在Deepin团队移植工作取得了突破性的成果,Deepin桌面已经在龙芯3A和龙芯3B电脑上成功运行起来了。 以下为龙芯3
在安装一些软件之后,我们的电脑总是会发生一点小变化,不是桌面上多了几个网址图标,就是IE浏览器的默认主页被篡改成乱七八糟的网址。最可气的是,在IE设置中将默认主页改回来后,下次启动Win7后又变了回
“注册表编辑器怎么打开”虽说不是很难的问题,但是对于对电脑常识不是很擅长的网民来说,当电脑出现问题或需要更改设置时,着实还是件头疼的问题。因为需要打开注册表进行操作解决。那么如何打开注册表编辑器呢?
这篇文章重点介绍10个重要的WordPress安全插件和技巧,用来保护WordPress网站或者博客。 1. WP Security 人工帮助你修复被黑客入侵的网站,只要按照他们网站上的联系电话
其实运用object和javascript调用外部文件,也能实现不同栏目调用不同友情链接,即相当于调用不同栏目友情链接文件, {dede:field.typeid/}来获取当前栏目的ID。
我有一个复值矩阵。 如果我发出命令: plot(myMatrix) 然后它在图形设备上显示一种散点图,X 轴标记为 Re(myMatrix),Y 轴标记为 Im(myMatrix)。这显示了我正在寻找
我是一名优秀的程序员,十分优秀!