图的基础知识【这部分建议使用acm模式】

图论理论基础 | 代码随想录

存储：

一般有邻接表【适合稀疏图】【数组 + 链表】和邻接矩阵【适合稠密图】存储方式

注意邻接表和邻接矩阵的写法都要掌握！

邻接矩阵

n个节点，申请n*n或者（n+1）*（n+1）大小的二维数组

vector<vector<int>>vec(n+1,vector<int>(n+1));

//m条边

while(m--){

cin>>s>>t;

vec[s][t] = 1;//可达

}

邻接表【数组+链表】

vector<list<int>>graph(n+1);//list是c++中的链表

while(m--){

cin>>s>>t;

graph[s].push_back(t);

}

图的遍历

dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。

关于为何回溯：

原来走的是1,2，到了终点，需要返回5的位置重新搜

bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

dfs【联想当初的回溯】

1.递归结束条件：到终点

2.递归过程

遍历每一个节点，加入路径中

回溯，继续往深遍历

98. 所有可达路径

遍历第一个节点到最后一个节点的所有路径

void dfs(int i,int & N,vector<vector<int>>&graph){if(i==N-1){res.push_back(path);return;}for(int j = 0;j<N;j++){if(geaph[i][j] == 1){path.push_bak(j);}dfs(j,N,graph);// dfs(i+1,N,graph);//下一层递归path.pop_back();// dfs(i+1,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(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {queue<pair<int, int>> que; // 定义队列que.push({x, y}); // 起始节点加入队列visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点while(!que.empty()) { // 开始遍历队列里的元素pair<int ,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;vector<int> topologicalSort(int n, vector<pair<int, int>>& edges) {vector<vector<int>> graph(n);vector<int> inDegree(n, 0);// 建图 & 计算入度for (auto& edge : edges) {int u = edge.first, v = edge.second;graph[u].push_back(v);inDegree[v]++;}// 初始化队列（入度为0的节点）queue<int> q;for (int i = 0; i < n; ++i) {if (inDegree[i] == 0) q.push(i);}// 执行拓扑排序vector<int> 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 pair<int, int> pii; // {distance, node}vector<int> dijkstra(int n, vector<vector<pii>>& graph, int start) {vector<int> dist(n, INT_MAX);dist[start] = 0;priority_queue<pii, vector<pii>, greater<pii>> 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;
}