關於圖表和文字的一些知識 - 多米諾骨牌。第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} ，那我們就解決了問題，因為 按給定順序輸出單字只是一個技術問題。因此，多米諾骨牌問題的解決方案歸結為實現一種在有向圖中 尋找歐拉路徑（循環是「自由」）的演算法。下一頁->