本文實例講述了Python數據結構與算法之圖結構(Graph)。分享給大家供大家參考，具體如下：

圖結構(Graph)——算法學中最強大的框架之一。樹結構只是圖的一種特殊情況。

如果我們可將自己的工作詮釋成一個圖問題的話，那么該問題至少已經接近解決方案了。而我們我們的問題實例可以用樹結構(tree)來詮釋，那么我們基本上已經擁有了一個真正有效的解決方案了。

鄰接表及加權鄰接字典

對于圖結構的實現來說，最直觀的方式之一就是使用鄰接列表。基本上就是針對每個節點設置一個鄰接列表。下面我們來實現一個最簡單的：假設我們現有 n 個節點，編號分別為 0, …, n-1.

節點當然可以是任何對象，可被賦予任何標簽或名稱。但使用 0, …, n-1 區間內的整數來實現的話，會簡單許多。因為如果我們能用數字來代表節點，我們索引起來顯然要方便許多。

然后，每個鄰接(鄰居)列表都只是一個數字列表，我們可以將它們編入一個大小為 n 的主列表，并用節點編號對其進行索引。由于這些列表內的節點的順序是任意的，所以，實際上，我們是使用列表來實現鄰接集(adjacency sets)。這里之所以還是使用列表這個術語，主要是因為傳統。幸運的是，Python 本身就提供獨立的 set 類型。

我們以下圖為例，說明圖結構的各種表示方法(當我們在執行與圖相關的工作時，需要反復遵從一個主題思想，即一個圖的最佳表示方法應該取決于我們要用它來做什么)：

在圖論中，N(v) 代表的是 v 的鄰居節點集；

加權鄰接字典

使用 dict 類型來代替 set 或 list 來表示鄰接集。在 dict 類型中，每個鄰居節點都會有一個鍵和一個額外的值，用于表示與其鄰居節點(或出邊)之間的關聯性，如邊的權重。

客戶端調用：

鄰接矩陣

鄰接矩陣是圖的另一種表示方法，這種表示方法的主要不同在于，它不再列出每個節點的所有鄰居節點。

關于鄰接矩陣：

(1)主對角線為自己到自己，為0

(2)行和為出度

(3)列和為入度

希望本文所述對大家Python程序設計有所幫助。

原文鏈接：http://blog.csdn.net/lanchunhui/article/details/50954005

總結

以上是生活随笔為你收集整理的python define graph_Python数据结构与算法之图结构（Graph）实例分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。