美文网首页19-23年 学习笔记
【 数据结构 & 算法 】—— 二叉树、图

【 数据结构 & 算法 】—— 二叉树、图

作者: Du1in9 | 来源:发表于2020-11-15 21:18 被阅读0次

    思维导图

    预备知识：二叉树定义（★）

    • 预备知识_二叉树定义.cpp
    #include <stdio.h>

struct TreeNode { // 二叉树数据结构 
    int val; // 数据域 
    TreeNode *left; // 左子树指针 
    TreeNode *right; // 右子树指针 
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
                // 当前遍历的节点，当前节点的层数 
void preorder_print(TreeNode *node, int layer){
    if (!node){ // 若空，返回 
        return;
    }
    for (int i = 0; i < layer; i++){ // 根据层数，打印相应数量的 '-' 
        printf("-----");
    }
    printf("[%d]\n", node->val);  
    preorder_print(node->left, layer + 1); // 遍历左子树，层数 + 1 
    preorder_print(node->right, layer + 1); // 遍历右子树，层数 + 1 
}

int main(){
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(5);
    TreeNode d(3);
    TreeNode e(4);
    TreeNode f(6);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    preorder_print(&a, 0);
    return 0;
}

    预备知识：二叉树的深度遍历（★）

    • 预备知识_二叉树深度遍历.cpp
    #include <stdio.h>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void traversal_print3(TreeNode *node,int layer){
    if (!node){
        return;
    }
    // 前序遍历 
    for (int i = 0; i < layer; i++){
        printf("-----");
    }
    printf("[%d]\n", node->val);
    traversal_print3(node->left, layer + 1);
    traversal_print3(node->right, layer + 1);
}

void traversal_print1(TreeNode *node,int layer){
    if (!node){
        return;
    }
    // 中序遍历 
    traversal_print1(node->left, layer + 1);
    for (int i = 0; i < layer; i++){
        printf("-----");
    }
    printf("[%d]\n", node->val);
    traversal_print1(node->right, layer + 1);
}

void traversal_print2(TreeNode *node,int layer){
    if (!node){
        return;
    } 
    // 后序遍历 
    traversal_print2(node->left, layer + 1);
    traversal_print2(node->right, layer + 1);
    for (int i = 0; i < layer; i++){
        printf("-----");
    }
    printf("[%d]\n", node->val);
}

int main(){
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(5);
    TreeNode d(3);
    TreeNode e(4);
    TreeNode f(6);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    traversal_print1(&a, 0);
    printf("\n");
    traversal_print2(&a, 0);
    printf("\n");
    traversal_print3(&a, 0);
    printf("\n");
    return 0;
}

    例1：路径之和（二叉树深搜）（★★）

    • LeetCode 113.Path Sum .cpp
    #include <stdio.h>
#include <vector>

struct TreeNode { // 二叉树数据结构 
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:                                    // 根，路径和 
    std::vector<std::vector<int> > pathSum(TreeNode* root, int sum) {
        std::vector<std::vector<int> > result; // 存储满足条件路径的数组 
        std::vector<int> path; // 路径栈 
        int path_value = 0; // 路径值 
        preorder(root, path_value, sum, path, result);
        return result;
    }
private:
    void preorder(TreeNode *node, int &path_value, int sum,
                std::vector<int> &path, 
                std::vector<std::vector<int> > &result){
        if (!node){ // 若树空，跳出函数 
            return;
        }
        path_value += node->val; // 更新路径值 
        path.push_back(node->val); // 更新路径栈 
        if (!node->left && !node->right && path_value == sum){ // 到达叶节点，且路径和等于sum 
            result.push_back(path); // 更新路径数组 
        }
        //（前序遍历） 
        preorder(node->left, path_value, sum, path, result);
        preorder(node->right, path_value, sum, path, result);
        path_value -= node->val; // 遍历完后，减去节点值 
        path.pop_back(); // 遍历完后，弹出节点值 
    }
};

