图 ( 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;
}
}
}
文章浏览阅读1.6k次。安装配置gi、安装数据库软件、dbca建库见下:http://blog.csdn.net/kadwf123/article/details/784299611、检查集群节点及状态:[root@rac2 ~]# olsnodes -srac1 Activerac2 Activerac3 Activerac4 Active[root@rac2 ~]_12c查看crs状态
文章浏览阅读1.3w次,点赞45次,收藏99次。我个人用的是anaconda3的一个python集成环境,自带jupyter notebook,但在我打开jupyter notebook界面后,却找不到对应的虚拟环境,原来是jupyter notebook只是通用于下载anaconda时自带的环境,其他环境要想使用必须手动下载一些库:1.首先进入到自己创建的虚拟环境(pytorch是虚拟环境的名字)activate pytorch2.在该环境下下载这个库conda install ipykernelconda install nb__jupyter没有pytorch环境
文章浏览阅读5.2k次,点赞19次,收藏28次。选择scoop纯属意外,也是无奈,因为电脑用户被锁了管理员权限,所有exe安装程序都无法安装,只可以用绿色软件,最后被我发现scoop,省去了到处下载XXX绿色版的烦恼,当然scoop里需要管理员权限的软件也跟我无缘了(譬如everything)。推荐添加dorado这个bucket镜像,里面很多中文软件,但是部分国外的软件下载地址在github,可能无法下载。以上两个是官方bucket的国内镜像,所有软件建议优先从这里下载。上面可以看到很多bucket以及软件数。如果官网登陆不了可以试一下以下方式。_scoop-cn
文章浏览阅读4.5k次,点赞2次,收藏3次。首先要有一个color-picker组件 <el-color-picker v-model="headcolor"></el-color-picker>在data里面data() { return {headcolor: ’ #278add ’ //这里可以选择一个默认的颜色} }然后在你想要改变颜色的地方用v-bind绑定就好了,例如:这里的:sty..._vue el-color-picker
文章浏览阅读640次。基于芯片日益增长的问题,所以内核开发者们引入了新的方法,就是在内核中只保留函数,而数据则不包含,由用户(应用程序员)自己把数据按照规定的格式编写,并放在约定的地方,为了不占用过多的内存,还要求数据以根精简的方式编写。boot启动时,传参给内核,告诉内核设备树文件和kernel的位置,内核启动时根据地址去找到设备树文件,再利用专用的编译器去反编译dtb文件,将dtb还原成数据结构,以供驱动的函数去调用。firmware是三星的一个固件的设备信息,因为找不到固件,所以内核启动不成功。_exynos 4412 刷机
文章浏览阅读2w次,点赞24次,收藏42次。Linux系统配置jdkLinux学习教程,Linux入门教程(超详细)_linux配置jdk
文章浏览阅读3.3k次,点赞5次,收藏19次。xlabel('\delta');ylabel('AUC');具体符号的对照表参照下图:_matlab微米怎么输入
文章浏览阅读119次。顺序读写指的是按照文件中数据的顺序进行读取或写入。对于文本文件,可以使用fgets、fputs、fscanf、fprintf等函数进行顺序读写。在C语言中,对文件的操作通常涉及文件的打开、读写以及关闭。文件的打开使用fopen函数,而关闭则使用fclose函数。在C语言中,可以使用fread和fwrite函数进行二进制读写。 Biaoge 于2024-03-09 23:51发布 阅读量:7 ️文章类型:【 C语言程序设计 】在C语言中,用于打开文件的函数是____,用于关闭文件的函数是____。
文章浏览阅读3.4k次,点赞2次,收藏13次。跟随鼠标移动的粒子以grid(SOP)为partical(SOP)的资源模板,调整后连接【Geo组合+point spirit(MAT)】,在连接【feedback组合】适当调整。影响粒子动态的节点【metaball(SOP)+force(SOP)】添加mouse in(CHOP)鼠标位置到metaball的坐标,实现鼠标影响。..._touchdesigner怎么让一个模型跟着鼠标移动
文章浏览阅读178次。项目运行环境配置:Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX(Webstorm也行)+ Eclispe(IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持)。项目技术:Springboot + mybatis + Maven +mysql5.7或8.0+html+css+js等等组成,B/S模式 + Maven管理等等。环境需要1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。_基于java技术的停车场管理系统实现与设计
文章浏览阅读3.5k次。前言对于MediaPlayer播放器的源码分析内容相对来说比较多,会从Java-&amp;gt;Jni-&amp;gt;C/C++慢慢分析,后面会慢慢更新。另外,博客只作为自己学习记录的一种方式,对于其他的不过多的评论。MediaPlayerDemopublic class MainActivity extends AppCompatActivity implements SurfaceHolder.Cal..._android多媒体播放源码分析 时序图
文章浏览阅读2.4k次,点赞41次,收藏13次。java 数据结构与算法 ——快速排序法_快速排序法