企业网站建设参考资料,个人开发app需要多少钱,网站建设数据库怎么传送,手机网站模板大全图论入门与最短路径算法
图的基本概念
由节点和边组成的集合
图的一些概念#xff1a;
①有向边#xff08;有向图#xff09;#xff0c;无向边#xff08;无向图#xff09;#xff0c;权值
②节点#xff08;度#xff09;#xff0c;对应无向图#xff0c;…图论入门与最短路径算法
图的基本概念
由节点和边组成的集合
图的一些概念
①有向边有向图无向边无向图权值
②节点度对应无向图度就是节点连着几条边对于有向图就是出度加入度
③完全连通图
④子图
⑤路径
⑥完全图每两节点间都有一条边相连
图的遍历
①深度优先搜索
注意有向图和无向图的遍历不一样
②广度优先搜索
图的存储
邻接矩阵
①邻接矩阵-多维数组二维n * nn为节点数
设两点连通为1 如果有权值 优点快速且直观地每两个点间的关系如果要判断x和y之间的关系直接通过访问arr[x] [y]或arr[y] [x]获得两点信息
缺点存储了一些无用信息浪费空间不能快速地访问以某点为起点的所有的边。
代码演示
#includeiostream
using namespace std;int n, m, arr[105][105];int main() {cin n m;//n为节点个数//m为边的个数每条边带一个权值一个循环把权值存到数组里面for (int i 0; i m; i) {int a, b, c;cin a b c;arr[a][b] c;}//输出for (int i 1; i n; i) {cout i :;for (int j 1; j n; j) {if (arr[i][j] ! 0) {cout { i - arr[i][j] };}}cout endl;}return 0;
}Floyd算法
算法解决问题多源多个原点最短路径问题
核心思想为了取最小值所以把所有路径初始化为最大一般为0x3F然后将各种路径算一遍取两点最小距离的路径作为此最短路径因为两个两点路径的其中一个路径可以从另外两个两点路径获得所以每两点路径都是可以用两点路径获得或者两个两点路径获得
核心思想图示以1-3 1-2-5-4-3为例 核心代码
memset(arr, 0x3F, sizeof(arr));//初始化极大值
for (int i 1; i n; i) {for (int j 1; j n; j) {for (itn k 1; k n; k) {arr[j][k] min(arr[j][k], arr[j][i] arr[i][k]);//从j到k的最短路arr[j][i] arr[i][k]为经过i点中转从j到i再到k。注意无论之间有多少个中转点每三个都会被合并为一个比如15234合并523后会变成154}}
}oj746题:
#includeiostream
#includecstring
using namespace std;
int n, m, s, arr[1005][1005];
int main() {memset(arr, 0x3F, sizeof(arr));//初始化极大值cin n m;for (int i 0; i m; i) {//全边保留权值最小的边int a, b, c;cin a b c;if (arr[a][b] c) {arr[a][b] c;arr[b][a] c;}}for (int i 1; i n; i) {//floydfor (int j 1; j n; j) {for (int k 1; k n; k) {arr[j][k] min(arr[j][k], arr[j][i] arr[i][k]);//从j到k的最短路arr[j][i] arr[i][k]为经过i点中转从j到i再到k}}}arr[s][s] 0;for (int i 1; i n; i) {if (arr[s][i] 0x3F3F3F3F) {cout -1 endl;//还是原本最大值就说明到不了} else {cout arr[s][i] endl;}}return 0;}
邻接表
邻接表构建一个列数可变的二维数组根据节点数定义定义行数 邻接表的优缺点和邻接矩阵的优缺点互补
优点①、省空间②、快速访问以某点为起点的所有点
缺点①不能快速判断两点间的关系
代码演示
基础理解代码
#includeiostream
using namespace std;int n, m, num[105][105][2];int main() {cin n m;for (int i 0; i m; i) {int a, b, c;cin a b c;//a为起点节点b为终点节点c为权值num[a][num[a][0][0]][0] b;num[a][num[a][0][0]][1] c;}for (int i 1; i n; i) {cout i :;for (int j 1; j num[i][0][0]; j) {cout { num[i][j][0] , num[i][j][1] };}cout endl;}return 0;
}
全部代码
#includeiostream
#includevector
using namespace std;
//保存终点节点和此路径的权值也可用键值对来保存
struct edge {int e, v;
};int main() {int n, m;cin n m;//n为节点数m为边数vectorvectoredge edg(n 1, vectoredge());for (int i 0; i m; i) {int a, b, c;cin a b c;edg[a].push_back((edge){b, c});//a为起点节点b为终点节点c为权值}for (int i 1; i n; i) {cout i : ;for (int j 0; j edg[i].size(); j) {cout { i - edg[i][j].e , edg[i][j].v };}cout endl;}return 0;
}
Dijkstra算法
算法解决问题解决单源一个原点最短路径的问题
算法前提不能有负权边负环在环的路径中路径值无限减小没有最短路
核心思想
用一个数组保存一个能到此节点的所有的距离
核心思想图示 代码演示
#includeiostream
#includequeue
#includevector
#includecstring
using namespace std;//每个点的各种状态为了优先队列为一个小顶堆且这个排序根据原点到当前节点的距离排序的目的是为了编号从小到大去遍历
struct node {int now, dis;//now为当前点dis为到这的总长度bool operator (const node b) const {return this-dis b.dis;}
};struct edge {int e, v;//e为当前点的编号v为权值
};//ans[i]数组保存是从原点到编号为i点距离
int n, m, s, ans[100005];int main() {memset(ans, 0x3F, sizeof (ans));cin n m s;//n为节点数m为边数s为源点编号vectorvectoredge edg(n 1, vectoredge());for (int i 0; i m; i) {int a, b, c;//a为起点节点b为终点节点c为权值cin a b c;//无向图edg[a].push_back((edge){b, c});edg[b].push_back((edge){a, c});}priority_queuenode que;//que.push((node){s, 0});//起始元素加入队列, now为sdis为0ans[s] 0;//起点答案置为0while (!que.empty()) {node temp que.top();que.pop();if (temp.dis ans[temp.now]) {//如果答案已被固定也就是此时遍历点的 原点到此点的距离 如果大于 当前点的 原点到此点的距离continue;}//遍历以遍历点为起点的每一条边for (int i 0; i edg[temp.now].size(); i) {int e edg[temp.now][i].e;//temp.now为当前的点的编号e为当前点到达的终点int v edg[temp.now][i].v;//v为当前点到达终点的权值if (ans[e] ans[temp.now] v) {//ans[temp.now]保存的是从原点到当前点的距离如果从原点到当前点的距离和当前点到某终点的权值之和小于从原点到当前点的距离就把这个点放到优先队列且更新从原点到当前点的距离ans[e] ans[temp.now] v;que.push((node){e, ans[e]});}}}for (int i 1; i n; i) {if (ans[i] 0x3F3F3F) {cout -1 endl;} else {cout ans[i] endl;}}return 0;
}
链式前向星
静态链表用一个数组来存节点每个数组元素包括数据域和指针域指针域保存下一个节点的索引 链式前向星采取头插法的静态链表
意义保存每两个有联系点
解释首先需要两个数组一个数组为head这个数组的索引为各个起点编号head[i]保存的是以i为起点的最后一条边最后一个终点的编号另一个数组为静态链表edgedg[i].next保存的是以i这条边同起点的上一条边的编号edg[i].edge保存的是终点编号。
保存过程首先根据一个起始点的编号把终点存到数组中一个空的位置如以编号为1的起始点
首先会把3存到edg[1].edge 3且把head数组中存的最后一个终点的索引放到其指针域edge[1].next head[1]然后在head数组里面保存到目前为止起始点1的最后一条边指向的终点在edg数组的索引head[1] 1
然后就把编号2存到edge[2].edge 2然后一样edge[2].next head[1]更新最后一条边的终点的下标head[1] 2
依此类推…存一条边有三步存编号-换索引存编号edge-留索引next-更新索引head
存一条边代码
//a为起点编号b为终点编号,i为数组中某个空的位置的索引
edg[i].edge b;
edg[i].next head[a];
head[a] i访问过程因为head数组索引为起点编号通过head数组索引开始访问。比如访问起点编号为5
就会访问head[5] 得到一个值5然后根据5这个这个值作为一个索引访问edg数组edg[5].edge得到一个值4所以5-4然后再根据edg[5].next 得到一个索引4然后根据这个索引访问edg[4].edge得到一个值2所以5-2,然后再根据edg[4].next得到一个-1如果是-1说明已经是最后一个了。
依此类推…访问都是从head[i]开始根据edg[i].next得到下一条边的终点
图示 代码演示
#includeiostream
#includecstring
using namespace std;struct node {int e, v, next;
};int n, m, head[105];
node edg[105];int main() {memset(head, -1, sizeof(head));cin n m;//n为节点数m为边数for (int i 0; i m; i) {int a, b, c;//a为起点编号b为终点编号c为边的权值cin a b c;edg[i].e b;//任意选一个空的数组索引把终点编号存进去edg[i].next head[a];//把上一个最后的终点编号保存到指针域edg[i].v c;//存权值head[a] i;//保存最后一个的终点在edg数组中的索引}for (int i 1; i n; i) {cout i :;for (int j head[i]; j ! -1; j edg[j].next) {cout { i - edg[j].e , edg[j].v };}cout endl;}return 0;
}
前向星Dijkstra算法
#includeiostream
#includecstring
#includequeue
using namespace std;struct node {int now, dis;//now为搜索到当前节点的编号dis是从原点到此节点的距离bool operator (const node b) const {return this-dis b.dis;}
};struct edge {int e, v, next;//e为终点编号v为权值next为下一个终点的索引
};int n, m, s, ans[200005], head[200005];//n为节点数m为边数s为起点编号ans[i]为i编号节点的最短距离
edge edg[200005];
int cnt_edge;void add_edge(int a, int b, int c) {edg[cnt_edge].e b;edg[cnt_edge].v c;edg[cnt_edge].next head[a];head[a] cnt_edge;
}int main() {memset(head, -1, sizeof(head));memset(ans, 0x3F, sizeof(ans));cin n m s;for (int i 0; i m; i) {int a, b, c;//a为起点b为终点c为权值cin a b c;add_edge(a, b, c);add_edge(b, a, c);}priority_queuenode que;que.push((node) {s, 0});ans[s] 0;while (!que.empty()) {node temp que.top();que.pop();if (ans[temp.now] temp.dis) {continue;}for (int i head[temp.now]; i ! -1; i edg[i].next) {//遍历以temp.now为前驱节点的所有后继节点int e edg[i].e, v edg[i].v;if (ans[e] temp.dis v) {ans[e] temp.dis v;que.push((node) {e, ans[e]});}}}for (int i 1; i n; i) {if (ans[i] 0x3F3F3F3F) {cout -1 endl;} else {cout ans[i] endl;}}return 0;
}
bellman-ford算法
目的解决单源最短路径问题特殊是可以解决负数权值
bellman-ford算法暴力试每一种可能
核心思想设s为原点到某节点的距离初始化所有节点的s值为最大值然后遍历nn为节点数遍的mm为边数遍也就是以每个节点为起始点去进行搜索每一个节点都要搜索m遍。
代码演示
#includeiostream
#includecstring
using namespace std;struct edge {int s, e, v;
};edge edg[200005];
int n, m, s, edg_cnt, ans[100005];void add_edg(int a, int b, int c) {edg[edg_cnt].s a;edg[edg_cnt].e b;edg[edg_cnt].v c;
}int main() {memset(ans, 0x3F,sizeof(ans));cin n m s;for (int i 0; i m; i) {int a, b, c;cin a b c;add_edg(a, b, c);add_edg(b, a, c);}ans[s] 0;for (int i 1; i n; i) {for (int j 0; j edg_cnt; j) {int s edg[j].s, e edg[j].e, v edg[j].v;ans[e] min(ans[e], ans[s] v);//取终点编号到原点的距离和当前编号到原点距离加上这条边的权值之和中最小的}}for (int i 1; i n; i) {if (ans[i] 0x3F3F3F3F) {cout -1 endl;} else {cout ans[i] endl;}}return 0;
}
基于队列优化的Ballmen-ford算法spfa
由于原本的Ballmen-ford算法中的一些遍历是多余的比如如果没有遍历靠经原点的边就去遍历靠后的边这样的遍历是多余的因为也不会更新。所以引入了队列先遍历靠前的再遍历靠后的。
前提需要一个队列、设置一个ans数组存放最短路径一个mark标记数组标记数组标记的是队列中是否存在这个节点编号入队编号i时就标记mark[i]为1出队就标记为0而且要以某种形式存放每个起始节点的终点节点编号可以是静态链表也可以是邻接表下面代码以静态链表为例所以要构造静态链表就要设置head数组和edg数组head数组存放某起始节点的最后一条终点编号的所在edg数的索引。
过程首先是要有个原点在对队列操作前先把原点插入队列然后就可以进行队列操作了。把队首元素弹出以这个弹出的元素为一个起始编号对其所有的终点做个判断首先判断起始节点编号对应的最短路径数组ans的值加上该起始点到终点的权值和是否小于终点编号对应最短路径数组ans中的值如果小于说明这个路径更短就更新终点编号对应ans中的值再者就根据标记数组判断队列中是否有这个终点编号如果没有就入队。一直操作直到队列中没有元素。
图解 代码演示
#includeiostream
#includequeue
#includecstring
using namespace std;struct edge {int e, v, next;
};edge edg[200005];
int n, m, s,cnt_edg, ans[100005], head[100005], mark[100005];void add_edg(int a, int b, int c) {edg[cnt_edg].e b;edg[cnt_edg].v c;edg[cnt_edg].next head[a];head[a] cnt_edg;
}int main() {memset(ans, 0x3F, sizeof(ans));memset(head, -1, sizeof(head));cin n m s;for (int i 0; i m; i) {int a, b, c;cin a b c;add_edg(a, b, c);add_edg(b, a, c);}queueint que;que.push(s);ans[s] 0;while (!que.empty()) {int temp que.front();que.pop();mark[temp] 0;for (int i head[temp]; i ! -1; i edg[i].next) {int e edg[i].e, v edg[i].v;if (ans[e] ans[temp] v) {ans[e] ans[temp] v;if (mark[e] 0) {mark[e] 1;que.push(e);}}}}for (int i 1; i n; i) {if (ans[i] 0x3F3F3F3F) {cout - 1 endl;} else {cout ans[i] endl;}}return 0;
}
图与最短路径总结
图的存储邻接矩阵O(n*n)、邻接表O(m)、链式前向星(m)
最短路径floyd(邻接矩阵)多源digkstra邻接表链式前向星多源Ballman-ford邻接表链式前向星单源spfa邻接表链式前向星单源负权变
图论-最小生成树
图的最小代价生成树
概念n个节点就选n-1条边最小生成树不一定不一定唯一不一定不唯一最小生成树代价唯一 Kruskal算法
以边求解
意义求解最小生成树
过程对所有边权值排序选出n-1条权值最小边从边权值小的遍历到大的判断两节点是否相连如果相连就不选中否则就是。
图示 代码演示
#includeiostream
#includealgorithm
using namespace std;struct edge {//s为起始点e为终点v为权值而且重载小于号为了排序按权值的大小排序int s, e, v;bool operator (const edge b) const {return this-v b.v;}
};int n, m, ans, cnt, my_union[100005];//n为节点数m为边数my_union数组为并查集ans为最小代价cnt为边数
edge edg[100005];//邻接表存图
//初始化并查集初始每个节点间都不相连为了后面找到树的边
void init() {for (int i 1; i n; i) {my_union[i] i;}
}//并查集的遍历所有节点的编号就是并查集的下标
int find_fa(int x) {//传进一个起始点编号作为下标如果该下索引对应的值就是该索引说明该索引是该树干的最后一个节点if (my_union[x] x) {return x;}//如果不是就顺着下标找因为在连接的时候起始点会存有该起始点连接的一个终点编号对应的值return my_union[x] find_fa(my_union[x]);
}int main() {cin n m;for (int i 0; i m; i) {cin edg[i].s edg[i].e edg[i].v;}//初始化并查集init();//排序sort(edg, edg m);for (int i 0; i m; i) {//分别根据权值的小到大在并查集中找起始点和终点是否连接int fa find_fa(edg[i].s), fb find_fa(edg[i].e);if (fa ! fb) {//如果两点不连接就连接my_union[fa] fb;ans edg[i].v;//加上代价cnt;//树边数加一if (cnt n - 1) {//如果树的边树够了说明已经生成最小树就输出返回cout ans endl;return 0;}}}cout -1 endl;return 0;
}
代码图解包括小到大并查集操作和递归操作解释 Prim算法
以点求解最小生成树
意义求解最小生成树
过程以某个点为源点向外扩散每次选一条权值最小的边
图示 代码演示
#includeiostream
#includequeue
#includecstring
using namespace std;//e为终点v为权值并且为了后面的堆排序所以重载小于号
struct node {int e, v;bool operator (const node b) const {return this-v b.v;}
};//为后面链式前向星准备
struct edge {int e, v, next;
};edge edg[200005];
int n, m, edg_cnt, ans, mark[100005], cnt, head[100005];//链式前向星存图
void add_edg(int a, int b, int c) {edg[edg_cnt].e b;edg[edg_cnt].v c;edg[edg_cnt].next head[a];head[a] edg_cnt;
}int main() {memset(head, -1, sizeof(head));cin n m;for (int i 0; i m; i) {int a, b, c;cin a b c;add_edg(a, b, c);add_edg(b, a, c);}priority_queuenode que;que.push((node){(n / 4 0 ? 1 : n / 4), 0});while (!que.empty()) {node temp que.top();que.pop();//如果弹出的节点的终点已经连接就不再进行判断连接总结continueif (mark[temp.e] 1) {continue;} //如果没有连接就把该节点标记为1意为连接mark[temp.e] 1;//代价加上权值ans temp.v;//边数加一cnt;//如果已经形成树就返回if (cnt n - 1) {cout ans endl;return 0;}//对一个节点的所以终点进行操作没有连接就把该终点放到队列中for (int i head[temp.e]; i ! -1; i edg[i].next) {int e edg[i].e, v edg[i].v;if (mark[e] 0) {que.push((node) {e, v});}}}cout -1 endl;return 0;
}
图论-拓扑排序
拓扑排序求解1、找入度为0的节点 2、找到该点后删除所有以其为起点的边删除其实就是入度减一。
性质拓扑排序不唯一因为可能同时有多个入度为0的点。
应用判断图是否带环 代码演示
#includeiostream
#includecstring
#includequeue
using namespace std;//用于链式前向星存图
struct edge {int e, next;
};edge edg[1005];
//num数组保存答案in_degree数组统计入度
int n, m, head[105], num[105], cnt, in_degree[105];int main() {memset(head, -1, sizeof(head));cin n m;for (int i 0; i m; i) {int a, b;cin a b;in_degree[b];//计数入度edg[i].e b;edg[i].next head[a];head[a] i;}//queueint que;priority_queueint, vectorint, greaterint que;//因为拓扑排序有多个结果所以为了从小到大就用一个小顶堆//队列que保存所有入度为0的元素for (int i 1; i n; i) {if (in_degree[i] 0) {que.push(i);}}while (!que.empty()) {int temp que.top();que.pop();//计数存答案num[cnt] temp;//对每个终点的入度减一如果该入度为0就入队否则就不需要入队for (int i head[temp]; i ! -1; i edg[i].next) {int e edg[i].e;in_degree[e]--;if (in_degree[e] 0) {que.push(e);}}}//如果是环就输出no因为有环就不能把所有的节点都入队一遍所以肯定小于节点数if (cnt ! n ) {cout no endl;return 0;}//否则输出这个顺序for (int i 0; i cnt; i) {i cout ;cout num[i] ;}cout endl;return 0;}
输出所有拓扑排序
#includeiostream
#includevector
using namespace std;int n, m, f, num[105], in_degree[105], mark[105];void func(int now, vectorvectorint edg) {if (now n 1) {//当递归到最后一个节点就输出for (int i 1; i n; i) {cout num[i] ;}cout endl;f 1;return ;}for (int i 1; i n; i) {//遍历每个节点编号if (in_degree[i] 0 mark[i] 0) {//入度为0且没有遍历过就进行遍历num[now] i;mark[i] 1; for (int j 0; j edg[i].size(); j) {//把当前起点的所有的终点的入度减一in_degree[edg[i][j]]--;}func(now 1, edg);//在递归过程会不断地对入度减一直到最后一个节点遍历完。比如最后一层输出完毕后就会执行以下代码把标记还原把入度还原这就是搜索回溯回到前一个度数多的一个节点mark[i] 0;for (int j 0; j edg[i].size(); j) {in_degree[edg[i][j]];}}}
}int main() {cin n m;vectorvectorint edg(n 1, vectorint());for (int i 0; i m; i) {int a, b;cin a b;in_degree[b];edg[a].push_back(b);}func(1, edg);if (f 0) {cout no endl;}return 0;
}