int main(){
    TreeNode a(5);
    TreeNode b(4);
    TreeNode c(8);
    TreeNode d(11);
    TreeNode e(13);
    TreeNode f(4);
    TreeNode g(7);
    TreeNode h(2);
    TreeNode x(5);
    TreeNode y(1);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    c.left = &e;
    c.right = &f;
    d.left = &g;
    d.right = &h;
    f.left = &x;
    f.right = &y;
    Solution solve;
    // 返回满足条件路径的数组
    std::vector<std::vector<int> > result = solve.pathSum(&a, 22);
    for (int i = 0; i < result.size(); i++){
        for (int j = 0; j < result[i].size(); j++){
            printf("[%d] ", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}

    例2：最近的公共祖先（二叉树性质）（★★）

    • LeetCode 236.Lowest Common Ancestor of a Binary Tree.cpp
    #include <stdio.h>
#include <vector>
#include <set>

struct TreeNode { // 二叉树数据结构 
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void preorder(TreeNode* node, // 当前遍历节点 
              TreeNode *search, // 搜索的节点 
              std::vector<TreeNode*> &path, // 节点路径栈 
              std::vector<TreeNode*> &result, // 最终路径结果 
              int &finish){ // 记录是否搜索到节点 
    if (!node || finish){
        return;
    }
    path.push_back(node); // 先序遍历，push入路径栈 
    if (node == search){ // 若搜索到节点，则更新 finish 
        finish = 1;
        result = path;
    }
    preorder(node->left, search, path, result, finish); // 深度遍历 node左后代 
    preorder(node->right, search, path, result, finish); // 深度遍历 node右后代 
    path.pop_back(); // 结束遍历时，将 node节点弹出栈 
}

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        std::vector<TreeNode*> path; // 遍历的临时栈 
        std::vector<TreeNode*> node_p_path; // p的路径栈 
        std::vector<TreeNode*> node_q_path; // q的路径栈 
        int finish = 0; // 记录是否搜索到节点
        preorder(root, p, path, node_p_path, finish); // 获取 p的路径栈
        path.clear();
        finish = 0;
        preorder(root, q, path, node_q_path, finish); // 获取 q的路径栈     
        TreeNode *result = 0;
        for (int i = 0; i < node_p_path.size(); i++){ // 遍历完得到最近公共祖先节点 
            if (node_p_path[i] == node_q_path[i]){   
                result = node_p_path[i];
            }
        }
        return result;
    }
};

int main(){
    TreeNode a(3);
    TreeNode b(5);
    TreeNode c(1);
    TreeNode d(6);
    TreeNode e(2);
    TreeNode f(0);
    TreeNode x(8);
    TreeNode y(7);
    TreeNode z(4);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = &f;
    c.right = &x;
    e.left = &y;
    e.right = &z;
    
    Solution solve;
    TreeNode *result = solve.lowestCommonAncestor(&a, &b, &f);
    printf("root=3, p=5, q=0, 最近公共祖先：%d\n", result->val);
    result = solve.lowestCommonAncestor(&a, &d, &z);
    printf("root=3, p=6, q=4, 最近公共祖先：%d\n", result->val);
    result = solve.lowestCommonAncestor(&a, &b, &y);
    printf("root=3, p=5, q=7, 最近公共祖先：%d\n", result->val);   
    return 0;
}

    例3：二叉树转链表（二叉树与链表）（★★）

    • LeetCode 114.Flatten Binary Tree to Linked List (solve1).cpp
    #include <stdio.h>
#include <vector>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    void preorder(TreeNode *node, std::vector<TreeNode *> &node_vec){
        if (!node){
            return;
        }
        node_vec.push_back(node); // 前序遍历转换成链表
        preorder(node->left, node_vec);
        preorder(node->right, node_vec);
    }
public:
    void flatten(TreeNode *root) {
        std::vector<TreeNode *> node_vec;
        preorder(root, node_vec); // 链表 
        for (int i = 1; i < node_vec.size(); i++){ // 没有左枝的树 
            node_vec[i-1]->left = NULL;
            node_vec[i-1]->right = node_vec[i];
        }
    }
};

