學習圖算法

在算法中，我主要是自學成才的，這很好。但是，我很難理解圖形算法。我正在尋找一些具有概念和實際代碼的參考資料，所以我不僅可以學習理論（我通常可以做到這一點），還可以瞭解圖表在實踐中如何表現和操縱圖表（我通常具有更難掌握）。可以提供嗎？只要有概念和實現，從書本，鏈接到現有項目的任何事情都會很好。學習圖算法

這是語言不可知的，但我最熟悉python，並沒有太多的FP經驗。

來源

2010-10-27 jlv

這兩者都是非常好的：

The Algorithm Design Manual
Algorithms in C++ Part 5: Graph Algorithms（別擔心C++位，也有僞代碼）

免費的東西：

Chapter 5. Graphs and graph algorithms

來源

2010-10-27 01:35:44

TADM剛剛提到（再次感謝，但！）但我會檢查第二個肯定。 – jlv 2010-10-27 01:37:47

Steve Yegge說this是關於廣泛使用圖的算法的一本了不起的書。

來源

2010-10-27 01:33:09 duffymo

亞馬遜願意上市。 – jlv 2010-10-27 01:37:05

我學到了很多從下面鏈接的書圖...這是我最喜歡的一本書： http://books.google.com/books?id=5l5ps2JkyT0C&printsec=frontcover&dq=a+course+in+combinatorics&source=bl&ots=wSYYY6KPuI&sig=mZLrdj0xo2mTxW4MxYt4tW_E-10&hl=en&ei=PoHHTOaROIHGlQegn8ibAg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CCkQ6AEwAQ#v=onepage&q&f=false

A Course in Combinatorics 
J. H. van Lint, R. M. Wilson 
Cambridge University Press 
ISBN 0 521 00601 5

來源

2010-10-27 01:33:29

下面的網站也有一些非常酷的動畫，可以幫助你理解圖算法：http：//www.cs.sunysb。edu /〜skiena/combinatorica /動畫/ – 2010-10-27 01:35:23

我從來沒有看過combinatorics，所以我的興趣非常高。但是，它似乎沒有包含任何代碼正確的？ – jlv 2010-10-27 01:38:41

jlv：沒錯，這本書沒有代碼。然而，這是一本用於學習圖結構背後的數學的好書，可以應用於算法。我不會提到它，但它只是一本很棒的書。我不能*不提及它。 :) – 2010-10-28 03:15:22

我建議，當你學習任何算法則並不認爲它編碼的。算法是完全數學的，你必須對他們持相同的態度。當你學習像Graph Spanner算法之類的東西時，不要考慮如何編碼它如何表示它們。首先明白爲什麼算法是重要的和不重要的。然後嘗試一些非常小的解決方案並比較它們的複雜性。接下來看看最佳解決方案是怎樣的，並嘗試推導它們的屬性。使用紙和筆而不是IDE，嘗試派生並證明引號等。最後，看看如何編寫僞代碼來解決問題。如果你做了這些事情，那麼你會發展與算法的親密關係，然後你會發現它是更容易解決它們，因爲那時你不認爲在編碼時，爲什麼我這樣做。

不幸的是，由於對程序員的巨大需求，現在的程序員不是數學家，他們在解決新問題時會遇到問題。早期的程序員，如Don Knuth，Mcarthy是數學家和優秀的研究人員。因此，與計算機科學家相比，程序員現在是一個相對便宜的單詞。

來源

2012-07-14 18:05:37

OTOH我個人發現實現一個算法（之前沒有看到任何僞代碼），並使用該實現驗證了我完全理解該算法的工作原理。 – 2013-11-17 21:59:01

@MarkusUnterwaditzer - 真的，這是一個很棒的練習。請注意，儘管如此，很容易陷入糟糕的解決方案。如果你已經達到了一個看起來不合適的地步，那麼看看僞代碼是值得的。 – Ben 2014-02-19 20:19:47

Bellman-Ford算法：從源到即使-eve邊緣權重（未循環）在加權有向圖的所有其他節點最短路徑。比Dijsktra慢但多才多藝。 複雜度：O（| V | | E |）

BFS：查找路徑從一個給定的頂點到在未加權未向圖的其他節點。 複雜度：O（| V | + | E |）。當您知道前面的頂點並使用適當的數據結構i時，速度會更快。ËFIFO闕搞清楚可以降低到ö這已經比複雜處理的頂點（| V |）

DFS：搜索由源到其他節點的最短路徑。在樹和圖中。圖表可能包含循環，這意味着節點可能會一次又一次被訪問。所以我們可以使用布爾數組來跟蹤訪問節點。否則算法不會停止。它更多地越過越深，越遠到達樹的末端。 複雜度：O（| V | + | E |）。和複雜度：O（| V |）存儲頂點的空間。

Floyed Warshal算法： 查找定向未加權的曲線圖與+前夕，-eve（未循環）邊緣權重的所有對的最短路徑。但它並不返回路徑的細節。它可以用來檢測圖中的重量週期。當它找到一個它終止。它比較每對頂點之間所有可能的路徑圖。所以它採用動態方法而不是貪婪的方法。 複雜度：O（| V^3 |）

約翰遜的算法：發現在向加權稀疏圖所有對的最短路徑時邊緣權重是+前夕，-eve但不-eve週期。它首先使用貝爾福特算法從原始圖形計算變換圖。它消除了重量的邊緣。然後應用Dijkstra來查找路徑。 複雜度：O（V^2登錄V + VE）

Dijkstra算法： 該算法不的原始版本使用優先闕所以複雜度爲O（| V^2 |）但較新版本使用這種數據結構，因此複雜性變爲O（E + V log V）。並且它是更快的單源最短路徑算法。它通過給被訪問節點分配一個臨時權重，對被訪問節點的未訪問節點分配一個無窮大來查找所有未被訪問的邊，並以最小權重選擇。並將其添加到路徑集。

Krushkal's算法：找到MST，在MST中找到一個可能權重最小的邊，它連接了無向圖的加權圖上森林中的任意兩棵樹。這是貪婪算法。它也發現最小生成森林。 複雜度：O（E日誌V）

Prim算法：它發現形成上未定向，加權圖樹邊緣的子集。但不能像Krushkal算法那樣找到MS Forest。

Brouvka的算法：這個算法的問題是權重在圖中應該是唯一的。它通過檢查每個頂點然後以較小的重量來找到MST。該算法本質上是並行的，但不比Prim算法快。

與Krushkal算法一樣複雜。

來源

2015-08-04 06:53:27

回答

相關問題