Dijkstra 算法模板及应用

// vector<type> name 表示定义一个元素类型为 type 的动态数组 name
// graph[s] 存储节点 s 指向的节点（出度）
vector<int>[] graph;

// 输入节点 s 返回 s 的相邻节点
vector<int> adj(int s);

vector<int>* graph;

// 输入节点 s，返回 s 的相邻节点
vector<int> adj(int s) {
    return graph[s];
}

// 返回节点 from 到节点 to 之间的边的权重
int weight(int from, int to);

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
int levelTraverse(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> q;
    q.push(root);

    int depth = 1;
    // 从上到下遍历二叉树的每一层
    while (!q.empty()) {
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            printf("节点 %s 在第 %s 层", cur, depth);

            // 将下一层节点放入队列
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
    return depth;
}

void levelTraverse(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);

    int depth = 1;
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            printf("节点 %s 在第 %s 层", cur, depth);

            for (auto child : cur->children) {
                q.push(child);
            }
        }
        depth++;
    }
}

#include <queue>
#include <set>

// 输入起点，进行 BFS 搜索
int BFS(Node* start) {
    // 核心数据结构
    std::queue<Node*> q;
    // 避免走回头路
    std::set<Node*> visited;
    
    // 将起点加入队列
    q.push(start);
    visited.insert(start);

    // 记录搜索的步数
    int step = 0;
    while (!q.empty()) {
        int sz = q.size();
        // 将当前队列中的所有节点向四周扩散一步
        for (int i = 0; i < sz; i++) {
            Node* cur = q.front();
            q.pop();
            printf("从 %s 到 %s 的最短距离是 %s", start->val, cur->val, step);

            // 将 cur 的相邻节点加入队列
            for (Node* x : cur->adj()) {
                if (visited.count(x) == 0) {
                    q.push(x);
                    visited.insert(x);
                }
            }
        }
        step++;
    }
}

// 输入一棵二叉树的根节点，遍历这棵二叉树所有节点
void levelTraverse(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> q;
    q.push(root);

    // 遍历二叉树的每一个节点
    while (!q.empty()) {
        TreeNode* cur = q.front();
        printf("我不知道节点 %s 在第几层", cur);

        // 将子节点放入队列
        if (cur->left != nullptr) {
            q.push(cur->left);
        }
        if (cur->right != nullptr) {
            q.push(cur->right);
        }
        q.pop();
    }
}

struct State {
    // 记录 node 节点的深度
    int depth;
    TreeNode* node;

    State(TreeNode* node, int depth) {
        this -> depth = depth;
        this -> node = node;
    }
};

// 输入一棵二叉树的根节点，遍历这棵二叉树所有节点
void levelTraverse(TreeNode* root) {
    if (root == nullptr) return;
    queue<State> q;
    q.push(State(root, 1));

    // 遍历二叉树的每一个节点
    while (!q.empty()) {
        State cur = q.front();
        q.pop();
        TreeNode* cur_node = cur.node;
        int cur_depth = cur.depth;
        printf("节点 %s 在第 %s 层", cur_node, cur_depth);

        // 将子节点放入队列
        if (cur_node -> left != nullptr) {
            q.push(State(cur_node -> left, cur_depth + 1));
        }
        if (cur_node -> right != nullptr) {
            q.push(State(cur_node -> right, cur_depth + 1));
        }
    }
}