int main(){
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(5);
    TreeNode d(3);
    TreeNode e(4);
    TreeNode f(6);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    Solution solve;
    solve.flatten(&a); // 生成树 
    TreeNode *head = &a; 
    while(head){ // 遍历树 
        printf("[%d]", head->val);
        head = head->right;
    }
    printf("\n");
    return 0;
}
    • LeetCode 114.Flatten Binary Tree to Linked List (solve2).cpp
    #include <stdio.h>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
                   // 当前的节点，子树最后的节点 
    void preorder(TreeNode *node, TreeNode *&last){
        if (!node){ // 遍历完节点返回 
            return;
        }
        if (!node->left && !node->right){ // 找到子树最后的节点 
            last = node;
            return;
        } 
        TreeNode *left = node->left; // 左指针 left
        TreeNode *right = node->right; // 右指针 right  
        TreeNode *left_last = NULL; // 左子树最后的节点 left_last
        TreeNode *right_last = NULL; // 右子树最后的节点 left_last
        if (left){ // 若有左子树，递归将左子树转换为单链表 
            preorder(left, left_last);
            node->left = NULL;
            node->right = left; // 连接 node 和 left 
            last = left_last;
        }
        // 若有右子树，递归将右子树转换为单链表
        if (right){
            preorder(right, right_last);
            if(left_last){
                left_last->right = right; // 连接 left 和 right 
            }
            last = right_last;
        }
    }
public:
    void flatten(TreeNode *root) {
        TreeNode *last = NULL;
        preorder(root, last);
    }
};

int main(){
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(5);
    TreeNode d(3);
    TreeNode e(4);
    TreeNode f(6);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    Solution solve;
    solve.flatten(&a);
    TreeNode *head = &a;
    while(head){
        if (head->left){
            printf("ERROR\n");
        }
        printf("[%d]", head->val);
        head = head->right;
    }
    printf("\n");
    return 0;
}

    预备知识：二叉树层次遍历（★）

    • 预备知识_二叉树层次遍历.cpp
    #include <stdio.h>
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 二叉树层次遍历 
void BFS_print(TreeNode* root){
    std::queue<TreeNode *> Q;
    Q.push(root); // push 根 
    while(!Q.empty()){
        TreeNode *node = Q.front();
        Q.pop();
        printf("[%d]\n", node->val);
        if (node->left){ // push 左孩子 
            Q.push(node->left);
        }
        if (node->right){ // push 右孩子
            Q.push(node->right);
        }
    }
}

int main(){
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(5);
    TreeNode d(3);
    TreeNode e(4);
    TreeNode f(6);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    BFS_print(&a);
    return 0;
}

    例4：侧面观察二叉树（二叉树宽搜）（★★）

    • LeetCode 199.Binary Tree Right Side View.cpp
    #include <stdio.h>
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    std::vector<int> rightSideView(TreeNode* root) {
        std::vector<int> view; // 按层遍历的最后一个节点 
        std::queue<std::pair<TreeNode *, int> > Q;
        if (root){ // 若根非空，push <root, 0> 
            Q.push(std::make_pair(root, 0));
        }
        while(!Q.empty()){   
            TreeNode *node = Q.front().first; // 第一个参数是节点 
            int depth = Q.front().second; // 第二个参数是层数 
            Q.pop(); // 弹出此层上一节点 
            if (view.size() == depth){
                view.push_back(node->val);
            }
            else{ // 更新此层 view 
                view[depth] = node->val;
            }
            if (node->left){ // 更新层数 depth  
                Q.push(std::make_pair(node->left, depth + 1));
            }
            if (node->right){ // 更新层数 depth 
                Q.push(std::make_pair(node->right, depth + 1));
            }
        }
        return view; // 返回每层的最后一个节点 
    }
};

int main(){
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(5);
    TreeNode d(3);
    TreeNode e(4);
    TreeNode f(6);
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.right = &f;
    Solution solve;
    std::vector<int> result = solve.rightSideView(&a);
    for (int i = 0; i < result.size(); i++){
        printf("【%d】\n", result[i]);    
    }
    return 0;
}

    预备知识

    • 预备知识 _ 图的表示 (临接矩阵).cpp
    #include <stdio.h>

