热门标签 | 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;

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


推荐阅读
  • 我的读书清单(持续更新)201705311.《一千零一夜》2006(四五年级)2.《中华上下五千年》2008(初一)3.《鲁滨孙漂流记》2008(初二)4.《钢铁是怎样炼成的》20 ... [详细]
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • 本文探讨了使用普通生成函数和指数生成函数解决组合与排列问题的方法,特别是在处理特定路径计数问题时的应用。文章通过详细分析和代码实现,展示了如何高效地计算在给定条件下不相邻相同元素的排列数量。 ... [详细]
  • 探索Java 11中的ZGC垃圾收集器
    Java 11引入了一种新的垃圾收集器——ZGC,由Oracle公司研发,旨在支持TB级别的内存容量,并保证极低的暂停时间。本文将探讨ZGC的开发背景、技术特点及其潜在的应用前景。 ... [详细]
  • 利用无代码平台实现高效业务应用开发
    随着市场环境的变化加速,全球企业都在探索更为敏捷的应用开发模式,以便快速响应新兴的商业机遇。然而,传统的软件开发方式不仅成本高昂,而且耗时较长,这往往导致IT与业务部门之间的合作障碍,进而影响项目的成功。本文将探讨如何通过无代码开发平台解决这些问题。 ... [详细]
  • 为何Compose与Swarm之后仍有Kubernetes的诞生?
    探讨在已有Compose和Swarm的情况下,Kubernetes是如何以其独特的设计理念和技术优势脱颖而出,成为容器编排领域的领航者。 ... [详细]
  • 本文探讨了程序员这一职业的本质,认为他们是专注于问题解决的专业人士。文章深入分析了他们的日常工作状态、个人品质以及面对挑战时的态度,强调了编程不仅是一项技术活动,更是个人成长和精神修炼的过程。 ... [详细]
  • 在日常生活中,支付宝已成为不可或缺的支付工具之一。本文将详细介绍如何通过支付宝实现免费提现,帮助用户更好地管理个人财务,避免不必要的手续费支出。 ... [详细]
  • 本文介绍了如何通过C#语言调用动态链接库(DLL)中的函数来实现IC卡的基本操作,包括初始化设备、设置密码模式、获取设备状态等,并详细展示了将TextBox中的数据写入IC卡的具体实现方法。 ... [详细]
  • 深入解析Unity3D游戏开发中的音频播放技术
    在游戏开发中,音频播放是提升玩家沉浸感的关键因素之一。本文将探讨如何在Unity3D中高效地管理和播放不同类型的游戏音频,包括背景音乐和效果音效,并介绍实现这些功能的具体步骤。 ... [详细]
  • 本文探讨了一种常见的C++面试题目——实现自己的String类。通过此过程,不仅能够检验开发者对C++基础知识的掌握程度,还能加深对其高级特性的理解。文章详细介绍了如何实现基本的功能,如构造函数、析构函数、拷贝构造函数及赋值运算符重载等。 ... [详细]
  • 随着Linux操作系统的广泛使用,确保用户账户及系统安全变得尤为重要。用户密码的复杂性直接关系到系统的整体安全性。本文将详细介绍如何在CentOS服务器上自定义密码规则,以增强系统的安全性。 ... [详细]
  • 3DSMAX制作超现实的体育馆模型
    这篇教程是向脚本之家的朋友介绍3DSMAX制作超现实的体育馆模型方法,教程制作出来的体育馆模型非常地不错,不过教程有点难度,需要有一定基础的朋友学习,推荐到脚本之家,喜欢的朋友可 ... [详细]
  • 本文介绍了如何在AngularJS应用中使用ng-repeat指令创建可单独点击选中的列表项,并详细描述了实现这一功能的具体步骤和代码示例。 ... [详细]
  • 本文详细介绍了C++中的构造函数,包括其定义、特点以及如何通过构造函数进行对象的初始化。此外,还探讨了转换构造函数的概念及其在不同情境下的应用,以及如何避免不必要的隐式类型转换。 ... [详细]
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社区 版权所有