就叶子数而言，完整 k 叉树中的节点总数是多少?
我正在做一种独特形式的 Huffman 编码，并且正在构建一个完整的 k-ary(在这种特殊情况下，3-ary)树(每个节点将有 0 或 k 个孩子)，我知道有多少在我建造它之前它就会有.如何根据叶子数计算树中的节点总数? 我知道在完全二叉树(2-ary)的情况下，这个公式是 2L - 1，其中 L 是叶子的数量.我想将此原则扩展到 k 叉树的情况. 解决方案 想想如何证明一棵完整二
..
graph-theory相关内容
正确性证明:图论中树的直径算法
为了找到树的直径，我可以从树中取出任何节点，执行 BFS 以找到离它最远的节点，然后在该节点上执行 BFS.与第二个 BFS 的最大距离将产生直径. 不过，我不确定如何证明这一点?我试过对节点数使用归纳法，但是情况太多了. 任何想法将不胜感激... 解决方案 让我们调用第一个 BFS x 找到的端点.关键的一步是证明在第一步中找到的 x 总是“有效"——也就是说，它总是在某个最
..
什么是好的和稳定的 C++ 树实现?
我想知道是否有人可以推荐一个好的 C++ 树实现，希望是一个如果可能，与 stl 兼容. 为了记录，我以前写过很多次树算法，我知道这很有趣，但如果可能的话，我想变得务实和懒惰.因此，这里的目标是提供指向有效解决方案的实际链接. 注意:我正在寻找通用树，而不是平衡树或地图/集，在这种情况下，结构本身和树的连接性很重要，而不仅仅是其中的数据.所以每个分支都需要能够保存任意数量的数据，并且每
..
为什么用 DFS 而不是 BFS 在图中寻找循环
主要使用 DFS 来查找图中的循环，而不是 BFS.有什么原因吗?两者都可以找到一个节点是否已经在遍历树/图时访问过. 解决方案 深度优先搜索比广度优先搜索的内存效率更高，因为您可以更快地回溯.如果使用调用堆栈也更容易实现，但这依赖于不溢出堆栈的最长路径. 此外，如果您的图表是定向，那么您不仅要记住您是否访问过节点与否，还有你是如何到达那里的.否则，您可能认为您找到了一个循环，但实际
..
找到两个给定节点之间的路径?
假设我有以下方式连接的节点，我如何得出给定点之间存在的路径数量以及路径详细信息? 1,2//节点1和2相连2,32,54,25,1111,126,75,63,66,88,108,9 找到从 1 到 7 的路径: 答案:找到 2 条路径，它们是 1,2,3,6,71、2、5、6、7 实施发现这里很好，我将使用相同的 这是上面python中链接的片段 # 一个示例图图 = {'A
..
C#图形绘制库?
我正在寻找一个(免费的)库，它允许我绘制一个CFG(控制流图).像 yFiles 之类的东西，但是是免费的还是最好是开源的?理想情况下，该库将允许用户导航图形(并修改它)，即图形不仅仅是静态的先验渲染位图.想法? 更新: Glee 与提到 QuickGraph 库似乎工作得很好.谢谢 更新 2:Graph# 似乎是目前最强大的库.还有一个很好的教程关于如何使用它. 解决方案
..
如果我在图形节点中有 2way 关系并且节点是相互关联的，则 Neo4j 查询最短路径卡住(不起作用)
我制作了关系图两个关系，就像如果 A 知道 B 那么 B 知道 A，每个节点都有唯一的 Id 和 Name 以及其他属性......所以我的图看起来像 如果我触发一个简单的查询MATCH (p1:SearchableNode {name: "Ishaan"}), (p2:SearchableNode {name: "Garima"}),path = (p1)-[:NAVIGATE_TO*]-
..
带分组的拓扑排序
好的，所以在根据输入数据进行拓扑排序时，通常有多个正确的解决方案可以“处理"图形的顺序，以便所有依赖项都出现在“依赖"于它们的节点之前.但是，我正在寻找一个略有不同的答案: 假设有以下数据:a ->b 和 c ->d(a 必须在 b 之前，c 必须在 d 之前). 仅凭这两个约束，我们就有多个候选解决方案:(a b c d、a c d b、c a b d 等).但是，我希望创建一种“分组"
..
VF2 算法的任何工作示例?
我一直在阅读 VF2 算法 用于查找两个图是否同构但不知何故错过了大局.可能是我错过了这方面的相关背景，但我所看到的只是一堆我需要在每个步骤中使用的规则，而没有看到为什么要执行这些步骤的直观解释. 从基本的谷歌搜索来看，这似乎被认为是查找两个图是否同构的事实上的算法之一，但由于某种原因，我无法找到一个足够简单的解释，可以在高层次上理解.或者这个算法有别的名字吗? 无论如何，有没有人知道
..
Javascript有向无环图库?(不需要图形可视化)
我有一个最好用图表表示的数据集.它由具有有向边的 6 或 7 种不同“类型"的节点组成(相互依赖，保证没有循环依赖).数据集本质上是一个分层配置的模板，用户需要能够从不同的层中选择所需的配置的点点滴滴，并自动引入相关的位. 一般的 UI 需求是让用户从多选框(每个节点类型一个这样的框)中选择或取消选择项目，并在其他框中选择或取消选择“依赖"项目需要.我需要能够从服务器下拉数据集，让用户选择所
..
用于 Python 的快速最大流最小切割库
是否有可靠且文档齐全的 Python 库，可以快速实现在有向图中找到最大流和最小割的算法? pygraph.algorithms.minmax.maximum_flow 来自 python-graph 解决了这个问题，但是它非常缓慢:在有 4000 个节点和 11000 条边的有向图中找到最大流和最小割需要 > 1 分钟.我正在寻找至少快一个数量级的东西. 悬赏:我在这个问题上悬赏，看
..
稀疏图和密集图有什么区别?
我读到通过邻接列表表示稀疏图和通过邻接矩阵表示密集图是理想的.但我想了解稀疏图和密集图之间的主要区别. 解决方案 Dense graph 是边数接近最大边数的图.稀疏图是边数接近最小边数的图.稀疏图可以是断开连接的图.
..
汉密尔顿路径和欧拉路径的区别
谁能告诉我汉密尔顿路径和欧拉路径之间的区别.他们看起来很像！ 解决方案 欧拉路径是一条通过每条边恰好一次的路径.如果它在初始顶点处结束，则它是一个欧拉循环. 哈密顿路径是通过每个顶点恰好一次(不是每条边)的路径.如果它在初始顶点处结束，则它是一个哈密顿循环. 在欧拉路径中，您可能会不止一次通过顶点. 在哈密顿路径中，您可能不会通过所有边.
..
图数据结构:DFS vs BFS?
如果给定一个图形问题，我们如何知道我们需要使用 bfs 还是 dfs 算法???或者我们什么时候使用 dfs 算法或 bfs 算法.一种与另一种的区别和优势是什么? 解决方案 BFS 将根据分支因子使用更多内存...然而，BFS 是一个完整的算法...意味着如果你使用它来搜索对于尽可能低的深度的东西，BFS 会给你最佳的解决方案.BFS 空间复杂度是 O(b^d)... 分支因子提升到深度
..
图形可以比替代方案更好地解决问题的好例子是什么?
阅读 Stevey Yegge 的 Get That Job At谷歌文章，我发现这个小引用很有趣: 每当有人向您提出问题时，请考虑图表.它们是表示任何类型关系的最基本和最灵活的方式，因此任何有趣的设计问题都包含一个图形，大约是 50-50 个镜头.在转向其他解决方案类型之前，请务必确保您无法想出使用图形解决问题的方法.这个提示很重要！ 图数据结构/算法最能代表和/或解决的问题有哪些例
..
在直接加权图中找到从节点 A 到节点 B 的所有简单路径，权重之和小于某个值?
我有一个有向加权图 G=(V,E)，它可能有环. 我正在尝试确定完成任务的最佳时间效率算法:t找到 G 中源节点和目标节点之间的所有简单路径，该路径中边的总权重小于某个值(为方便起见，我们将此值表示为 PATH_WEIGHT_LIMIT) 所有权重都是正数，可以浮动. 所以，我的函数原型是: def find_paths(G, source, target, path_weig
..
求矩阵中连通集总数的算法
我想知道我应该在这里应用哪种算法.DFS 可以吗? 给定一个二维矩阵.求该矩阵中连通集的总数. 连接集可以定义为一组小区，其中提到了 1 并且在该组中至少有一个其他小区与它们共享邻居关系.一个包含 1 且周围没有包含 1 的邻居的单元可以被认为是一个包含一个单元的集合.邻居可以定义为在 8 个可能的方向(即 N、W、E、S、NE、NW、SE、SW 方向)上与给定小区相邻的所有小区.一个
..
包含给定节点集的最小连通子图
我有一个未加权的连通图.我想找到一个连接的子图，它肯定包含一组特定的节点，并且尽可能少的额外.这怎么可能实现? 为了以防万一，我会用更精确的语言重申这个问题.令 G(V,E) 是一个未加权、无向、连通图.设 N 是 V 的某个子集.找到 G(V,E) 的最小连通子图 G'(V',E') 使得 N 是 V' 的子集的最佳方法是什么? 近似值很好. 解决方案 我想不出一种有效的算法
..
如何在线性时间内找到树中最短的简单路径?
这是 Vazirani 的算法书中的一个问题 这个问题的输入是一个边上具有整数权重的树 T.权重可能为负，零，或正.给出一个线性时间算法来寻找 T 中最短的简单路径. a 的长度path 是路径中边的权重之和.如果没有重复顶点，则路径是简单的.笔记路径的端点是不受约束的. 提示:这与寻找树中最大独立集的问题非常相似. 如何在线性时间内解决这个问题? 这是我的算法，但我想知道
..
查找图中的所有循环，redux
我知道这个问题有很多答案.但是，我发现他们中没有一个人真正切中要害. 有些人认为循环(几乎)与强连接组件相同(s. 在有向图中查找所有循环)，因此可以使用为该目标设计的算法. 一些人认为，可以通过 DFS 并检查后缘来找到一个循环(s.关于文件依赖关系的增强图文档). 我现在想就是否可以通过 DFS 检测图中的所有循环并检查后边缘提出一些建议? http://www.me.utexas
..