int main(){
    const int MAX_N = 5; // 顶点个数 
    int Graph[MAX_N][MAX_N] = {0}; // 初始化矩阵 
    // 将图连通，且不带权 
    Graph[0][2] = 1;
    Graph[0][4] = 1;
    Graph[1][0] = 1;
    Graph[1][2] = 1;
    Graph[2][3] = 1;
    Graph[3][4] = 1;
    Graph[4][3] = 1;
    printf("Graph:\n"); 
    // 打印输出图 
    for (int i = 0; i < MAX_N; i++){
        for (int j = 0; j < MAX_N; j++){
            printf("%d ", Graph[i][j]);
        }
        printf("\n");
    }
    return 0;
}
    • 预备知识 _ 图的表示 (临接表).cpp
    #include <stdio.h>
#include <vector>

struct GraphNode{ 
    int label; // 图的顶点 
    std::vector<GraphNode *> neighbors; // 相邻节点的指针数组 
    GraphNode(int x) : label(x) {};
};

int main(){ 
    const int MAX_N = 5;
    GraphNode *Graph[MAX_N]; 
    // 新建内存 
    for (int i = 0; i < MAX_N; i++){  
        Graph[i] = new GraphNode(i);
    }
    // 将图连通 
    Graph[0]->neighbors.push_back(Graph[2]);
    Graph[0]->neighbors.push_back(Graph[4]);
    Graph[1]->neighbors.push_back(Graph[0]);
    Graph[1]->neighbors.push_back(Graph[2]);
    Graph[2]->neighbors.push_back(Graph[3]);
    Graph[3]->neighbors.push_back(Graph[4]);
    Graph[4]->neighbors.push_back(Graph[3]);
    // 打印输出 
    printf("Graph:\n");
    for (int i = 0; i < MAX_N; i++){
        printf("Label(%d) : ", i);
        for (int j = 0; j < Graph[i]->neighbors.size(); j++){
            printf("%d ", Graph[i]->neighbors[j]->label);
        }
        printf("\n");
    }
    // 释放内存 
    for (int i = 0; i < MAX_N; i++){
        delete Graph[i];
    }
    
    return 0;
}
    • 预备知识_图的深度优先遍历.cpp
    #include <stdio.h>
#include <vector>

struct GraphNode{ // 图的邻接表数据结构 
    int label;
    std::vector<GraphNode *> neighbors;
    GraphNode(int x) : label(x) {};
};

void DFS_graph(GraphNode *node, int visit[]){
    visit[node->label] = 1; // 标记已访问的顶点 
    printf("%d ", node->label);
    for (int i = 0; i < node->neighbors.size(); i++){ // 访问相邻的且没有被访问的顶点 
        if (visit[node->neighbors[i]->label] == 0){
            DFS_graph(node->neighbors[i], visit); 
        }
    }
} 

int main(){
    const int MAX_N = 5;
    GraphNode *Graph[MAX_N];    
    for (int i = 0; i < MAX_N; i++){ // 创建图的顶点 
        Graph[i] = new GraphNode(i); 
    }
    // 添加图的边 
    Graph[0]->neighbors.push_back(Graph[4]);
    Graph[0]->neighbors.push_back(Graph[2]);    
    Graph[1]->neighbors.push_back(Graph[0]);
    Graph[1]->neighbors.push_back(Graph[2]);
    Graph[2]->neighbors.push_back(Graph[3]);
    Graph[3]->neighbors.push_back(Graph[4]);
    Graph[4]->neighbors.push_back(Graph[3]);
    int visit[MAX_N] = {0}; 
    // 用来标记访问过的点 
    for (int i = 0; i < MAX_N; i++){
        if (visit[i] == 0){ // 若该顶点未被访问 
            printf("From label(%d) : ", Graph[i]->label);
            DFS_graph(Graph[i], visit);  
            printf("\n");
        }
    }
    for (int i = 0; i < MAX_N; i++){ // 释放内存 
        delete Graph[i];
    }
    return 0;
}
    • 预备知识_图的宽度优先遍历.cpp
    #include <stdio.h>
#include <vector>
#include <queue>

