程序员经验分享-hwhale

除了邻接表或邻接矩阵之外，还有其他数据结构可以表示图吗？

2023-12-26

我一直在寻找不同的数据结构来表示图形，我遇到了 Nvidia CUDA Toolkit，并在 source_indices、destination_offsets 的帮助下找到了表示图形的新方法。

我对这种创新的图表示方式着迷，因此寻找其他表示图的方法。但没有发现什么新东西。

我想知道除了邻接矩阵或列表之外是否还有其他方法来表示图......


我想知道是否还有其他方法来表示其他图 比邻接矩阵或列表...

邻接表或邻接矩阵还有其他选择，例如边列表, 邻接图 or 前锋星仅举几例。鉴于此图（图像取自here http://cecas.clemson.edu/~shierd/Shier/):

  • 这是邻接矩阵表示:
  • 这是邻接表表示:
  • 这将是另一种选择，边列表:
  • 另一个很常见的就是前向星代表:

如果你进入这个研究领域你会发现很多方法，主要是优化对于具体情况，考虑以下因素：

  • 图大小（节点数）
  • 图的密度
  • 有向图或无向图
  • 静态或动态图
  • 图在编译时已知或在运行时构造
  • 节点 ID（按顺序标记或不按顺序标记）
  • ...

例如，这些优化可以支持节点重新排序 in a 预处理阶段增加参考地点。还有很多工作要做最短路径算法，特别是在计算世界地图中的最短路径时。

