虚拟主机怎么建设网站,网站功能设计指什么,湖南大和品牌设计有限公司,做个人网页图论 文章目录 图论图的存储与深度、广度遍历基础定义代码实现其他补充 并查集基础定义代码实现 最小生成树基础定义代码实现**Kruskal算法**prim算法 拓扑排序基础定义思路分析代码实现 最短路径基础定义代码实现Dijkstra算法Bellman-Ford算法Floyd算法 图的存储与深度、广度遍…图论 文章目录 图论图的存储与深度、广度遍历基础定义代码实现其他补充 并查集基础定义代码实现 最小生成树基础定义代码实现**Kruskal算法**prim算法 拓扑排序基础定义思路分析代码实现 最短路径基础定义代码实现Dijkstra算法Bellman-Ford算法Floyd算法 图的存储与深度、广度遍历
基础定义
存储方式
**邻接矩阵**如果图有 N 个节点那么矩阵的维度为 N×N矩阵中的每个元素 A[i] [j] 表示节点 i 和节点 j 之间是否存在边。 [!NOTE] 邻接矩阵适用于稠密图 **邻接表**在邻接表表示法中每个节点都有一个列表该列表存储与该节点直接相连的所有节点。 [!NOTE] 邻接表适用于稀疏图 遍历方式
DFS深度优先搜索从一个选定的节点开始沿着每一条分支尽可能深入地探索直到不能继续为止然后回溯到上一个节点继续探索其他未访问的分支。
深搜三部曲
1、确认递归函数参数
2、确认终止条件一般是判断是否visited [!NOTE] 在DFS中栈在任何时刻都只包含从起始点的下一个点到当前探索点的路径,在岛屿问题中如果岛屿退化成一条链那么栈里就是岛屿上所有的土地-1。 BFS广度优先搜索按层次逐层探索图先访问当前深度层次的所有节点然后再进入下一深度层次的节点。 [!NOTE] 在BFS中队列在某些时刻可能会包含岛屿的所有或大部分土地节点例如岛屿在某一层上的宽度或周长 如果岛屿是一条长链1xN的形状那么队列的最大大小将始终为1或2因为在任何时候只有一个或两个节点正在被处理。如果岛屿是一个正方形NxN的形状队列的最大大小可能接近岛屿的周长4N-4。 代码实现
DFS (邻接矩阵)
#include iostream
#include vector
using namespace std;
vectorvectorint result; // 收集符合条件的路径
vectorint path; // 1节点到终点的路径void dfs (const vectorvectorint graph, int x, int n) {// 当前遍历的节点x 到达节点n if (x n) { // 找到符合条件的一条路径result.push_back(path);return;}for (int i 1; i n; i) { // 遍历节点x链接的所有节点if (graph[x][i] 1) { // 找到 x链接的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯撤销本节点}}
}int main() {int n, m, s, t;cin n m;// 节点编号从1到n所以申请 n1 这么大的数组vectorvectorint graph(n 1, vectorint(n 1, 0));while (m--) {cin s t;// 使用邻接矩阵 表示无线图1 表示 s 与 t 是相连的graph[s][t] 1;}path.push_back(1); // 无论什么路径已经是从0节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.size() 0) cout -1 endl;for (const vectorint pa : result) {for (int i 0; i pa.size() - 1; i) {cout pa[i] ;}cout pa[pa.size() - 1] endl;}
}DFS (邻接表)
#includeiostream
#includevector
#includelist
using namespace std;
vectorvectorint result;
vectorintpath;
void dfs(vectorlistintgraph,int x,int n){if(xn){result.push_back(path);return;}for(int m:graph[x]){path.push_back(m);dfs(graph,m,n);path.pop_back();}
}int main(){int a,b;cinab;vectorlistintgraph(a1);while(b--){int s,t;cinst;graph[s].push_back(t);}path.push_back(1);dfs(graph,1,a);if (result.size() 0) cout -1 endl;for (const vectorint pa : result) {for (int i 0; i pa.size() - 1; i) {cout pa[i] ;}cout pa[pa.size() - 1] endl;}
}BFS (邻接矩阵)
#include iostream
#include vector
#include queue
using namespace std;const int MAX_N 1000; // 最大顶点数
vectorvectorint graph(MAX_N, vectorint(MAX_N, 0));
vectorbool visited(MAX_N, false);
int n; // 顶点数void bfs(int start) {queueint q;q.push(start);visited[start] true;while (!q.empty()) {int v q.front();q.pop();cout v ;for (int i 0; i n; i) {if (graph[v][i] !visited[i]) {q.push(i);visited[i] true;}}}
}int main() {int m; // 边数cin n m;for (int i 0; i m; i) {int u, v;cin u v;graph[u][v] graph[v][u] 1;}bfs(0); // 从顶点0开始BFSreturn 0;
}BFS (邻接表)
#include iostream
#include vector
#include queue
using namespace std;const int MAX_N 1000; // 最大顶点数
vectorvectorint graph(MAX_N);
vectorbool visited(MAX_N, false);
int n; // 顶点数void bfs(int start) {queueint q;q.push(start);visited[start] true;while (!q.empty()) {int v q.front();q.pop();cout v ;for (int u : graph[v]) {if (!visited[u]) {q.push(u);visited[u] true;}}}
}int main() {int m; // 边数cin n m;// 确保输入的顶点数不超过最大限制if (n MAX_N) {cout 顶点数超过最大限制 endl;return 1;}// 读入边并构建图for (int i 0; i m; i) {int u, v;cin u v;// 确保顶点编号在有效范围内if (u 0 u n v 0 v n) {graph[u].push_back(v);graph[v].push_back(u);} else {cout 无效的顶点编号 endl;return 1;}}bfs(0); // 从顶点0开始BFSreturn 0;
}
其他补充
1、图的坐标轴与数学坐标轴不同图以x轴垂直向下y轴水平向右为正对此dir数组的表示也不同。
上下左右{-10}{10}{0-1}{-10}
2、在二叉树中深度优先遍历包括中序、前序、后序广度优先遍历是层序遍历。
并查集
基础定义
并查集是一种处理集合与集合关系的数据结构主要包含查询两个元素是否属于同一集合和将两个不同的集合合成一个新的大集合。
查询find是否同属于一个“父亲”添加join将两个集合添加进同一个“父亲”底下路径压缩为了使查找到效率达到O(1)将同一棵树下的所有节点的父节点指向根节点。
代码实现
int n 1005; // n根据题目中节点数量而定一般比节点数量大一点就好
vectorint father vectorint (n, 0); // C里的一种数组结构// 并查集初始化
void init() {for (int i 0; i n; i) {father[i] i;}
}
// 并查集里寻根的过程
int find(int u) {return u father[u] ? u : father[u] find(father[u]); // 路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u find(u);v find(v);return u v;
}// 将v-u 这条边加入并查集
void join(int u, int v) {u find(u); // 寻找u的根v find(v); // 寻找v的根if (u v) return ; // 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v] u;
}按秩优化
int n 1005; // n根据题目中节点数量而定一般比节点数量大一点就好
vectorint father vectorint (n, 0); // C里的一种数组结构
vectorint rank vectorint (n, 1); // 初始每棵树的高度都为1// 并查集初始化
void init() {for (int i 0; i n; i) {father[i] i;rank[i] 1; // 也可以不写}
}
// 并查集里寻根的过程
int find(int u) {return u father[u] ? u : find(father[u]);// 注意这里不做路径压缩
}// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {u find(u);v find(v);return u v;
}// 将v-u 这条边加入并查集
void join(int u, int v) {u find(u); // 寻找u的根v find(v); // 寻找v的根if (rank[u] rank[v]) father[u] v; // rank小的树合入到rank大的树else father[v] u;if (rank[u] rank[v] u ! v) rank[v]; // 如果两棵树高度相同则v的高度1因为上面 if (rank[u] rank[v]) father[u] v; 注意是
}最小生成树
基础定义
最小生成树Minimum Spanning Tree, MST是一个连通无向图的子图它包含图中所有的顶点并且边的权重之和最小。最小生成树具有以下特性
连通性包含所有节点并保持连通。无环性不包含环。最小权重边的权重之和最小。
常用的算法有
Kruskal 算法按权重升序对边排序然后使用并查集逐步添加边避免环的形成。Prim 算法从任意节点开始逐步扩展生成树选择权重最小的边连接到未包含的节点。
代码实现
Kruskal算法
思路定义
边的权值排序因为要优先选最小的边加入到生成树里遍历排序后的边 如果边首尾的两个节点在同一个集合说明如果连上这条边图中会出现环如果边首尾的两个节点不在同一个集合加入到最小生成树并把两个节点加入同一个集合
需求分析
如何实现优先选择最小的边非for循环遍历 可以建立一个小顶堆保证堆顶元素即为最小的边。 判断是否属于同一个集合 并查集。
具体代码
#include iostream
#include vector
#include algorithmusing namespace std;// l,r为 边两边的节点val为边的数值
struct Edge {int l, r, val;
};// 节点数量
int n 10001;
// 并查集标记节点关系的数组
vectorint father(n, -1); // 节点编号是从1开始的n要大一些// 并查集初始化
void init() {for (int i 0; i n; i) {father[i] i;}
}// 并查集的查找操作
int find(int u) {return u father[u] ? u : father[u] find(father[u]); // 路径压缩
}// 并查集的加入集合
void join(int u, int v) {u find(u); // 寻找u的根v find(v); // 寻找v的根if (u v) return ; // 如果发现根相同则说明在一个集合不用两个节点相连直接返回father[v] u;
}int main() {int v, e;int v1, v2, val;vectorEdge edges;int result_val 0;cin v e;while (e--) {cin v1 v2 val;edges.push_back({v1, v2, val});}// 执行Kruskal算法// 按边的权值对边进行从小到大排序sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) {return a.val b.val;});// 并查集初始化init();// 从头开始遍历边for (Edge edge : edges) {// 并查集搜出两个节点的祖先int x find(edge.l);int y find(edge.r);// 如果祖先不同则不在同一个集合if (x ! y) {result_val edge.val; // 这条边可以作为生成树的边join(x, y); // 两个节点加入到同一个集合}}cout result_val endl;return 0;
}时间复杂度nlogn 快排 logn 并查集 所以最后依然是 nlogn 。n为边的数量。
扩展
如果是要输出最小生成树都有哪些边
#include iostream
#include vector
#include algorithmusing namespace std;struct Edge {int l, r, val;
};int n 10001;vectorint father(n, -1); void init() {for (int i 0; i n; i) {father[i] i;}
}int find(int u) {return u father[u] ? u : father[u] find(father[u]);
}void join(int u, int v) {u find(u); v find(v); if (u v) return ; father[v] u;
}int main() {int v, e;int v1, v2, val;vectorEdge edges;int result_val 0;cin v e;while (e--) {cin v1 v2 val;edges.push_back({v1, v2, val});}sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) {return a.val b.val;});vectorEdge result; // 存储最小生成树的边init();for (Edge edge : edges) {int x find(edge.l);int y find(edge.r);if (x ! y) {result.push_back(edge); // 保存最小生成树的边result_val edge.val; join(x, y);}}// 打印最小生成树的边for (Edge edge : result) {cout edge.l - edge.r : edge.val endl;}return 0;
}prim算法
思路定义
第一步选距离生成树最近节点val最小第二步最近节点加入生成树第三步更新非生成树节点到生成树的距离即更新minDist数组
minDist数组 用来记录 每一个节点距离最小生成树的最近距离。
需求分析
需要个数组
1、存图数组
2、最小生成树数组
3、minDist数组
4、是否已经在树中数组
代码实现
#includeiostream
#includevector
#include climitsusing namespace std;
int main() {int v, e;int x, y, k;cin v e;// 填一个默认最大值题目描述val最大为10000vectorvectorint grid(v 1, vectorint(v 1, 10001));while (e--) {cin x y k;// 因为是双向图所以两个方向都要填上grid[x][y] k;grid[y][x] k;}// 所有节点到最小生成树的最小距离vectorint minDist(v 1, 10001);// 这个节点是否在树里vectorbool isInTree(v 1, false);// 我们只需要循环 n-1次建立 n - 1条边就可以把n个节点的图连在一起for (int i 1; i v; i) {// 1、prim三部曲第一步选距离生成树最近节点int cur -1; // 选中哪个节点 加入最小生成树int minVal INT_MAX;for (int j 1; j v; j) { // 1 - v顶点编号这里下标从1开始// 选取最小生成树节点的条件// 1不在最小生成树里// 2距离最小生成树最近的节点if (!isInTree[j] minDist[j] minVal) {minVal minDist[j];cur j;}}// 2、prim三部曲第二步最近节点cur加入生成树isInTree[cur] true;// 3、prim三部曲第三步更新非生成树节点到生成树的距离即更新minDist数组// cur节点加入之后 最小生成树加入了新的节点那么所有节点到 最小生成树的距离即minDist数组需要更新一下// 由于cur节点是新加入到最小生成树那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢for (int j 1; j v; j) {// 更新的条件// 1节点是 非生成树里的节点// 2与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小// 很多录友看到自己 就想不明白什么意思其实就是 cur 是新加入 最小生成树的节点那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入需要更新一下数据了if (!isInTree[j] grid[cur][j] minDist[j]) {minDist[j] grid[cur][j];}}}// 统计结果int result 0;for (int i 2; i v; i) { // 不计第一个顶点因为统计的是边的权值v个节点有 v-1条边result minDist[i];}cout result endl;}扩展
如果是把边记录下下来
#includeiostream
#includevector
#include climitsusing namespace std;
int main() {int v, e;int x, y, k;cin v e;vectorvectorint grid(v 1, vectorint(v 1, 10001));while (e--) {cin x y k;grid[x][y] k;grid[y][x] k;}vectorint minDist(v 1, 10001);vectorbool isInTree(v 1, false);//加上初始化vectorint parent(v 1, -1);for (int i 1; i v; i) {int cur -1;int minVal INT_MAX;for (int j 1; j v; j) {if (!isInTree[j] minDist[j] minVal) {minVal minDist[j];cur j;}}isInTree[cur] true;for (int j 1; j v; j) {if (!isInTree[j] grid[cur][j] minDist[j]) {minDist[j] grid[cur][j];parent[j] cur; // 记录边}}}// 输出 最小生成树边的链接情况for (int i 1; i v; i) {cout i - parent[i] endl;}
}拓扑排序
基础定义
给出一个 有向图把这个有向图转成线性的排序 就叫拓扑排序。
类似于大学排课有一些课程需要其他课程学完了才能学其他课程就称为该课程的依赖关系。
思路分析
找到入度为0 的节点加入结果集将该节点从图中移除
结果集的顺序就是我们想要的拓扑排序顺序 结果集里顺序可能不唯一
这里可以采用广搜或者深搜。
代码实现
#include iostream
#include vector
#include queue
#include unordered_map
using namespace std;
int main() {int m, n, s, t;cin n m;vectorint inDegree(n, 0); // 记录每个文件的入度unordered_mapint, vectorint umap;// 记录文件依赖关系vectorint result; // 记录结果while (m--) {// s-t先有s才能有tcin s t;inDegree[t]; // t的入度加一umap[s].push_back(t); // 记录s指向哪些文件}queueint que;for (int i 0; i n; i) {// 入度为0的文件可以作为开头先加入队列if (inDegree[i] 0) que.push(i);//cout inDegree[i] endl;}// int count 0;while (que.size()) {int cur que.front(); // 当前选中的文件que.pop();//count;result.push_back(cur);vectorint files umap[cur]; //获取该文件指向的文件if (files.size()) { // cur有后续文件for (int i 0; i files.size(); i) {inDegree[files[i]]--; // cur的指向的文件入度-1if(inDegree[files[i]] 0) que.push(files[i]);}}}if (result.size() n) {for (int i 0; i n - 1; i) cout result[i] ;cout result[n - 1];} else cout -1 endl;}最短路径
基础定义
在图中从一个起点到一个终点的路径使得路径上边的权重之和最小。
Dijkstra算法 适用于非负权重图。使用优先队列逐步扩展最短路径。 Bellman-Ford算法 适用于有负权边的图。可以检测负权环。 Floyd-Warshall算法 适用于计算所有节点对之间的最短路径。使用动态规划解决。
代码实现
Dijkstra算法
通过贪心算法
第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组
minDist数组 用来记录 每一个节点距离源点的最小距离。
#include iostream
#include vector
#include climits
using namespace std;int main() {int n, m, p1, p2, val;cin n m;vectorvectorint grid(n 1, vectorint(n 1, INT_MAX));for(int i 0; i m; i){cin p1 p2 val;grid[p1][p2] val;}int start 1;int end n;// 存储从源点到每个节点的最短距离vectorint minDist(n 1, INT_MAX);// 记录顶点是否被访问过vectorbool visited(n 1, false);minDist[start] 0; // 起始点到自身的距离为0for (int i 1; i n; i) { // 遍历所有节点int minVal INT_MAX;int cur 1;// 1、选距离源点最近且未访问过的节点for (int v 1; v n; v) {if (!visited[v] minDist[v] minVal) {minVal minDist[v];cur v;}}visited[cur] true; // 2、标记该节点已被访问// 3、第三步更新非访问节点到源点的距离即更新minDist数组for (int v 1; v n; v) {if (!visited[v] grid[cur][v] ! INT_MAX minDist[cur] grid[cur][v] minDist[v]) {minDist[v] minDist[cur] grid[cur][v];}}}if (minDist[end] INT_MAX) cout -1 endl; // 不能到达终点else cout minDist[end] endl; // 到达终点最短路径}对于此也有优化版
代码随想录
Bellman-Ford算法
初始化 将源点的距离初始化为 0其他所有节点的距离初始化为正无穷大。 松弛操作 对所有边进行 V−1 次迭代V 是节点数。对于每条边 (u,v)如果 distance[u]weight(u,v)distance[v]则更新 distance[v]。 检测负权环 在第 V 次迭代中再次尝试松弛所有边。如果还能更新任意节点的距离则图中存在负权环。
#include iostream
#include vector
#include list
#include climits
using namespace std;int main() {int n, m, p1, p2, val;cin n m;vectorvectorint grid;// 将所有边保存起来for(int i 0; i m; i){cin p1 p2 val;// p1 指向 p2权值为 valgrid.push_back({p1, p2, val});}int start 1; // 起点int end n; // 终点vectorint minDist(n 1 , INT_MAX);minDist[start] 0;for (int i 1; i n; i) { // 对所有边 松弛 n-1 次for (vectorint side : grid) { // 每一次松弛都是对所有边进行松弛int from side[0]; // 边的出发点int to side[1]; // 边的到达点int price side[2]; // 边的权值// 松弛操作 // minDist[from] ! INT_MAX 防止从未计算过的节点出发if (minDist[from] ! INT_MAX minDist[to] minDist[from] price) { minDist[to] minDist[from] price; }}}if (minDist[end] INT_MAX) cout unconnected endl; // 不能到达终点else cout minDist[end] endl; // 到达终点最短路径}Floyd算法
Floyd-Warshall算法用于计算所有节点对之间的最短路径。它适用于带权有向图可以处理负权边但不能处理负权环。
初始化 创建一个距离矩阵 dist将每个节点对的距离初始化为边权重对于没有直接边的节点对初始化为正无穷大。对角线元素自身到自身的距离初始化为 0。 动态规划 逐步引入每个节点作为中间节点更新距离矩阵。对于每对节点 (i,j)检查是否通过中间节点 kk 可以缩短路径 dist[i] [j]min(dist[i] [j],dist[i] [k]dist[k] [j]) 检测负权环 如果在最终的距离矩阵中任何 dist[i][i]dist[i][i] 变为负数则存在负权环。
**dp数组的定义如下**grid[i] [j] [k] m表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。
#include iostream
#include vector
#include list
using namespace std;int main() {int n, m, p1, p2, val;cin n m;// 创建一个三维向量 grid用于存储节点之间的最短路径距离// 初始化为 10005表示初始时节点之间不可达假设边的最大权重为 10000vectorvectorvectorint grid(n 1, vectorvectorint(n 1, vectorint(n 1, 10005))); // 读取图的边信息for(int i 0; i m; i){cin p1 p2 val;grid[p1][p2][0] val; // 设置 p1 到 p2 的初始距离grid[p2][p1][0] val; // 因为是无向图所以还要设置 p2 到 p1 的距离}// 开始 Floyd-Warshall 算法for (int k 1; k n; k) { // k 表示中间节点for (int i 1; i n; i) { // i 表示起始节点for (int j 1; j n; j) { // j 表示终止节点// 更新 i 到 j 的最短路径考虑通过 k 的路径grid[i][j][k] min(grid[i][j][k-1], grid[i][k][k-1] grid[k][j][k-1]);}}}// 处理查询int z, start, end;cin z;while (z--) {cin start end;// 输出从 start 到 end 的最短路径// 如果距离仍为初始值 10005表示不可达输出 -1if (grid[start][end][n] 10005) cout -1 endl;else cout grid[start][end][n] endl;}
}