struct GraphNode{
    int label;
    std::vector<GraphNode *> neighbors;
    GraphNode(int x) : label(x) {};
};

void BFS_graph(GraphNode *node, int visit[]){
    std::queue<GraphNode *> Q; // 宽度优先遍历使用队列 
    Q.push(node);
    visit[node->label] = 1; // 标记已访问的顶点 
    while(!Q.empty()){ // 遍历队列 
        GraphNode *node = Q.front();
        Q.pop();
        printf("%d ", node->label);
        for (int i = 0; i < node->neighbors.size(); i++){
            if (visit[node->neighbors[i]->label] == 0){ // 访问相邻的且没有被访问的顶点 
                Q.push(node->neighbors[i]);
                visit[node->neighbors[i]->label] = 1;
            }
        }
    }
}

int main(){
    const int MAX_N = 5;
    GraphNode *Graph[MAX_N];
    for (int i = 0; i < MAX_N; i++){ // 创建图的顶点 
        Graph[i] = new GraphNode(i);
    }
    // 添加图的边    
    Graph[0]->neighbors.push_back(Graph[4]);
    Graph[0]->neighbors.push_back(Graph[2]);
    Graph[1]->neighbors.push_back(Graph[0]);
    Graph[1]->neighbors.push_back(Graph[2]);
    Graph[2]->neighbors.push_back(Graph[3]);
    Graph[3]->neighbors.push_back(Graph[4]);
    Graph[4]->neighbors.push_back(Graph[3]);
    int visit[MAX_N] = {0};
    for (int i = 0; i < MAX_N; i++){
        if (visit[i] == 0){
            printf("From label(%d) : ", Graph[i]->label);
            BFS_graph(Graph[i], visit);
            printf("\n");
        }
    }
    for (int i = 0; i < MAX_N; i++){ // 释放内存 
        delete Graph[i];
    }
    return 0;
}

    例5：课程安排（有向图安排环）（★★）

    • LeetCode 207.Course Schedule(solve1).cpp
    #include <stdio.h>

#include <vector>
struct GraphNode{
    int label; // 当前节点 
    std::vector<GraphNode *> neighbors; // 相邻节点 
    GraphNode(int x) : label(x) {};
};
bool DFS_graph(GraphNode *node, std::vector<int> &visit){
    visit[node->label] = 0; // 该节点正在访问 
    for (int i = 0; i < node->neighbors.size(); i++){ // 遍历该节点的相邻节点 
        if (visit[node->neighbors[i]->label] == -1){ // 若该相邻节点未被访问 
            if (DFS_graph(node->neighbors[i], visit) == 0){ // 带入进行 DFS 
                return false;
            }
        }
        else if (visit[node->neighbors[i]->label] == 0){ // 若该相邻节点正在访问 
            return false;
        }
    }
    visit[node->label] = 1;
    return true;
}

class Solution {
public:
                                  // pair<课程1课程2> 课程1依赖课程2
    bool canFinish(int numCourses, std::vector<std::pair<int, int> >& prerequisites) {
        std::vector<GraphNode*> graph; // 邻接表
        std::vector<int> visit; // 节点访问状态, -1没有访问过, 0正在访问, 1已完成访问
        for (int i = 0; i < numCourses; i++){ // 创建图的节点,并赋访问状态为空
            graph.push_back(new GraphNode(i));
            visit.push_back(-1);
        }
        for (int i = 0; i < prerequisites.size(); i++){ // 创建图, 连接图的顶点
            GraphNode *begin = graph[prerequisites[i].second];
            GraphNode *end = graph[prerequisites[i].first];
            begin->neighbors.push_back(end); // 课程2指向课程1
        }
        for (int i = 0; i < graph.size(); i++){ 
            // 如果节点没访问过, 进行DFS, 如果DFS遇到环, 返回无法完成
            if (visit[i] == -1 && !DFS_graph(graph[i], visit)){ 
                return false; 
            }
        }
        for (int i = 0; i < numCourses; i++){ // 释放内存 
            delete graph[i];
        }
        return true;
    }
};

