使用圖形和樹可以解決哪些問題或更容易解決哪些問題？

Question

這兩種數據結構可以解決哪些最常見的問題？

這將是對我好也有書的建議是：

• 實現結構
• 實現和解釋的使用它們的算法推理

Answer 1

我讀到這個問題時首先想到的是：什麼類型的東西使用圖/樹？然後我回想我如何使用它們。

例如，採取樹的兩個常見用途：

• 的DOM
• 文件系統

的DOM和XML對於這個問題，像樹結構。

它也是有意義的。 這是有道理的，因爲這些數據需要如何安排。也是一個文件系統。在UNIX系統上有一個根節點，並在下面分支。當你安裝一個新設備時，你將它連接到樹上。

你也應該問自己：數據是否屬於這種類型的結構？創建對問題有意義的數據結構，其餘部分將隨之而來。

只要更容易，我認爲那是相對的。你用遞歸函數遍歷一棵樹/圖是否合適？如果你需要平衡這棵樹怎麼辦？

想想解決一個字搜索難題的程序。您可以將單詞搜索的所有字母映射到圖中，並檢查周圍的節點，以查看該字符串是否與任何單詞匹配。但是難道你不能只用一個數組來做同樣的事情嗎？你真正需要做的就是移動一個索引來檢查左右兩邊的字母，並用寬度來檢查字母上下。用圖表解決這個問題並不困難，但是如果你不習慣使用它們，它會產生很多額外的工作和難度 - 當然這不應該阻止你這樣做，特別是如果你正在學習他們。

我希望能幫助你考慮這些結構。至於書籍推薦，我必須去Introduction to Algorithms。

Answer 2

有一個過程在我的大學這樣的事情：CSE 326。我並不認爲這本書太有用，但是這些項目很有趣，並教你一些關於實現一些簡單結構的一些事情。

至於示例，用樹解決的最常見問題之一（由使用它的人數）是手機文本輸入的問題。您可以使用樹（不一定是二進制）來表示可能來自任何給定數字列表的可能詞的空間，用戶可以很快地對其進行打分。

Answer 3

Algorithms for Java: Part 5作者：Robert Sedgewick所有關於圖算法和數據結構。如果你想實現一些圖算法，這將是一本很好的第一本書。

Answer 4

在遊戲和多媒體應用程序中繪製圖形的場景圖大量使用樹和圖形。節點表示要呈現的對象，變換，控件，組...

場景圖通常具有多個圖層和屬性，這意味着您只能按指定的順序（圖層）繪製某個圖的某個節點（屬性） 。根據場景圖的種類，它可以有兩個parralel結構：聲明和實例化。 Th

Answer 5

The Algorithm Design Manual包含一些有趣的案例研究與創造性地使用圖。儘管它的名字，這本書是非常可讀，甚至有時娛樂。

Answer 6

@DavidJoiner /所有：

FWIW：在Algorithm Design Manual的新版本現在任何一天是由於出來。

是Skiena他開發了教授這本書的整個過程也可在網絡上：

http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html

Answer 7

電路圖。

彙編（定向非循環圖）

地圖。非常緊湊的圖形。

網絡流量問題。

決策樹木專家系統（SIC）

魚骨圖查找故障，工藝改良效果，安全性分析。對於獎勵積分，請將您的錯誤恢復代碼作爲爲魚骨圖的對象。

Answer 8

由於其遞歸性質，樹在函數式編程語言中被更多地使用。

此外，圖形和樹是模擬很多AI問題的好方法。

Answer 9

幾乎每個問題都可以用圖論的方法來重寫。我不是在開玩笑，看任何關於NP完整問題的書籍，還有一些非常古怪的問題轉化爲圖論，因爲我們有很好的工具來處理圖表......

Answer 10

遊戲中經常使用圖表來幫助查找通過遊戲世界的路徑。世界的圖形表示可以具有諸如廣度優先搜索或A *的算法以便找到穿過它的路線。

他們還經常使用樹來表示世界中的實體。如果您有成千上萬的實體，並且需要在某個位置找到一個實體，那麼通過列表進行線性迭代可能效率很低，尤其是在需要經常執行時。因此，該區域可以細分爲一棵樹，以便更快地搜索它。就像線性空間可以用二進制搜索有效地搜索（並且因此被分成二叉樹）一樣，2D空間可以被劃分爲quadtree和3D空間成爲octree。