如果标题很令人困惑，我们深表歉意。
我正在用 Java 编写“风险”棋盘游戏，其中 map是由多种颜色的节点组成的节点图。我需要编写一个算法，确定是否可以在两个节点之间找到一条路径(沿着实心空线)，其中给定两个节点之间的所有节点(包括在内)都具有相同的颜色(较小的内圆的颜色) ，而不是较大的大陆彩色圆圈)。
例如，在上面给定的图像中:
东非到乌拉尔是一条有效路径(东非>中东>阿富汗>乌拉尔都是黄色节点)。
非洲东部到秘鲁不是(非洲北部打破了黄色节点的路径)。
在每个节点，我都可以检查其所有相邻节点的颜色，移动到这些相邻节点之一并重复。确定这样的路径是否存在的最有效方法是什么？
感谢您提前提供的任何帮助。
最佳答案
使用边缘收缩将相同颜色的相邻节点合并为单个节点。
为了限制图更新的代价，让每个节点都有一个指向其收缩的指针，并有一个方法将节点映射到其最终值。该方法将缓存最终找到的收缩。
这使得执行边收缩只需创建一个新节点，将两个旧节点指向它，并说该节点有邻居=邻居节点的并集。
现在你的算法如下所示:
to_process = all nodes
while to_process:
node = grab one from to_process
if node has been contracted:
skip
else:
for each neighbor:
if neighbor has the same color:
contract node+neighbor
put contracted node in to_process
// All same color paths now have length 1.
search for points connected by a single point
关于java - 用于确定是否可以在多色节点图的两个节点之间找到相同颜色节点的路径的最有效算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36409346/