热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

图的存储和遍历方法——链式前向星法

本文介绍了一种图的存储和遍历方法——链式前向星法,该方法在存储带边权的图时时间效率比vector略高且节省空间。然而,链式前向星法存图的最大问题是对一个点的出边进行排序去重不容易,但在平行边无所谓的情况下选择这个方法是非常明智的。文章还提及了图中搜索树的父子关系一般不是很重要,同时给出了相应的代码示例。

链式前向星法存的带边权的图,(尤其在多组数据时)时间效率比vector略高且节省空间,缺点是不容易对一个点的出边进行排序去重,当平行边无所谓时选择这个方法是非常明智的。链式前向星法存图的最大的问题是要记得给反向边预留空间。

图的存储和遍历,在图中搜索树的父子关系其实一般不是很重要。注意下面的代码是没有对vis进行清空的,因为其实并不是每次搜索前都会需要清空,有时候有一些其他的操作(特别是有向图)。需要管边权的去找dijkstra算法就好了。

struct Graph {
    static const int MAXN = 200000;
    static const int MAXM = 400000;

    int n;
    int head[MAXN + 5], top;

    struct Edge {
        int v, w, next;
    } edge[MAXM + 5];

    void Init(int _n) {
        n = _n;
        top = 0;
        memset(head, 0, sizeof(head[0]) * (n + 1));
    }

    void AddEdge(int u, int v, int w) {
        edge[++top].next = head[u];
        edge[top].v = v;
        edge[top].w = w;
        head[u] = top;
    }

    bool vis[MAXN + 5];
    void dfs(int u, int w) {
        vis[u] = 1;
        for(int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if(vis[v])
                continue;
            dfs(v, edge[i].w);
        }
    }

    int que[MAXN + 5], front, back;
    void bfs(int s) {
        frOnt= 1, back = 0;
        vis[s] = 1;
        que[++back] = s;
        while(front <= back) {
            int u = que[front++];
            for(int i = head[u]; i; i = edge[i].next) {
                int v = edge[i].v;
                if(vis[v])
                    continue;
                vis[v] = 1;
                que[++back] = v;
            }
        }
    }
} G;

树的存储和遍历,dfs中带有父节点p的编号,树一般就不需要什么bfs了,距离都是唯一的。

struct Graph {
    static const int MAXN = 200000;
    static const int MAXM = 400000;

    int n;
    int head[MAXN + 5], top;

    struct Edge {
        int v, w, next;
    } edge[MAXM + 5];

    void Init(int _n) {
        n = _n;
        top = 0;
        memset(head, 0, sizeof(head[0]) * (n + 1));
    }

    void AddEdge(int u, int v, int w) {
        edge[++top].next = head[u];
        edge[top].v = v;
        edge[top].w = w;
        head[u] = top;
    }

    void dfs(int u, int p, int w) {
        for(int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if(v == p)
                continue;
            dfs(v, u, edge[i].w);
        }
    }
} G;

模板 - 图论 - 图的存储和遍历


