河西网站建设,世界优秀摄影作品网站,网站支付链接怎么做的,太姥山镇建设的网站图的基础知识【这部分建议使用acm模式】
图论理论基础 | 代码随想录
存储#xff1a;
一般有邻接表【适合稀疏图】【数组 链表 】和邻接矩阵【适合稠密图】存储方式
注意邻接表 和 邻接矩阵的写法都要掌握#xff01;
邻接矩阵 n个节点#xff0c;申请n*n或者#xf…图的基础知识【这部分建议使用acm模式】
图论理论基础 | 代码随想录
存储
一般有邻接表【适合稀疏图】【数组 链表 】和邻接矩阵【适合稠密图】存储方式
注意邻接表 和 邻接矩阵的写法都要掌握
邻接矩阵 n个节点申请n*n或者n1*n1大小的二维数组 vectorvectorintvec(n1,vectorint(n1)); //m条边 while(m--){ cinst; vec[s][t] 1;//可达 } 邻接表【数组链表】 vectorlistintgraph(n1);//list是c中的链表 while(m--){ cinst; graph[s].push_back(t); } 图的遍历
dfs是可一个方向去搜不到黄河不回头直到遇到绝境了搜不下去了再换方向换方向的过程就涉及到了回溯。
关于为何回溯 原来走的是1,2到了终点需要返回5的位置重新搜 bfs是先把本节点所连接的所有节点遍历一遍走到下一个节点的时候再把连接节点的所有节点遍历一遍搜索方向更像是广度四面八方的搜索过程。
dfs【联想当初的回溯】 1.递归结束条件到终点 2.递归过程 遍历每一个节点加入路径中 回溯继续往深遍历 98. 所有可达路径
遍历第一个节点到最后一个节点的所有路径
void dfs(int i,int N,vectorvectorintgraph){if(iN-1){res.push_back(path);return;}for(int j 0;jN;j){if(geaph[i][j] 1){path.push_bak(j);}dfs(j,N,graph);// dfs(i1,N,graph);//下一层递归path.pop_back();// dfs(i1,N,graph);}
}
bfs【围绕起点一圈一圈搜索】
上下左右
模板关键点 dir[4][2]四个方向右、下、左、上。 visited防止重复访问否则会死循环。 越界检查nextx和nexty不能超出地图范围。 关于dir:(0,1),(1,0),(-1,0),(0,-1表示四个方向
int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图也就是一个二维数组
// visited标记访问过的节点不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vectorvectorchar grid, vectorvectorbool visited, int x, int y) {queuepairint, int que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] true; // 只要加入队列立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pairint ,int cur que.front(); que.pop(); // 从队列取元素int curx cur.first;int cury cur.second; // 当前节点坐标for (int i 0; i 4; i) { // 开始想当前节点的四个方向左右上下去遍历int nextx curx dir[i][0];int nexty cury dir[i][1]; // 获取周边四个方向的坐标if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue; // 坐标越界了直接跳过if (!visited[nextx][nexty]) { // 如果节点没被访问过que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点visited[nextx][nexty] true; // 只要加入队列立刻标记避免重复访问}}}} 拓扑排序
#include vector
#include queue
using namespace std;vectorint topologicalSort(int n, vectorpairint, int edges) {vectorvectorint graph(n);vectorint inDegree(n, 0);// 建图 计算入度for (auto edge : edges) {int u edge.first, v edge.second;graph[u].push_back(v);inDegree[v];}// 初始化队列入度为0的节点queueint q;for (int i 0; i n; i) {if (inDegree[i] 0) q.push(i);}// 执行拓扑排序vectorint topoOrder;while (!q.empty()) {int u q.front();q.pop();topoOrder.push_back(u);for (int v : graph[u]) {if (--inDegree[v] 0) {q.push(v);}}}if (topoOrder.size() ! n) return {}; // 有环return topoOrder;
}
dj算法
小根堆得到当前的路径min
#include vector
#include queue
#include climits
using namespace std;
typedef pairint, int pii; // {distance, node}vectorint dijkstra(int n, vectorvectorpii graph, int start) {vectorint dist(n, INT_MAX);dist[start] 0;priority_queuepii, vectorpii, greaterpii pq; // 小根堆pq.push({0, start});while (!pq.empty()) {auto [d, u] pq.top();pq.pop();if (d dist[u]) continue; // 已处理过更优解for (auto [v, w] : graph[u]) {if (dist[v] dist[u] w) {dist[v] dist[u] w;pq.push({dist[v], v});}}}return dist;
}
