福特-福克森算法为什么需要反向边？
为了在一个图中找到最大流，仅饱和所有增广路径上的最小边容量而不考虑反向边是否能够满足需求是不够的。如果我们假设从反向边出发有流量，那么称其为反向边又有什么意义呢？
我们能否使用并查集数据结构来检测有向图中的循环？
我知道可以使用深度优先搜索 (DFS) 和广度优先搜索 (BFS) 来检测有向图中的循环。但我想知道是否可以使用 并查集 来检测有向图中的循环呢？ 如果可以，那么如何进行？ 如果不能，那么为什么？
简化加权有向债务图的算法
我写了一个小的Python脚本来管理我和室友之间的债务。它能够运作，但有一些缺失特性，其中之一是简化不必要复杂的债务结构。例如，如果以下加权有向图表示一些人，箭头代表他们之间的债务(Alice欠Bob 20美元和Charlie 5美元，Bob欠Charlie 10美元等)： 显然，这个图...
寻找三角网格的最近邻居
我有一个类似于所示图案的三角形镶嵌。给定镶嵌中三角形的数量N，我有一个N X 3 X 3数组，其中存储了每个三角形的三个顶点的(x, y, z)坐标。我的目标是为每个三角形找到共享相同边的相邻三角形。关键部分在于我不重复计算邻居数。也就是说，如果三角形j已经被计算为三角形i的邻居，则三角形i不...
将节点连接以最大化总边权值
我正在解决一个问题，它可以简化为以下的图优化问题。 给定一组有颜色的节点。它们都没有连接，即在图中没有边。 需要在这些节点之间插入边。 每个节点最多只能有4条边。 一张表格提供了从边缘获得利润的规则。 例如， 将红色节点与红色节点连接的边缘：利润为10。 将红色节点与蓝色节点连接的边...
我们能否将贝尔曼-福德算法应用于无向图？
我知道贝尔曼-福德算法适用于有向图。它是否适用于无向图？似乎对于无向图，它将无法检测出环路，因为并行边会被视为环路。这是真的吗？该算法能否应用于无向图中？
具有最小违反边数的循环图的拓扑排序
我正在寻找一种方法，在给定的有向无权图上执行拓扑排序，该图包含环。结果不仅应包含顶点的排序，还应包含由给定排序违反的边的集合。此边集应为最小。 由于我的输入图可能很大，我不能使用指数时间算法。如果无法在多项式时间内计算出最优解，那么对于给定问题，什么启发式方法是合理的？
如何证明n个节点之间的最大连接数为n*(n-1)/2。
给定 n 个节点，如果每个节点都与其他每个节点（除自身外）相连，则连接的数量将为 n*(n-1)/2。 如何证明这一点？ 这不是一个作业问题。我已经离开计算机科学教材很长时间了，已经忘记了如何证明这一点的理论知识。
为什么Dijkstra算法使用堆（优先队列）？
我曾经在一个带权有环图上尝试使用Djikstra算法，没有使用优先队列（堆），结果是可行的。 维基百科指出，该算法最初的实现不使用优先队列，并且运行时间为O(V^2)。 现在，如果我们只是移除了优先队列并使用普通队列，则运行时间是线性的，即O(V+E)。 有人可以解释一下为什么我们需要优...
计算两点之间的最短路径
我在过去几周一直在开发一个多人在线HTML5游戏，使用nodejs和websockets。 我有一个问题困扰了我一段时间。假设有一个由数组实现的瓦片地图（如下所示）。 1或棕色瓷砖 - 道路上有障碍物，玩家不能通过它。 0或绿色瓷砖 - 是允许玩家移动的自由路径。 通过调用以下方式访问地图上的...