推荐阅读
  • C++入门必备:首个博客知识点汇总
    本文总结了C++初学者需要掌握的关键知识点,特别强调了成员类型的区分。其中,protected成员与private成员在本类中的作用相同,但protected成员允许派生类的成员函数访问,而private成员则不允许。此外,文章还介绍了其他重要的C++基础概念,如类的构造函数、析构函数以及继承机制,为初学者提供了一个全面的学习指南。 ... [详细]
  • 捕获并处理用户输入数字时的异常,提供详细的错误提示与指导
    在用户输入数字时,程序能够有效捕获并处理各种异常情况,如非法字符或格式错误,并提供详尽的错误提示和操作指导,确保用户能够准确输入有效的数字数据。通过这种方式,不仅提高了程序的健壮性和用户体验,还减少了因输入错误导致的系统故障。具体实现中,使用了Java的异常处理机制,结合Scanner类进行输入读取和验证,确保了输入的合法性和准确性。 ... [详细]
  • 二叉树的直径是指树中任意两个叶节点之间最长路径上的节点数量。本文深入解析了计算二叉树直径的算法,并提出了一种优化方法,以提高计算效率和准确性。通过详细的案例分析和性能对比,展示了该优化算法在实际应用中的优势。 ... [详细]
  • 在处理遗留数据库的映射时,反向工程是一个重要的初始步骤。由于实体模式已经在数据库系统中存在,Hibernate 提供了自动化工具来简化这一过程,帮助开发人员快速生成持久化类和映射文件。通过反向工程,可以显著提高开发效率并减少手动配置的错误。此外,该工具还支持对现有数据库结构进行分析,自动生成符合 Hibernate 规范的配置文件,从而加速项目的启动和开发周期。 ... [详细]
  • 理解和应用HTTP请求中的转发与重定向机制
    在HTTP请求处理过程中,客户端发送请求(通常简称为req),服务器进行相应处理后返回响应(通常简称为res)。理解和应用客户端的转发与重定向机制是前端开发的重要内容。这两种机制在Web开发中具有关键作用,能够有效管理和优化用户请求的处理流程。转发机制允许服务器内部将请求传递给另一个资源,而重定向则指示客户端向新的URL发起新的请求,从而实现页面跳转或资源更新。掌握这些技术有助于提升应用的性能和用户体验。 ... [详细]
  • VC维在机器学习中的应用与解析
    VC维在机器学习中的应用与解析VC维是指在机器学习中,一个假设空间能够正确分类的最大样本数量。具体而言,如果一个假设空间能够将N个样本以所有可能的 \(2^N\) 种方式完全分开,则称该假设空间具有N的VC维。VC维是衡量模型复杂度的重要指标,对于理解模型的泛化能力和过拟合风险具有重要意义。本文详细探讨了VC维的定义、计算方法及其在机器学习中的应用,并通过实例分析展示了其在模型选择和评估中的关键作用。 ... [详细]
  • 在使用Block时,正确的声明方法和确保线程安全是至关重要的。为了保证Block在堆中分配,应使用`copy`修饰符进行声明,因为栈中的Block与栈的生命周期绑定,容易导致内存问题。此外,还需注意Block捕获外部变量的行为,以避免潜在的循环引用和数据不一致问题。建议深入研究相关文档,以掌握更多高级技巧和最佳实践。 ... [详细]
  • 利用树莓派畅享落网电台音乐体验
    最近重新拾起了闲置已久的树莓派,这台小巧的开发板已经沉寂了半年多。上个月闲暇时间较多,我决定将其重新启用。恰逢落网电台进行了改版,回忆起之前在树莓派论坛上看到有人用它来播放豆瓣音乐,便萌生了同样的想法。通过一番调试,终于实现了在树莓派上流畅播放落网电台音乐的功能,带来了全新的音乐享受体验。 ... [详细]
  • 本文全面解析了 gRPC 的基础知识与高级应用,从 helloworld.proto 文件入手,详细阐述了如何定义服务接口。例如,`Greeter` 服务中的 `SayHello` 方法,该方法在客户端和服务器端的消息交互中起到了关键作用。通过实例代码,读者可以深入了解 gRPC 的工作原理及其在实际项目中的应用。 ... [详细]
  • MongoVUE基础操作指南:轻松上手数据库管理
    本文介绍了MongoVUE的基础操作,旨在帮助用户轻松掌握数据库管理技巧。MongoVUE是一款功能强大的MongoDB客户端工具,虽然需要注册,但其用户友好的界面和丰富的功能使其成为许多开发者的首选。文中详细解释了安装步骤、基本配置以及常见操作方法,并对一些常见的问题进行了修正和补充,确保用户能够快速上手并高效使用MongoVUE进行数据库管理。 ... [详细]
  • 在Python网络编程中,多线程技术的应用与优化是提升系统性能的关键。线程作为操作系统调度的基本单位,其主要功能是在进程内共享内存空间和资源,实现并行处理任务。当一个进程启动时,操作系统会为其分配内存空间,加载必要的资源和数据,并调度CPU进行执行。每个进程都拥有独立的地址空间,而线程则在此基础上进一步细化了任务的并行处理能力。通过合理设计和优化多线程程序,可以显著提高网络应用的响应速度和处理效率。 ... [详细]
  • HDU1176:免费馅饼问题的动态规划解法分析
    题目“免费馅饼”通过动态规划方法进行了解析。该问题的时间限制为 Java 2000ms 和其他语言 1000ms,内存限制为 Java 65536K 和其他语言 32768K。本文详细探讨了如何利用动态规划算法高效求解此问题,并对算法的时间复杂度和空间复杂度进行了深入分析。此外,还提供了具体的实现步骤和代码示例,帮助读者更好地理解和应用这一方法。 ... [详细]
  • 如何在Mac上构建高效的本地服务器环境
    在Mac上构建高效的本地服务器环境,首先需要了解基本步骤:1. 配置目录基础;2. 启动Apache服务;3. 添加自定义文档至本地服务器;4. 查看自定义效果。此外,还可以通过手机或其他电脑访问本机服务器,以确保跨设备的兼容性和调试效果。Mac系统自带的Apache服务为本地开发提供了便捷的工具,本文将详细介绍每个步骤的具体操作方法。 ... [详细]
  • 通过 NuGet 获取最新版本的 Rafy 框架及其详细文档
    为了帮助开发者更便捷地使用Rafy领域实体框架,我们已将最新版的Rafy框架程序集上传至nuget.org,并同步发布了最新版本的Rafy SDK至Visual Studio。此外,我们还提供了详尽的文档和示例,以确保开发者能够快速上手并充分利用该框架的强大功能。 ... [详细]
  • TypeScript 实战分享:Google 工程师深度解析 TypeScript 开发经验与心得
    TypeScript 实战分享:Google 工程师深度解析 TypeScript 开发经验与心得 ... [详细]
author-avatar
白云飞羽_389
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有