图 ( g r a p h ) (graph) (graph) 是一个二元组 G = ( V ( G ) , E ( G ) ) G=(V(G),E(G)) G=(V(G),E(G)),其中 V ( G ) V(G) V(G)是非空集,称为点集 ( v e r t e x s e t ) (vertex set) (vertexset),对于 V V V中的每个元素,我们称其为顶点 ( v e r t e x ) (vertex) (vertex)或节点 ( n o d e ) (node) (node),简称点, E ( G ) E(G) E(G)为 V ( G ) V(G) V(G)各结点之间边的集合,称为边集 ( e d g e s e t ) (edge set) (edgeset)
常用 G = ( V , E ) G=(V,E) G=(V,E) 表示图
图有多种,包括无向图 ( u n d i r e c t e d g r a p h ) (undirected graph) (undirectedgraph),有向图 ( d i r e c t e d g r a p h ) (directed graph) (directedgraph),混合图 ( m i x e d g r a p h ) (mixed graph) (mixedgraph),带权图 等
代码实现:
bool adj[MAXN][MAXN];
scanf("%d %d", &n , &m);
for (int i = 1 ; i <= m ; i ++) {
int u , v;
scanf("%d %d", &u , &v);
adj[u][v] = 1;
adj[v][u] = 1;
}
代码实现:
struct node{
vector<int> v;
}a[MAXN];
for (int i = 1 ; i <= m ; i ++) {
int u , v;
scanf("%d %d", &u , &v);
a[u].v.push_back(v);
a[v].v.push_back(u);
}
return 0;
对于这样一张有向图:
输入边的顺序如下:
1 2
2 3
3 4
1 3
4 1
1 5
4 5
对于邻接表来说是这样的:
1 -> 2 -> 3 -> 5
2 -> 3
3 -> 4
4 -> 1 -> 5
5 -> ^
对于链式前向星来说是这样的:
edge[0].to = 2; edge[0].next = -1; head[1] = 0;
edge[1].to = 3; edge[1].next = -1; head[2] = 1;
edge[2].to = 4; edge[2],next = -1; head[3] = 2;
edge[3].to = 3; edge[3].next = 0; head[1] = 3;
edge[4].to = 1; edge[4].next = -1; head[4] = 4;
edge[5].to = 5; edge[5].next = 3; head[1] = 5;
edge[6].to = 5; edge[6].next = 4; head[4] = 6;
简化后:1 -> 5 -> 3 -> 2
核心代码:
struct edge{
int to , nxt , w;
};
edge a[MAXN];
void add(int u , int v , int w) {
a[cnt].w = w;
a[cnt].to = v;
a[cnt].nxt = head[u];
head[u] = cnt ++;
}
(内置芝士)什么是图的遍历:从图中的某个顶点出发,按某种方法对图中的所有顶点访问且仅访问一次。为了保证图中的顶点在遍历过程中仅访问一次,要为每一个顶点设置一个访问标志
给定一个有向图,有 N N N个顶点, M M M条边,顶点从 1.. N 1..N 1..N依次编号,求出字典序最小的深度优先搜索顺序
利用邻接表存储点的关系,将点放入 d f s dfs dfs里搜索与之相邻但未被遍历过的点
核心代码如下:
void dfs(int k) {
if (vis[k]) return;
vis[k] = 1;
printf("%d ", k);
for (set<int>:: iterator it = st[k].begin() ; it != st[k].end() ; it ++) {
dfs(*it);
}
}
for (int i = 1 ; i <= m ; i ++) {
int u , v;
scanf("%d %d", &u , &v);
st[u].insert(v);
}
dfs(1);
for (int i = 1 ; i <= n ; i ++) {
if (!vis[i]) dfs(i);
}
给定一个有向图,有 N N N个顶点, M M M条边,顶点从 1 1 1… N N N依次编号,求出字典序最小的宽度优先搜索顺序
利用邻接表存储点的关系,将点放入 b f s bfs bfs里搜索与之相邻但未被遍历过的点
核心代码如下:
void bfs(int k) {
q.push(k);
while(!q.empty()) {
int x = q.front();
q.pop();
if (vis[x]) continue;
vis[x] = 1;
printf("%d ", x);
for (set<int>:: iterator it = st[x].begin() ; it != st[x].end() ; it ++) {
q.push(*it);
}
}
}
for (int i = 1 ; i <= m ; i ++) {
int u , v;
scanf("%d %d", &u , &v);
st[u].insert(v);
}
bfs(1);
for (int i = 1 ; i <= n ; i ++) {
if (!vis[i]) bfs(i);
}
一个无向图,从指定顶点出发进行 B F S BFS BFS,求遍历得到的顶点序
利用邻接矩阵存储边(每一层要从小到大排序,矩阵方便操作),将点放入 b f s bfs bfs里搜索与之相邻但未被遍历过的点
核心代码如下:
void bfs() {
q.push(rt);
while(!q.empty()) {
int x = q.front();
q.pop();
if (vis[x]) continue;
vis[x] = 1;
printf("%d ", x);
for (int i = 1 ; i <= n ; i ++) {
if (adj[x][i]) {
q.push(i);
}
}
}
}
for (int i = 1 ; i <= m ; i ++) {
int u , v;
scanf("%d %d", &u , &v);
adj[u][v] = 1;
adj[v][u] = 1;
}
Ps:欧拉路指的是:存在这样一种图,可以从其中一点出发,不重复地走完其所有的边如果欧拉路的起点与终点相同,则称之为欧拉回路
需满足条件:
根据一笔画的两个定理,如果寻找欧拉回路,对任意一个点执行深度优先遍历;找欧拉路,则对一个奇点执行 d f s dfs dfs,时间复杂度为 O ( m + n ) O(m+n) O(m+n), m m m为边数, n n n是点数
即把奇点作为起点放入 d f s dfs dfs搜索,每搜索到一个相邻的点即把这条边删掉,若所有边都遍历到了,输出答案
核心代码如下:
void dfs(int k , int id) {
ans[id] = k;
bool f = 1;
for (int i = 1 ; i <= n ; i ++) {
for (int j = 1 ; j <= m ; j ++) {
if (a[i][j]) {
f = 0;
break;
}
}
}
if (f) {
for (int i = 1 ; i <= id ; i ++) {
printf("%d ", ans[i]);
}
exit(0);
}
for (int i = 1 ; i <= n ; i ++) {
if (a[k][i]) {
a[k][i] = 0;
a[i][k] = 0;
dfs(i , id + 1);
a[k][i] = 1;
a[i][k] = 1;
}
}
}
思路:利用邻接表存储边的关系,枚举1~ n n n作为起点的情况,然后每搜到一种情况便把 a n s ans ans加 1 1 1即可
int dfs(int k , int cnt) {
if(cnt == n) return 1;
int res = 0;
for (int i = 1 ; i <= h[k][0] ; i ++) {
if (!vis[h[k][i]]) {
vis[h[k][i]] = 1;
res += dfs(h[k][i] , cnt + 1);
vis[h[k][i]] = 0;
}
}
return res;
}
for (int i = 1 ; i <= n ; i ++) {
vis[i] = 1;
ans += dfs(i , 1);
vis[i] = 0;
}
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图 ( ( (由结点和路径组成的 ) ) )中两结点之间的最短路径。
例如:
佛洛伊德是最简单的最短路径算法,可以计算图中任意两点间的最短路径。时间复杂度为 O ( N 3 ) O(N^3) O(N3),适用于出现负边权的情况
for(int k = 1 ; k <= n ; k ++) {
for(int i = 1 ; i <= n ; i ++) {
for(int j = 1 ; j <= n ; j ++) {
if(F[i][j] > F[i][k] + F[k][j]) {
F[i][j] = F[i][k] + F[k][j];
}
}
}
}
F [ i ] [ j ] F[i][j] F[i][j]得出的就是任意起点 i i i到任意终点 j j j的最短路径
- 动态规划以”途径点集大小”为阶段
- 决策需要枚举中转点,不妨考虑也以中转点集为阶段
- F [ k ] [ i ] [ j ] F[k][i][j] F[k][i][j]表示”可以经过标号 ≤ k ≤k ≤k的点中转时”从 i i i到 j j j的最短路
- F [ 0 ] [ i ] [ j ] = W [ i ] [ j ] F[0][i][j]=W[i][j] F[0][i][j]=W[i][j], W W W为前面定义的邻接矩阵
- F [ k ] [ i ] [ j ] F[k][i][j] F[k][i][j] = m i n min min{
F [ k − 1 ] [ i ] [ j ] F[k-1][i][j] F[k−1][i][j] , F [ k − 1 ] [ i ] [ k ] F[k-1][i][k] F[k−1][i][k] + F [ k − 1 ] [ k ] [ j ] F[k-1][k][j] F[k−1][k][j]}
- k k k这一维空间可以省略,变成 F [ i ] [ j ] F[i][j] F[i][j]
- 由于 k k k是 D P DP DP的阶段循环,所以 k k k循环必须要放在最外层
F l o y d Floyd Floyd算法输出路径也是采用记录前驱点的方式。因为 f l o y d floyd floyd是计算任意两点间最短路径的算法, F [ i ] [ j ] F[i][j] F[i][j]记录从 i i i到 j j j的最短路径值。故我们定义 p r e [ i ] [ j ] pre[i][j] pre[i][j]为一个二维数组,记录从 i i i到 j j j的最短路径中, j j j的前驱点是哪一个,递归还原路径
void floyd() {
for (int k = 1 ; k <= n ; k ++) {
for (int i = 1 ; i <= n ; i ++) {
for (int j = 1 ; j <= n ; j ++) {
if (dp[i][k] + dp[k][j] < dp[i][j]) {
dp[i][j] = dp[i][k] + dp[k][j];
pre[i][j] = pre[k][j];
}
}
}
}
}
void print(int x) {
if (pre[s][x] == 0) return;
print(pre[s][x]);
printf(" %d", x);
}
设起点为 s s s, d i s [ v ] dis[v] dis[v]表示从指定起点 s s s到 v v v的最短路径, p r e [ v ] pre[v] pre[v]为 v v v的前驱,用来输出路径
m e m s e t ( d i s , + ∞ ) memset(dis,+∞) memset(dis,+∞)
m e m s e t ( v i s , f a l s e ) memset(vis,false) memset(vis,false);
( i n t (int (int v = 1 ; v < = n ; v + + ) v = 1 ; v <= n ; v ++) v=1;v<=n;v++)
d i s [ v ] = w [ s ] [ v ] dis[v]=w[s][v] dis[v]=w[s][v];
d i s [ s ] = 0 dis[s]=0 dis[s]=0; p r e [ s ] = 0 pre[s]=0 pre[s]=0; v i s [ s ] = t r u e vis[s]=true vis[s]=true;
dis [ v ] [v] [v]为 s s s到 v v v的最短路距离; p r e [ v ] pre[v] pre[v]为 v v v的前驱结点,用来输出路径
让我们来看一组动画 (不动的动画)
原始图
初始化
寻找源点相邻的最短路
松弛源点到1/4/3
寻找源点到1/4/3的最短路
松弛源点到4
寻找源点到4的最短路由于点4没有相邻点故不作松弛操作
寻找剩余未访问点3松弛源点到4并未更改最短路
最后奉上本人的代码(优化后) :
struct edge{
int to , nxt , w;
}a[MAXN];
void add(int u , int v , int w) {
a[++ cnt].w = w;
a[cnt].to = v;
a[cnt].nxt = head[u];
head[u] = cnt;
}
struct node{
int id , w;
node(int iid , int ww) {
id = iid;
w = ww;
}
friend bool operator<(node x , node y) {
return x.w > y.w;
}
};
priority_queue<node> q;
void dijkstra() {
memset(dis , 0x3f , sizeof(dis));
dis[s] = 0;
q.push(node(s , 0));
while(!q.empty()) {
int u = q.top().id;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u] ; i ; i = a[i].nxt) {
int v = a[i].to , w = a[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(node(v , dis[v]));
}
}
}
}
非本人代码(不想打了):
所以,我们引入了一个新的算法—— S P F A SPFA SPFA
bool vis[MAXN];
struct edge{
int to , w , nxt;
}a[MAXN];
void add(int u , int v , int w) {
a[++ cnt].w = w;
a[cnt].to = v;
a[cnt].nxt = head[u];
head[u] = cnt;
}
struct node {
int id , w;
node(int iid , int ww) {
id = iid;
w = ww;
}
};
queue<node> q;
int SPFA() {
memset(dis , 0x3f, sizeof(dis));
dis[s] = 0;
q.push(node(s , 0));
while(!q.empty()) {
int u = q.front().id;
q.pop();
vis[u] = 0;
for (int i = head[u] ; i ; i = a[i].nxt) {
int v = a[i].to , w = a[i].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) {
vis[v] = 1;
q.push(node(v , dis[v]));
}
}
}
}
return 1;
}
( a ) (a) (a)初始化: m i n [ v ] = ∞ ( v ≠ 1 ) min[v]=∞(v≠1) min[v]=∞(v=1); m i n [ 1 ] = 0 ; M S T = 0 ; min[1]=0;MST=0; min[1]=0;MST=0;
( b ) f o r ( i = 1 ; i < = n ; i + + ) (b)for(i=1;i<=n;i++) (b)for(i=1;i<=n;i++)
f o r for for寻找 m i n [ u ] min[u] min[u],最小的蓝点 u u u;
②将 u u u标记为白点;
③ M S T + = m i n [ u ] MST+=min[u] MST+=min[u];
④ f o r for for与白点 u u u相连的所有蓝点v(可暴力枚举,更好的是求 v e c t o r vector vector的 s i z e size size)
i f ( w [ u ] [ v ] < m i n [ v ] ) if(w[u][v]<min[v]) if(w[u][v]<min[v]) m i n [ v ] = w [ u ] [ v ] ; min[v]=w[u][v]; min[v]=w[u][v];
( c ) (c) (c)算法结束:MST即为最小生成树的权值之和
void Prim() {
for (int i = 1 ; i <= n ; i ++) d[i] = 0x3f3f3f3f3f3f;
d[1] = 0;
q.push(node(1 , 0));
while(!q.empty()) {
int u = q.top().id;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u] ; i ; i = a[i].nxt) {
ll v = a[i].to;
ll w = a[i].w;
if (w < d[v] && !vis[v]) {
d[v] = w;
q.push(node(v , d[v]));
}
}
MST += d[u];
}
}
( a ) (a) (a)初始化
①写出并查集三件套
②将边按权值大小排序
$(b)
① i f if if两个点的祖先不是同一个,将两个点合并,并累加权值;
②如果图已经联通,即 t o t = = n tot==n tot==n跳出
算法结束: M S T MST MST即为最小生成树的权值之和。
void kruscal() {
int tot = 0;
for (int i = 1 ; i <= m ; i ++) {
if (UnionSet(a[i].u , a[i].v)) {
MST += a[i].w;
tot ++;
if (tot == n) return;
}
}
}
文章浏览阅读85次。In computer science, aheapis a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (i..._该数的立方分解为一串连续奇数的和 样例输入 13 样例输出 13*13*13=2197=157+159+
文章浏览阅读6.2k次,点赞4次,收藏15次。Linux ln(英文全拼:link files)命令是一个非常重要命令,它的功能是为某一个文件在另外一个位置建立一个同步的链接。当我们需要在不同的目录,用到相同的文件时,我们不需要在每一个需要的目录下都放一个必须相同的文件,我们只要在某个固定的目录,放上该文件,然后在 其它的目录下用ln命令链接(link)它就可以,不必重复的占用磁盘空间。如果文件被删除,则软链接文件失去指向,变为不可用如果文件被删除,由于硬链接文件直接指向内容,因此不受影响。_linux ln -s
文章浏览阅读4.4k次,点赞5次,收藏3次。注意:此版本spring-cloud需要spring-boot 2.6.7及以上版本支持。版本说明 · alibaba/spring-cloud-alibaba Wiki · GitHubSpring Cloud Alibaba provides a one-stop solution for application development for the distributed solutions of Alibaba middleware. - 版本说明 · alibaba/spring-cloud-_spring-cloud-starter-alibaba-nacos-config 版本
文章浏览阅读827次,点赞26次,收藏23次。0 简介今天学长向大家介绍一个适合作为毕设的项目。
文章浏览阅读8.7w次,点赞66次,收藏385次。一、需求场景近来小区安装了智能门禁,但只配发了一张门禁卡,不方便使用,于是产生了用手机模拟门禁卡,或者复制一张门禁卡的想法。本文使用的软件:(CSDN无法修改下载积分了。。。)包括手机NFC读写卡神器Mifare Classic Tool(MCT)2.2.5最新版、手机读卡工具NFC TagInfo、NFC卡模拟软件Card emulator、RE管理器,以及一款NFC模拟..._nfc密钥字典
文章浏览阅读901次。近日有网友反映在Win10系统中安装dolby音效驱动的时候,发现无法安装,该怎么办呢?由于Win10系统中已正常方法安装驱动只能安装带签名的驱动,导致dolby音效驱动无法安装。下面就详情来看看具体的解决办法吧!首先我们来了解下dolby是什么?dolby以英国R.M.DOLBY博士发明的杜比声效系统,对电影音响和家庭音响带来了巨大的影响。像我们家中就常会用到杜比降噪系统和杜比环绕声系统。对于对..._realtek使用conexant驱动
文章浏览阅读852次。故事的开始一个咖啡劲儿已经消退了的午后,业务大大突然笑眯眯的对我说:"Presto insert Mysql 特别慢,跑了几十分钟了,一直 13% 左右, 你,帮忙看看?"。第一反应就是: "嗯?难道出大问题了?",老实讲,有一点点小兴奋。一顿操作猛如虎紧接着,大概进行了如下几个猛如虎的操作:Presto 监控看起来,嗯~有一个 Stage 很慢,但是又没有死,大概十几K Row/s 的速度在爬..._presto insert
文章浏览阅读5.3k次。用nvm安装的node使用很正常,突然有天npm报错npm -vnpm不存在node -vnode不存在_error: cannot find module 'e:\devtools\nodejs\node_modules\npm\bin\npm-cli.j
文章浏览阅读930次。由于系统总是偶然出问题,记录此文以便快速恢复环境。基本环境设置密码$ sudo passwd root$ sudo passwd 用户名更换源为清华源 or else系统更新$ apt update$ apt fullupgrade$ apt autoremove$ apt autoclean配置SSH$ apt install openssh-server$ /etc/init.d/ssh start支持32位$ dpkg --add-archite_ctf实验机的输入法换出来
文章浏览阅读2.7w次,点赞189次,收藏1.4k次。题目:打印出所有的“水仙花数”,所谓“水仙花数”是指一个三位数,其各位数字立方和等于该数本身。例如:153是一个“水仙花数”,因为153=1的三次方+5的三次方+3的三次方。_c语言代码
文章浏览阅读940次,点赞3次,收藏10次。输入的格式限定有待完善#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream>using namespace std;const int inf=0x3f3f3f3f;#define OK 1#define ERROR 0typedef i..._链栈计算器
文章浏览阅读10w+次,点赞269次,收藏1.3k次。Spring的一个核心功能是IOC,就是将Bean初始化加载到容器中,Bean是如何加载到容器的,可以使用Spring注解方式或者Spring XML配置方式。 Spring注解方式减少了配置文件内容,更加便于管理,并且使用注解可以大大提高了开发效率!_spring注解