存在一种旅行推销员问题，其中最优解的边缘会相交吗？ 节点位于x-y平面中，因此在这种情况下交叉意味着如果你绘制出图形，则连接四个单独节点的两个线段会相交。

我目前正在尝试编写代码以计算度矩阵，以便我可以计算拉普拉斯矩阵L = D-A，其中D=度矩阵，A=邻接矩阵。 这将在我的谱聚类算法中使用。我正在使用Python。所以对于这个玩具例子，我遇到了困难。有人能够提供一个有效的方法来完成这项工作吗？或者是否有用于计算度矩阵的API？我的问题是，计算...

我在网上找到了一个例子，但是仅返回BFS元素的序列不足以进行计算。假设根节点是BFS树的第一层，那么它的子节点就是第二层，以此类推。从下面的代码中，我该如何知道它们所处的层级以及每个节点的父节点是谁（我将创建一个对象来存储其父节点和树的层级）？ # sample graph implemen...

维基页面说： 通过为图中的顶点选择一个全序并将每条边从序列较早的端点指向序列较晚的端点，可以使任何无向图变成DAG。 但我不知道如何获取无向图的全序。应该使用深度优先搜索算法吗？如果是这样，我该如何进行？ 更多信息：我正在处理一个有一个源和一个汇的无向图。我试图定向这些边，以便通...

是否有一份可靠且有良好文档记录的Python库，它具有快速实现在有向图中找到最大流和最小割的算法? python-graph的 pygraph.algorithms.minmax.maximum_flow 解决了这个问题，但速度极慢：在一个有约4000个节点和11000条边的有向图中查找最大...

我有这个问题。我有一个由n个节点组成的图，我想将其分成两个子图，一个包含x个节点，另一个包含n-x个节点，同时满足保留边数最大化（或者最小化切断的边数）的约束。 不确定是否清楚。虽然不是图论专家，但这是我的问题的抽象版本。我应该查看哪些算法能够帮助我呢？ 这不是一道作业题。我认为这是一个有...

最小生成树可以在无向图中找到最便宜的路径。但是最小生成森林是什么？它只适用于连通图还是非连通图？

如何找到（遍历）从/到给定节点的有向图中的所有环？ 例如，我想要像这样的东西：A->B->A A->B->C->A 但不包括： B->C->B

首先，我不是要求代码，我只是想澄清我的方法。 其次，如果这不完全涉及 Stack Overflow，我会将问题移动到最相关的 Stack Exchange 网站。我很确定这是一个图论相关的问题。 所以我有一个带有定义点 (0,0) 的无限大网格。 网格中水平/垂直线之间的每个交点都定义了...

我在比赛中遇到了这个问题，但一直没有想出解决方案。我有一些正整数，需要找到最长的子集，使得相邻的两个元素中一个能够整除另一个。 我的做法是：创建图形，然后连接彼此可以整除的数字节点。之后使用深度优先搜索（一个节点可以连接两个节点）。 但并非所有测试用例都通过了。在使用DFS之前，我需要对数...