算法学习 | 忆昔

BPS

定义vector<vector> graph，作为邻接表
定义vector visited[标记数组],用来记录图中成员是否已被访问
定义队列queue q，存储已被访问的成员
开始节点入队，并标记为已访问

队列不为空，循环取出第一个结点并遍历其所有邻居，未被访问的元素入队

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

void bfs(vector<vector<int>>& graph, int start) {
    // 节点数量
    int n = graph.size();
    
    // 访问标记数组
    vector<bool> visited(n, false);
    
    // 队列用于BFS
    queue<int> q;

    // 开始节点入队并标记为已访问
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        // 取出队列中的第一个节点
        int node = q.front();
        q.pop();
        cout << node << " "; // 打印节点

        // 遍历该节点的所有邻居
        for (int neighbor : graph[node]) {
            // 如果邻居未被访问
            if (!visited[neighbor]) {
                // 标记为已访问并入队
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}
```  
----
## **DPS**  
1. 定义vector<vector<int>> graph，作为邻接表
2. 定义vector<bool> visited[标记数组],用来记录图中成员是否已被访问
3. 定义栈stack<int> s模拟递归，或直接使用递归
4. 栈不为空，循环取出栈顶元素并遍历其所有邻居，未被访问的元素入队
```C++  
#include <iostream>
#include <vector>
#include <stack>

using namespace std;
//使用递归
void dfs(vector<vector<int>>& graph, int node, vector<bool>& visited) {
    // 打印当前节点
    cout << node << " ";
    
    // 标记当前节点为已访问
    visited[node] = true;

    // 遍历当前节点的所有邻居
    for (int neighbor : graph[node]) {
        // 如果邻居未被访问，则递归调用DFS
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}
//使用栈
void dfs(vector<vector<int>>& graph, int start) {
    // 节点数量
    int n = graph.size();
    
    // 访问标记数组
    vector<bool> visited(n, false);

    // 使用栈来模拟递归
    stack<int> s;

    // 起始节点入栈
    s.push(start);

    while (!s.empty()) {
        // 取栈顶元素
        int node = s.top();
        s.pop();

        // 如果节点未被访问
        if (!visited[node]) {
            // 打印节点并标记为已访问
            cout << node << " ";
            visited[node] = true;

            // 将当前节点的所有邻居入栈
            for (int i = graph[node].size() - 1; i >= 0; --i) {
                if (!visited[graph[node][i]]) {
                    s.push(graph[node][i]);
                }
            }
        }
    }
}
```  

## **Dijkstra**  
```C++  
#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

typedef pair<int, int> iPair;

void dijkstra(vector<vector<pair<int, int>>>& graph, int start) {
    int V = graph.size(); // 图中节点的数量

    // 距离数组，初始化为最大值
    vector<int> dist(V, numeric_limits<int>::max());

    // 记录最短路径中的前驱节点
    vector<int> parent(V, -1);

    // 优先队列，用于存储 {距离, 节点} 对
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;

    // 起始节点的距离为0
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        // 从优先队列中取出距离最小的节点
        int u = pq.top().second;
        pq.pop();

        // 遍历该节点的所有邻居
        for (auto& neighbor : graph[u]) {
            int v = neighbor.first; // 邻居节点
            int weight = neighbor.second; // 到邻居的权重

            // 如果通过当前节点到邻居的路径更短
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
                parent[v] = u;
            }
        }
    }

    // 打印最短路径和距离
    for (int i = 0; i < V; ++i) {
        if (i != start) {
            cout << "最短路径从 " << start << " 到 " << i << " 是: ";
            vector<int> path;
            for (int at = i; at != -1; at = parent[at])
                path.push_back(at);
            reverse(path.begin(), path.end());
            for (int j = 0; j < path.size(); ++j) {
                cout << path[j];
                if (j != path.size() - 1) cout << " -> ";
            }
            cout << ", 距离是: " << dist[i] << endl;
        }
    }
}