优化的一个例子是动态图结构 (打包内存图 (PMG) https://www.ceid.upatras.gr/webpages/faculty/zaro/pub/conf/C63-CIAC2013-new-dyn-graph.pdf) 适合于大规模的交通网络.

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

datastructures

Graph

graphalgorithm

adjacencymatrix

adjacencylist

除了邻接表或邻接矩阵之外，还有其他数据结构可以表示图吗？ 的相关文章

  • ZedGraph 垂直线与 LineObj 问题

    我有一个 ZedGraphControl 里面有几条曲线 我想在一些固定的 x 位置添加垂直线 当然 这些线只能位于实际图形区域内 我尝试以下 LineObj line new LineObj Color Black xPos myPane

  • 如何在 C# 中创建真正不可变的双向链表？

    这更多的是一个理论问题 在 C 中是否可以通过任何方式创建一个真正不可变的双向链表 我认为一个问题在于两个相邻节点的相互依赖 我所说的 真正 是指使用只读字段 这可以通过棘手的构造函数逻辑来完成 例如 public sealed class

  • Gremlin 按顶点属性分组并获取同一顶点中其他属性的总和

    我们有顶点来存储各种作业及其类型 并算作属性 我必须按状态和数量进行分组 我尝试了以下查询 该查询适用于一个属性 receiveCount g V hasLabel Jobs has Type within A B C group by T

  • 比较周期性数据的快速方法

    假设我有任意类型的数据集 A B C D 并且我想将其与另一个数据集进行比较 我希望 A B C D B C D A C D A B 和 D A B C 的比较成立 但是不适用于 A C B D 或任何其他未类似排序的集合 有什么快速方法可

  • PHP 中的 MPTT（修改的先序树遍历）问题

    我的第一篇文章在这里 看来这是一个变得明智的地方 我目前正在进行一些测试 第一次尝试使用 MPTT 修改的预序树遍历 方法在 PHP 的帮助下将数据存储在 Mysql 数据库中 但是 我试图找到最注重性能的方法来获取特定级别上的所有列表元素

  • 使用 NSMutableDictionary 与 NSMutableArray 造成的性能损失>

    我正在考虑使用 NSMutableDictionary 代替我当前的 NSMutableArray 这主要是出于 KVC KVO 的原因 该集合将在我的绘图方法的内循环中经历严重的变化 如果我继续进行此替换 性能是否会受到重大影响 干杯 道

  • 有向图的并查/不交集数据结构

    我正在寻找一个高效的联查 aka 不相交集 https en wikipedia org wiki Disjoint set data structure 我的数据结构有向图 https en wikipedia org wiki Dire

  • 计算 List 中相似的相邻项目数

    我试图在列表中找到相似的相邻项目并计算其数量 例如 List

  • 如何显示 matplotlib 饼图中的实际值

    我有一个饼图 绘制从 CSV 文件中提取的值 当前显示值的比例 百分比显示为 autopct 1 1f 有没有办法显示每个切片的数据集中表示的实际值 Pie for Life Expectancy in Boroughs import pa

  • 为什么 Java 中的 hashCode() 可以对不同对象返回相同的值？

    引用我正在读的书中的一段话首先Java http www amazon co uk Head First Java Kathy Sierra dp 0596009208 关键是 哈希码可以相同 但不一定保证对象相等 因为使用的 哈希算法 h

  • R：邻接表到邻接矩阵

    Bonjour 我想将邻接列表 3 列 转换为邻接矩阵 在这个论坛中 我找到了多个有关如何将边列表转换为邻接矩阵的示例 我成功地为两列列表做到了这一点 我已经尝试了在网上可以找到的所有解决方案 但似乎我错过了一小步 我尝试过的 我的变量是用

  • 如何从数组表示构建不完全二叉树

    如果输入是一个数组 其中null表示没有节点 input 1 2 3 null 5 null 7 请假设我已经检查过输入 对于每个array i 它的父母array i 2 不会是null 递归地 所以根不能是null 如何构建具有这样的逻

  • Gremlin 中的广度优先枚举

    我正在尝试使用 Gremlin 进行广度优先枚举 但是我无法找到一种方法来输出枚举期间观察到的所有步骤 我只能打印出最后一次迭代的结果 我的问题是 给定这样的起始节点 我如何使用 Gremlin 跟踪所有路径 不知道整体深度 并打印出我沿途

  • R中一张图中的多个条形图

    我是 R 初学者 我需要创建一个像这样的图表 https i stack imgur com az56z jpg https i stack imgur com az56z jpg 我不知道如何生成整个数据集 基本思想是某个外显子 ID 会

  • 图中的后边

    I m having a hard time understanding Tarjan s algorithm for articulation points I m currently following this tutorial he

  • 子序列和

    给定一个整数数组 例如 1 2 3 1 查找是否存在总和为0并返回它 例如 1 2 3 or 2 3 1 检查每个子序列是O n 2 这效率太低了 有改进的想法吗 创建一个新数组 其中每个元素等于前一个元素加上该元素的总和 Input 1

  • 生成二叉树的所有从根到叶的分支

    抱歉 如果这是一个常见问题 但我还没有找到适合我的特定问题的答案 我正在尝试实施一个walk方法将二叉树从根节点遍历到每个叶节点 每当到达叶节点时都会生成根到叶路径 例如 遍历表示为的二叉树 a b d c 会产生 a b c a d 我的

  • 如何在文件系统中存储图像

    目前 我已将图像 最大 6MB 作为 BLOB 存储在 InnoDB 表中 随着数据大小的增长 夜间备份变得越来越慢 阻碍了正常性能 因此 二进制数据需要进入文件系统 指向文件的指针将保存在数据库中 数据具有树状关系 main site u

  • 用表达式分割轴标签

    我有一个带有包含表达式的长标签的图 我想将其分成两行 在表达式中添加 n 结果不符合预期 ylabel lt expression A very long label with text and n expression alpha bet

  • Data.Sequence 中的 inits 和 tails 如何工作？

    Louis Wasserman 编写了当前的实现inits and tails in Data Sequence 他表示它们非常高效 事实上 只要查看代码 我就可以看到 无论它们在做什么 它们都是以干净 自上而下的方式进行的 这往往会给惰性

随机推荐

  • JavaScript - 将带有方法的对象保存为字符串

    我一直在寻找一种方法来做到这一点 但似乎找不到任何东西 我有不同的配置对象 我需要将它们保存为变量中的文本以便稍后进行处理 这里是一个示例 object args config config next null final delimite

  • 阅读此 XML 的好方法是什么？

    阅读此 XML 的好方法是什么 或者也许我可以以不同的方式构建 XML 我想要的是流程成为主要内容 然后您可以遵循任意数量的相关流程

  • 如何阻止 favicon.ico 请求？

    我没有 favicon ico 但我的浏览器总是发出请求 是否可以阻止浏览器从我的网站发出对网站图标的请求 也许 HTML 标头中有一些元标记 我首先要说的是 在网页中拥有网站图标是一件好事 通常 然而 这并不总是理想的 有时开发人员需要一

  • 错误：（gcloud.services.enable）用户无权访问项目（或者可能不存在）：调用者没有权限

    我希望编写一个可以从 Cloud Shell 运行的脚本 以便在所有项目中启用 API 它正在成功地完成每个项目 但我收到每个项目都被拒绝的消息 我是所有者 所以不应该有任何许可问题 作为权限测试 如果我仅运行 gcloud service

  • C++三元运算符执行条件

    我不确定 C C 三元运算符的执行保证 例如 如果给我一个地址和一个布尔值来判断该地址是否适合读取 我可以使用 if else 轻松避免读取错误 int foo const bool addressGood const int ptr if

  • 为 jQuery 延迟对象提供默认的“失败”方法

    我正在使用 jQuery 编写一个 Javascript API 客户端 我的顶级请求方法如下所示 function request method uri params proxies var deferred Deferred ajax

  • Fabric.js 直线并单击选择

    我为这段代码创建了 3 种模式 选择行 画线和 删除行 看起来它正在工作 但我想改变两件事 例如 每次我选择一行时 我只需要单击它 你能告诉我如何改进我的代码吗 谢谢您的回答 这是我的代码

  • 在 SecurityContext 中找不到 Authentication 对象 - Spring 3.2.2

    我正在尝试从实现了的类中调用受保护的方法ApplicationListener

  • Firebase 云函数打字稿错误“并非所有代码路径都返回值”

    我正在使用 firebase 云功能和 firestore 交易来减少基于购买的产品的可用数量 部署时 它返回错误 错误 TS7030 并非所有代码路径都返回值 这是代码 import as functions from firebase

  • 在本地模拟/模拟 SQL Azure？

    与常规 MS 开发内容相比略有 OT 我想使用 MSSQL 2008 作为数据库来编写我的下一个 NET 4 0 应用程序 但以 Azure 就绪 的方式配置存储和访问方法 因此当新的财政年度在夏季开始时 我们可以想象做一些影响较小的事情

  • iPhone：Bonjour NSNetService IP 地址和端口

    请原谅我的 iPhone Objective C 新手身份 我已经使用 NSNetServiceBrowser 找到了我的 HTTP 服务器 但现在我只想找到该服务的 IP 地址和端口 我的委托方法中有类似以下内容的内容 NSNetServ

  • 使用 Java Stream API，查找变量的最高值，以及对变量所做的更改的流

    背景 场景 假设我们有一个不可变的对象 名为Transaction where transaction getAction 会返回一个TransactionAction enum这可以是DEPOSIT or WITHDRAW and tra

  • Sql - WHERE 条件的显式顺序？

    有没有办法明确说明 WHERE 条件发生的顺序 我意识到查询优化器将查看 WHERE 子句的所有部分 以确定满足查询的最有效方法 如这些答案中所述 SQL 中 where 子句的顺序重要吗 https stackoverflow com q

  • Spring JpaRepository 中的%Like%查询

    我想写一个类似的查询JpaRepository但它没有返回任何东西 LIKE place 它不工作 LIKE place 工作完美 这是我的代码 Repository registerUserRepository public interf

  • Selenium Webdriver Chromedriver 在无头模式下启动时超时

    我正在使用 Selenium Webdriver 带有 Ruby 32 位 1 9 3 Chromedriver v2 9 248315 Chrome 38 0 2125 111 m 和 Jenkins 1 588 的本地实例 Gems c

  • WPF SaveFileDialog DefaultExt 被忽略？

    var dlg new SaveFileDialog dlg FileName graph dlg DefaultExt bmp dlg Filter PNG png DOT dot Windows Bitmap Format bmp GI

  • 通过 Digital Ocean 安装的 npm 被杀死

    大约一年前 我将一个存储库上传到我的 Digit Ocean Droplet 并尝试 npm install 但没有成功 我最近决定再次尝试并尝试解决这个问题 但当我尝试 npm install 时 仍然收到 Killed 错误 我知道有些

  • Appveyor 上的 GitHub API 未经授权的响应

    我们刚刚开始一个新项目 并试图通过 Appveyor 让 CI 工作 它是一个Aurelia网络应用程序所以我们需要jspm在构建服务器上 在我的工作站上我手动配置jspm https github com jspm jspm cli bl

  • 编译器优化安全吗？

    我最近在工作中发现 由于存在编译器错误的风险 硬实时嵌入式系统不使用编译器优化是政策 我们主要使用 gcc 但该政策也扩展到其他编译器 显然 这个政策的开始是因为过去有人因优化器的错误而被烧伤 我的直觉是 这过于偏执 所以我开始寻找有关此问

  • 除了邻接表或邻接矩阵之外，还有其他数据结构可以表示图吗？

    我一直在寻找不同的数据结构来表示图形 我遇到了 Nvidia CUDA Toolkit 并在 source indices destination offsets 的帮助下找到了表示图形的新方法 我对这种创新的图表示方式着迷 因此寻找其他表

热门标签