标签: graph-algorithm

我正在准备考试，但我遇到了这个问题：

我们有n支球队，彼此交手两次。每场比赛均以平局结束。获胜次数最多的团队被宣布为获胜者（可以多于一个）。设计一种算法，在给定一组初始比赛结果的情况下，检查某个球队是否仍有机会成为本次锦标赛的获胜者。

我不知道如何接近。该问题被放在“流量和匹配”类别中，但我不明白这怎么可能是最大流量问题。

我试图找到这个问题的名称，但不知道如何搜索它。问题如下：

找到图中的路径，从顶点 A 开始，在两个方向上每条边恰好经过所有边两次（一次在一个方向，第二次在相反方向），最后一步再次到达顶点 A。

如果有人给我一些关于如何称呼这个问题的提示（因为它听起来像是一个众所周知的问题），并且可能提供一些解决方案的指导，我会很高兴。

我试图使用动态规划来理解树分解中的最大独立集问题。然而，我无法在所提出的算法中理解“分隔符”的概念。有人可以让我清楚这一点吗？提前致谢。

我有一个networkx.Graph表示一个图的对象，其节点表示英语单词，其两个 wnode 之间的边意味着这些节点表示的两个单词在其同义词集之间至少有一个共享的认知同义词（即非空交集）。我希望这对某人来说是有趣或有用的背景，但我的问题是一个与图、Python 相关的更广泛适用的问题。networkx

该图的许多诱导子图（边诱导或顶点诱导）都是边不相交和顶点不相交，我想将这些子图分成它们自己的networkx.Graph对象，以便它们连接且相互不相交。我可能只是在networkx文档中使用了错误的搜索词，但我没有看到任何与 "disjoint" 相关的有前途的内容。以下是来自图表一小部分的一些示例。

我查看了Stack Overflow 上的搜索结果[networkx] disjoint，但没有看到我要找的内容。例如，一个结果讨论了当已经有一条边集可以从 中导出时获取导出子图。或者另一篇文章谈到尝试绘制两个不相交的图，但这是假设您已经拥有它们。与我的问题的图论方面相关，但与该networkx方面无关的是，显然存在诸如洪水填充算法之类的东西，可以解决我的问题的一部分。

现在，作为一个最小的工作示例，让我们创建一个小的随机图，但确保它已断开连接。

import networkx as nx

g = nx.fast_gnp_random_graph(10, 0.3)

while nx.is_connected(g):
    g = nx.fast_gnp_random_graph(10, 0.3)

此时，我们就有了一个图表g。我想到的是如下所示的内容，其中我占据了相互不相交的图形列表。我不仅需要在循环节点时添加更多图表，还需要随时更新图表。我认为归纳图的并集可能会起作用，但是 和nx.disjoint_union_all要么nx.union会通过重新标记来强制图不相交（我不希望这样），要么期望图已经不相交。

graphs = []

for node in g.nodes(): # same 'g' …

给定无向图和连通图G，找到直径最小的生成树。

我将我的图表表示为邻接列表.我想知道如何找到一个内部连接但没有边缘点的节点集群.有没有我可以使用的众所周知的算法？

对于egThis是我的图表.

1---->2
2---->1
2---->3
3---->1
3---->4
4---->5
5---->4

节点4和5在内部连接.然而,没有外界优势.这将是我的答案.类似地,节点1,2,3即使它们形成一个循环,也不符合标准,因为外边缘从节点3发出.因此它与在邻接列表中找到循环不同.

可选阅读:(为什么我需要这个)我正在研究排名页面(搜索引擎)算法,像4和5这样的节点称为排名接收.

我试图让一个敌人节点跟随C#中的玩家节点使用A*算法.我已阅读教程并下载了一些C#exmaples.我的A*算法现在已达到一定程度.它将在开放空间中跟随玩家,但在尝试追踪对象时遇到障碍.

因此,当我的算法检查并向最低F值方向移动时,它可能会遇到一个死胡同,此时它需要向后回溯它的步骤,但它不能,因为我的代码告诉它先前检查过节点已关闭且无法移动到,因此它会卡住.

如何重新计算一个封闭的节点,告诉我的算法可以以这种方式返回.

此外,如果我确实告诉我的算法重新开始,那么什么是阻止它再回到AGAIN到它刚刚来的更好的节点; 有效地在两个节点之间反复回归.

我看到它应该能够检查关闭列表中的节点并确定它在这个特定路径上是否更好,但我不确定如何完成.

我正在使用的启发式方法.

G = Math.Abs(StartNodeX - TargetNodeX) + Math.Abs(StartNodeY - TargetNodeY)

H = Math.Abs(CurrentNodeX - TargetNodeX) + Math.Abs(CurrentNodeY - CurrentNodeY)

F = G + H

伪码.

1. 将所有相邻节点添加到打开列表
2. 检查所有这些节点的最低F分数,并将该节点添加到最佳路径列表
3. 将所有选中的节点添加到"关闭列表"(它们都已经过检查,不想再次检查)
4. 重复直到达到目标
5. 沿最佳路径方向移动敌人1节点
6. 重复一遍

我需要帮助解决这个问题POUR1.我认为它可以通过强力方法解决,但我读到这是一个图形问题(BFS).我解决了ABCPATH,LABYR1,PT07Y,PT07Z,BITMAP等问题......
但我不知道如何以BFS方式接近POUR1.

有人可以给我一些建议吗？

问题陈述:

鉴于两艘船,其中一艘可以容纳一升水,另一艘可容纳一升水,确定在其中一艘船中获得精确c升水所需的步数.

起初两艘船都是空的.以下操作计为"步骤":

• 清空一艘船
• 填充船只,
• 将水从一个容器倒到另一个容器中,不会溢出,直到其中一个容器满或空.

输入:

整数t,1 <= t <= 100,表示测试用例的数量,后跟t组输入数据,每组输入数据由三个正整数a,b,c组成,不大于40000,在单独的行中给出.

输出:

对于每组输入数据,输出获得c升所需的最小步数,如果不可能,则输出-1.

例:

样本输入:

2
5
2
3
2
3
4

样本输出:

2
-1

真正的问题是如何在ruby中表示图形数据结构(一些示例代码可能有助于我理解).

我目前有想法代表图表.即每一个Node具有array的neighbourNodes其是object_id节点对象.有没有更好的解决方案？我可以轻松地通过一些库来实现这一点.我已经看过GRATR和RGL.两者都已经过时了(至少我是这么认为的.)无论如何,任何有关tuby 2.0.0的工作示例都会对我有所帮助.

我有Busstops哪些作文Routes.Routes是一系列的Busstops.我如何表示所有的图表Routes.我想使用Dijkstra的算法来找到两个总线停止之间的最短路径(可能会或可能不会在同一个路径上Route.这意味着您必须在途中更换总线)).

我有一个部分或完全循环的图,我想根据前面节点的成本的加权和来计算每个节点的成本.没有传入边缘的节点具有分配给它们的固定成本.

例如,下面的图表标记了每个节点的计算成本(节点2的成本是固定的),每个边缘都标有前一个节点的权重.因此,节点1.33成本从1*0.33 + 0.5*2计算.

我目前使用迭代方法计算每个节点在某个epsilon内的成本,但我正在寻找一种能够精确计算成本的算法.上面的例子非常简单,实际问题涉及每个强连接组件约100个节点.对算法有什么建议可以解决这个问题吗？