建站
咨詢
售后
建站咨詢
新聞中心
圖結(jié)構(gòu)（graph）——算法學(xué)中最強(qiáng)大的框架之一。樹結(jié)構(gòu)只是圖的一種特殊情況。
創(chuàng)新互聯(lián)建站是一家專業(yè)提供復(fù)興企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站建設(shè)、做網(wǎng)站、HTML5建站、小程序制作等業(yè)務(wù)。10年已為復(fù)興眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計(jì)公司優(yōu)惠進(jìn)行中。
如果我們可將自己的工作詮釋成一個(gè)圖問題的話，那么該問題至少已經(jīng)接近解決方案了。而我們我們的問題實(shí)例可以用樹結(jié)構(gòu)（tree）來詮釋，那么我們基本上已經(jīng)擁有了一個(gè)真正有效的解決方案了。
鄰接表及加權(quán)鄰接字典
對(duì)于圖結(jié)構(gòu)的實(shí)現(xiàn)來說，最直觀的方式之一就是使用鄰接列表?；旧暇褪轻槍?duì)每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)鄰接列表。下面我們來實(shí)現(xiàn)一個(gè)最簡(jiǎn)單的：假設(shè)我們現(xiàn)有 n 個(gè)節(jié)點(diǎn)，編號(hào)分別為 0, …, n-1.
節(jié)點(diǎn)當(dāng)然可以是任何對(duì)象，可被賦予任何標(biāo)簽或名稱。但使用 0, …, n-1 區(qū)間內(nèi)的整數(shù)來實(shí)現(xiàn)的話，會(huì)簡(jiǎn)單許多。因?yàn)槿绻覀兡苡脭?shù)字來代表節(jié)點(diǎn)，我們索引起來顯然要方便許多。
然后，每個(gè)鄰接（鄰居）列表都只是一個(gè)數(shù)字列表，我們可以將它們編入一個(gè)大小為 n 的主列表，并用節(jié)點(diǎn)編號(hào)對(duì)其進(jìn)行索引。由于這些列表內(nèi)的節(jié)點(diǎn)的順序是任意的，所以，實(shí)際上，我們是使用列表來實(shí)現(xiàn)鄰接集（adjacency sets）。這里之所以還是使用列表這個(gè)術(shù)語，主要是因?yàn)閭鹘y(tǒng)。幸運(yùn)的是，python 本身就提供獨(dú)立的 set 類型。
相關(guān)推薦：《Python基礎(chǔ)教程》
我們以下圖為例，說明圖結(jié)構(gòu)的各種表示方法（當(dāng)我們?cè)趫?zhí)行與圖相關(guān)的工作時(shí)，需要反復(fù)遵從一個(gè)主題思想，即一個(gè)圖的最佳表示方法應(yīng)該取決于我們要用它來做什么）：
a, b, c, d, e, f, g, h = range(8)
N = [
{b, c, d, e, f},
{c, e},
9jloib9,
{e},
{f},
{c, g, h},
{f, h},
{f, g}
]在圖論中，N(v) 代表的是 v 的鄰居節(jié)點(diǎn)集；
>>> b in N[a] # neighborhood membership True >>> len(N[f]) # out-degree：出度 3
加權(quán)鄰接字典
使用 dict 類型來代替 set 或 list 來表示鄰接集。在 dict 類型中，每個(gè)鄰居節(jié)點(diǎn)都會(huì)有一個(gè)鍵和一個(gè)額外的值，用于表示與其鄰居節(jié)點(diǎn)（或出邊）之間的關(guān)聯(lián)性，如邊的權(quán)重。
a, b, c, d, e, f, g, h = range(8)
N = [
{b:2, c:1, d:3, e:9, f:4},
{c:4, e:4},
{d:8},
{e:7},
{f:5},
{c:2, g:2, h:2},
{f:1, h:6},
{f:9, g:8}
]客戶端調(diào)用：
>>> b in N[a] # neighborhood membership True >>> len(N[f]) # out-degree 3 >>> N[a][b] # Edge weight for (a, b) 2
鄰接矩陣
鄰接矩陣是圖的另一種表示方法，這種表示方法的主要不同在于，它不再列出每個(gè)節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)。
a, b, c, d, e, f, g, h = range(8) N =[ [0, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 1, 1, 0], ]
關(guān)于鄰接矩陣：
（1）主對(duì)角線為自己到自己，為0
（2）行和為出度
（3）列和為入度
網(wǎng)站標(biāo)題：創(chuàng)新互聯(lián)Python教程：pythongraph什么意思
當(dāng)前地址：http://www.5511xx.com/article/dpphedp.html
