圖的基礎知識【這部分建議使用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;
}