尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
图的存储(邻接表法)
文章目录邻接表法顺序链式存储度的求法对比邻接矩阵 VS 邻接表数组实现的顺序存储邻接矩阵法空间复杂度高O(n2),不适合存储稀疏图适合存储稠密图。邻接表法顺序链式存储邻接表是一种“顺序存储 链式存储” 的混合体顶点表顺序/数组用一个一维数组存储所有顶点每个顶点带一个 “指向第一条边的指针”。边弧表链式/链表每个顶点后面挂一个单链表链表中每个结点存储邻接点的下标或指针和 指向下一条边的指针。#defineMaxVertexNum100// 最大顶点数// 1. 边(弧)表结点链表中存的是什么存的是【邻接点的位置】typedefstructArcNode{intadjvex;// 该弧所指向的顶点的位置数组下标structArcNode*next;// 指向下一条弧的指针// 若带权图这里加一个 int weight;}ArcNode;// 2. 顶点表结点数组中的元素是什么typedefstructVNode{VertexType data;// 顶点信息如 A, BArcNode*first;// 指向第一条依附于该顶点的弧的指针}VNode,AdjList[MaxVertexNum];// AdjList 是顶点数组类型// 3. 图结构包含顶点数组和顶点/边计数typedefstruct{AdjList vertices;// 顶点数组里面存了 VNode 和 指针intvexnum,arcnum;// 图的当前顶点数和边数弧数}ALGraph;无向图边结点的数量是2|E|整体空间复杂度为O( |V|2|E| )有向图边结点的数量是|E|整体空间复杂度为O( |V||E| )度的求法无向图顶点的度遍历该顶点相关的边链表有多少个边结点就有几度边数所有顶点度数和÷ 2因为每条边被存了两次。有向图顶点的出度OD遍历该顶点相关的边链表反映从当前结点出去的弧。顶点的入度(ID)指向当前顶点的弧计算麻烦需要全部遍历。弧数所有顶点出度之和即所有边表结点总数。对比邻接矩阵 VS 邻接表对比邻接矩阵邻接表空间复杂度O ( ∣ V ∣ 2 ) O(\vert V \vert^2)O(∣V∣2)有向图O ( ∣ V ∣ ∣ E ∣ ) O(\vert V \vert\vert E \vert)O(∣V∣∣E∣)无向图O ( ∣ V ∣ 2 ∣ E ∣ ) O(\vert V \vert2\vert E \vert)O(∣V∣2∣E∣)适用场景稠密图边多空间利用率高稀疏图边少节省空间有向图求入度O ( ∣ V ∣ ) O(\vert V \vert)O(∣V∣)扫描对应一列O ( ∣ V ∣ ∣ E ∣ ) O(\vert V \vert\vert E \vert)O(∣V∣∣E∣)需要遍历全部边为主要缺陷存储唯一性唯一顶点编号顺序确定矩阵就确定不唯一链表结点插入顺序不固定计算度 /出度 /入度必须遍历对应行或列计算有向图的度、入度不方便其余很方便找相邻的边必须遍历对应行或列找有向图的入边不方便其余很方便
RELATED

相关推荐

探索uncertain_ground_truth:革命性框架如何解决AI评估中的模糊标注难题

探索uncertain_ground_truth:革命性框架如何解决AI评估中的模糊标注难题

探索uncertain_ground_truth:革命性框架如何解决AI评估中的模糊标注难题 【免费下载链接】uncertain_ground_truth Dermatology ddx dataset, Jax implementations of Monte Carlo conformal prediction, plausibility regions and statistical annotation aggregat…

📅 2026/9/14 3:36:54
终极指南:如何用Loop免费提升Mac窗口管理效率300%

终极指南:如何用Loop免费提升Mac窗口管理效率300%

终极指南:如何用Loop免费提升Mac窗口管理效率300% 【免费下载链接】Loop Window management made elegant. 项目地址: https://gitcode.com/GitHub_Trending/lo/Loop 你是否曾因Mac上杂乱的窗口布局而感到烦躁?当浏览器、文档、代码编辑器和聊天工…

📅 2026/9/1 2:19:39
PTA团体程序设计天梯赛L2真题讲解L2-041-044

PTA团体程序设计天梯赛L2真题讲解L2-041-044

官网:https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7 文章目录L2-041 插松枝L2-042 老板的作息表L2-043 龙龙送外卖L2-044 大众情人L2-041 插松枝 题目大意 制作松枝的流程包含三个核心对象:推送器(按顺序给出n片…

📅 2026/9/1 10:12:26
MORE NEWS

更多资讯

📰

Windows AI开发目录工程:从mkdir陷阱到PyTorch可训练数据集

1. 这不是普通文件夹创建:一场面向AI工程落地的Windows命令链实战复盘你有没有试过,在凌晨两点赶一个交通路牌识别项目的交付包,打开cmd敲下mkdir D:\模块Bcd /d D:\模块B,回车后发现D盘根目录下多了一个叫“模块Bcd”的空文件夹&…

📰

Jev哑巴模型与TypeSafe AI:类型安全模型接入实战指南

1. 从“哑巴模型”说起:Jev到底是个什么定位第一次看到“哑巴模型”这个词,我脑子里冒出来的画面是一个只会点头摇头、不主动开口的助手。放到AI圈子里,这个说法其实挺形象——它指的是那种不靠“聊天”取胜、而是靠“干活”取胜的模型形态。…

📰

RTL8211F与FPGA的RGMII接口设计:从硬件选型到时序收敛全解析

1. 为什么RTL8211F加FPGA这套组合值得单独拿出来讲搞FPGA网络通信的兄弟大多有过这种经历:板子画好了,PHY芯片焊上去,上电之后FPGA这边数据死活收不到,或者能收到但丢包严重,抓波形一看RGMII时序全是毛刺。RTL8211F这颗…

📰

Jev类型安全AI交互层:结构化输出与Schema校验实战指南

1. 从“哑巴模型”说起:Jev到底是个什么东西第一次看到“Jev”这个词,是在一个开发者群里。有人甩了张截图,说“这玩意儿居然能让模型不废话直接干活”,底下跟了一串“求地址”“怎么接入”。我当时的第一反应是:又一个…

📰

Java实现FastDFS大文件上传与断点续传:从分片到秒传的完整方案

简介:基于Java的FastDFS大文件上传与断点续传设计源码,面向需要处理大文件传输的Java Web开发者,重点解决上传中断、重复存储及秒传等实际问题,可应用于网盘、视频平台、文件管理系统等场景。压缩包共36个文件,约563KB…

📰

从零构建AI工程:数据、训练、推理与监控全链路实战

1. 这个项目到底在解决什么问题第一次看到 "ai-engineering-from-scratch" 这个标题,我脑子里蹦出来的第一个念头是:终于有人把这件事挑明了。市面上讲 AI 的内容铺天盖地,但绝大多数要么停留在"调包侠"层面——import 几…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