关于图表和文字的一些知识 - 多米诺骨牌。第1部分。

第 2 部分 第 3 部分 第 4 部分 我是因为 Java 多线程任务中的一个有害任务而写这篇文章的，开发人员不无戏弄地称该任务为“StringBuilder 任务”。她的病情的本质是一组单词（在给出城市名称的情况下，这让人想起儿童的文字游戏）必须根据多米诺骨牌原理排列，n'单词的最后一个字母应该是等于单词 (n+1) go 的第一个字母，并且已知所有给定的（单独的）单词都以这样的链形式相加。如果可以为所需的单词链组成多个选项，则任何一个都可以作为解决方案。尽管情况看起来简单明了，但解决问题远非易事，熟练使用 StringBuilder 并没有挽救局面。事实证明，这个问题的开发者是来自线性混沌星球的有序同构体，他们不止一次让 JavaRush 学员感到恐惧。正如预期的那样，肤浅的解决方案不适合验证器，因为总是存在迫使朴素算法跳过单词的链。有必要堆积额外的“拐杖”，这虽然使问题复杂化，但并没有使解决方案在一般情况下更接近，并且越来越强化了一种简单的条件应该有一个同样简单的解决方案的感觉。我必须改变策略并深入研究更基本的领域。让我立即保留一点，在任何情况下，我都不认为自己是图论方面的专家；我将涉及的主题几乎不会超出解决多米诺骨牌问题的范围，也许除了一些理论上的题外话。 所以，图表。 什么是图：它是相互连接的顶点的集合（集合、集合、列表等）。连接通常称为边，顶点也称为节点或结点。这是一个图： 这也是一个图： 如果我们可以说一条边有方向，那么该图称为有向图： 前两张图中的图是无向的。我们可以说边 (u, v) 与边 (v, u) 相同，也就是说，例如，边 (0, 4) 和 (4, 0) 是同一条边。有向图边上的箭头表示边 (u, v) 是从顶点 u 到顶点 v 的路径，边 (v, u) 不存在。在第三张图中有一条边缘（E，A）。没有边（A，E）。让我们仔细看看最后一张图。你可以注意到顶点 F 根本没有边，这是很有可能的。我们还注意到，在顶点 A 附近出现了一条边——一个环，并且在顶点 B 和 D 之间有两条不同方向的边。有向图允许出现此类伪影。假设该图描述了一群互相赠送礼物的熟人。我们看到贪婪的F没有给任何人任何东西，B和D交换了礼物（除了他们每个人都给了别人一份礼物），A给了自己一份礼物，可能是在成功解决一个问题之际来自线性混沌星球的问题。顺便说一句，请注意，图的顶点不一定是数字或包含数字；它们更像是容器，即 他们可以存储任何对象。图表是对连接的描述。稍后对我们有用的一个重要术语 - 附加到顶点（或者，正如他们也说的，附属于它）的边的数量称为给定顶点的度。例如，在第一张图中，顶点 0 的度数为 2，顶点 1 的度数为 4，顶点 3 的度数为 3，第二张图的顶点 0 的度数为 1。在本文中，我们不会深入研究各种不同类型的图，我们只会提到还有加权图。每条边都附有一定的数字，表示其通过的“价格”。连通图有许多子类型，按其属性进行区分。例如，边在任何地方都不形成循环的图被称为树（它们有有趣的家族，有很棒的名字，例如“红黑树”），并且广泛用于各种重要的算法和数据结构中。 您可能会说，使用图表来解决问题 所有这些都非常有趣，但是这一切与构建单词链有什么关系呢？事实证明，最直接的就是。让我们看一下条件下的测试示例：{ 阿姆斯特丹 墨尔本 纽约 基辅 维也纳 }。让我们以任意顺序写下单词所附着的“节点”字母：{A，M，N，K，B} 并将它们与单词连接起来。 正如我们所见，我们有一个有向图，其中节点是字母边缘是连接它们的单词。如果我们找到一种方法从一个顶点到另一个顶点遍历所有边，以便我们只访问每条边一次，我们的问题就会得到解决。让我们尝试以稍微不同的方式分布图中的节点： 现在我们可以更好地看到我们的图是一个闭环。我们可以用任何单词开始这个序列，这将是正确的决定。然而，问题的情况告诉我们，任何一种解决方案都足够了。让我们用 Vladimir 替换 Vena： 我们看到两个结果：首先，我们必须添加一个新顶点，即字母 P，其次，我们看到不再可能循环我们的图。让我们总结一下以上内容，并介绍两个新术语： 1. 一个连通图，其边只能通过访问每条边一次来遍历，称为包含“欧拉路径”的图。这种图的一个特征（除了没有无边的顶点之外）是除了两个（并且只有两个）之外的所有顶点的偶数度。2. 如果结果能够返回到原节点，我们就说图中存在“欧拉循环”。这种图的一个特征（除了不存在无边的顶点之外）是所有顶点的偶数度。 让我们想象一下我们的城市列表是这样的：{莫斯科阿纳帕阿德勒顿河畔罗斯托夫武汉}。让我们构建一个图： 在图中您可以看到该图具有欧拉路径。只有两个顶点的度数为奇数 - 它们是 M 和 L，其余的都是偶数：A 的度数为 4，因为 循环计数两次，P和Y的度数为2。如果我们想出一种算法，可以基于这个方案构建欧拉路线，比如说，以列表的形式{M，A，A，P，Y ，L}，那么我们就解决了问题，因为 按给定顺序输出单词只是一个技术问题。因此，多米诺骨牌问题的解决方案归结为实现一种在有向图中 查找欧拉路径（循环是“自由”）的算法。下一页->