int main(){ 
    std::vector<std::pair<int, int> > prerequisites;
    prerequisites.push_back(std::make_pair(1, 0));
    prerequisites.push_back(std::make_pair(2, 0));
    prerequisites.push_back(std::make_pair(3, 1));
    prerequisites.push_back(std::make_pair(3, 2));
    Solution solve;
    printf("0->1->3, 0->2->3\n");
    printf("是否可以将四个课程全部完成：%d\n", solve.canFinish(4, prerequisites));
    prerequisites.push_back(std::make_pair(1, 0));
    prerequisites.push_back(std::make_pair(2, 1));
    prerequisites.push_back(std::make_pair(3, 2));
    prerequisites.push_back(std::make_pair(0, 3));
    Solution solve2;
    printf("0->1->2->3->0\n");
    printf("是否可以将四个课程全部完成：%d\n", solve2.canFinish(4, prerequisites));
    return 0;
}
    • LeetCode 207.Course Schedule(solve2).cpp
    #include <stdio.h>
#include <vector>
#include <queue>

struct GraphNode{
    int label;
    std::vector<GraphNode *> neighbors;
    GraphNode(int x) : label(x) {};
};

class Solution {
public:
                                   // pair<课程1课程2> 课程 1依赖课程 2
    bool canFinish(int numCourses, std::vector<std::pair<int, int> >& prerequisites) {
        std::vector<GraphNode*> graph;
        std::vector<int> degree; // 入度数组 
        for (int i = 0; i < numCourses; i++){ // 初始化入度，创建节点 
            degree.push_back(0);
            graph.push_back(new GraphNode(i));
        }
        for (int i = 0; i < prerequisites.size(); i++){
            GraphNode *begin = graph[prerequisites[i].second];
            GraphNode *end = graph[prerequisites[i].first];
            begin->neighbors.push_back(end); // 课程 2指向课程 1 
            degree[prerequisites[i].first]++; // 课程 1入度 ++ 
        }       
        std::queue<GraphNode *> Q;
        for (int i = 0; i < numCourses; i++){
            if (degree[i] == 0){ // 初始时入度为 0的节点存入 Q 
                Q.push(graph[i]);
            }
        }
        while(!Q.empty()){
            GraphNode *node = Q.front();
            Q.pop();
            for (int i = 0; i<node->neighbors.size(); i++){ // 遍历节点 
                degree[node->neighbors[i]->label]--; // 该节点的相邻节点入度 -- 
                if (degree[node->neighbors[i]->label] == 0){ // 遍历后入度为 0的节点存入 Q 
                    Q.push(node->neighbors[i]);
                }
            }
        }       
        for (int i = 0; i < graph.size(); i++){ // 释放内存 
            delete graph[i];
        }       
        for (int i = 0; i < degree.size(); i++){ // 若存在节点入度不为 0 
            if (degree[i]){
                return false;  
            }
        }
        return true;
    }
};

int main(){ 
    std::vector<std::pair<int, int> > prerequisites;
    prerequisites.push_back(std::make_pair(1, 0));
    prerequisites.push_back(std::make_pair(2, 0));
    prerequisites.push_back(std::make_pair(3, 1));
    prerequisites.push_back(std::make_pair(3, 2));
    Solution solve;
    printf("0->1->3, 0->2->3\n");
    printf("是否可以将四个课程全部完成：%d\n", solve.canFinish(4, prerequisites));
    prerequisites.push_back(std::make_pair(1, 0));
    prerequisites.push_back(std::make_pair(2, 1));
    prerequisites.push_back(std::make_pair(3, 2));
    prerequisites.push_back(std::make_pair(0, 3));
    Solution solve2;
    printf("0->1->2->3->0\n");
    printf("是否可以将四个课程全部完成：%d\n", solve2.canFinish(4, prerequisites));
    return 0;
}

    相关文章

      网友评论

        本文标题：【 数据结构 & 算法 】—— 二叉树、图

        本文链接：https://www.haomeiwen.com/subject/nohobktx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        19-23年 学习笔记

        关于我们|服务条款|联系我们|【 数据结构 & 算法 】—— 二叉树、图|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！