有趣的圖(一)(55)
小朋友們好，大朋友們好！
我是貓妹，一名愛上Python編程的小學(xué)生。
和貓妹學(xué)Python，一起趣味學(xué)編程。
今日主題
咱們今天的內(nèi)容比較抽象，也比較有趣。
這里的圖是指計(jì)算機(jī)中的圖，確切地說，是一種數(shù)據(jù)結(jié)構(gòu)。
在解決實(shí)際問題時(shí)，經(jīng)常會(huì)用到。
我們舉個(gè)生活中的例子：
一個(gè)人要把大陸31個(gè)省會(huì)城市自駕游一遍，最短路徑是多少公里？
一個(gè)人能在一個(gè)省份只經(jīng)過一次的情況下把大陸31個(gè)省會(huì)城市自駕游一遍嗎？
今天的主題有：
圖的定義
圖的分類
圖的接口
圖的Python表示
圖的定義
圖G由兩個(gè)集合組成，頂點(diǎn)集合和邊集合。
一個(gè)由頂點(diǎn)(vertex)構(gòu)成的有窮非空集合和一個(gè)由邊(edge)構(gòu)成的有窮允空集合。
比如上圖：
頂點(diǎn)集合有：1,2,3,4,5,6,7
邊集合有：有10條，帶權(quán)值
比如上圖：
頂點(diǎn)結(jié)合有：0,1,2,3,4,5
邊集合有：共9條，不帶權(quán)值
圖的分類
圖根據(jù)邊是否有方向，分為有向圖和無向圖。
(a)為有向圖，(b)為無向圖
圖根據(jù)邊是否有權(quán)值，分為邊無權(quán)值的圖，邊有權(quán)值的圖。
如下圖：
節(jié)點(diǎn)的度
無向圖中結(jié)點(diǎn)的度：頂點(diǎn)引出的邊數(shù)和。
有向圖中結(jié)點(diǎn)的度：分為入度和出度。入度為指向該頂點(diǎn)的邊數(shù)和，出度為該頂點(diǎn)向外指向的邊數(shù)和。
圖的接口
addVertex(v)添加頂點(diǎn)
deleteVertex(v)刪除頂點(diǎn)
vertexes(v)獲取所有頂點(diǎn)
addEdge(v1,v2)添加一條邊
deleteEdge(v1,v2)刪除一條邊
edges()獲取所有邊
adjacent(v)獲取v的所有鄰接頂點(diǎn)
isEmpty()判斷圖是否為空
Python中的圖
可以使用Python自帶的列表、集合、字典來表示圖，也可以使用第三方庫(kù)networkx。
可以使用鄰接矩陣、鄰接列表、鄰接集合、鄰接加權(quán)字典來表示圖。%3CmxGraphModel%3E%3Croot%3E%3CmxCell%20id%3D%220%22%2F%3E%3CmxCell%20id%3D%221%22%20parent%3D%220%22%2F%3E%3CmxCell%20id%3D%222%22%20value%3D%22b%22%20style%3D%22ellipse%3BwhiteSpace%3Dwrap%3Bhtml%3D1%3Baspect%3Dfixed%3BfillColor%3D%2360a917%3BfontColor%3D%23ffffff%3BstrokeColor%3D%232D7600%3B%22%20vertex%3D%221%22%20parent%3D%221%22%3E%3CmxGeometry%20x%3D%22350%22%20y%3D%22130%22%20width%3D%2220%22%20height%3D%2220%22%20as%3D%22geometry%22%2F%3E%3C%2FmxCell%3E%3C%2Froot%3E%3C%2FmxGraphModel%3E
鄰接矩陣
設(shè)無向圖G=(V,E),其中頂點(diǎn)集V=v1,v2,…,vn，邊集 E=e1,e2,…,eε。用aij表示頂點(diǎn)vi與頂點(diǎn)vj之間的邊數(shù)，可能取值為0,1,2,…，稱所得矩陣A=A(G)=(aij)n×n為圖G的鄰接矩陣。
鄰接矩陣可以描述有向圖和無向圖。
鄰接矩陣的存儲(chǔ)特點(diǎn)：
（a）無向圖的鄰接矩陣是一個(gè)對(duì)稱矩陣，有向圖不一定是。
（b）鄰接矩陣所需的存儲(chǔ)空間值域只與頂點(diǎn)數(shù)有關(guān)系。
（c）用鄰接矩陣存儲(chǔ)圖，容易判斷兩個(gè)點(diǎn)之間是否有邊。
（d）如果一個(gè)有向圖的鄰接矩陣為三角矩陣（主對(duì)角線為0），則它的拓?fù)渑判蛞欢ù嬖凇?/p>
（e）小技巧：
無向圖：鄰接矩陣的第i行或者第i列的非零元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)Vi的度；
有向圖：鄰接矩陣的第i行的非零元素個(gè)數(shù)正好是第i個(gè)頂點(diǎn)Vi的出度，第i列非零元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)Vi的入度。
（f）鄰接矩陣也可以表示有權(quán)值的圖，此時(shí)單元格內(nèi)容是邊的權(quán)值。
上圖Python代碼參考：
鄰接矩陣的缺點(diǎn)：
當(dāng)結(jié)點(diǎn)很多，邊很少時(shí)，很多個(gè)0，浪費(fèi)空間。
尋找每個(gè)結(jié)點(diǎn)的鄰接頂點(diǎn)時(shí)，需要遍歷列表，稍有不便。
鄰接集合
只存儲(chǔ)有邊的數(shù)據(jù)，不存儲(chǔ)無邊的數(shù)據(jù)。
比如上圖中，和a相鄰的邊，只存儲(chǔ)ad和ae，只需要存儲(chǔ)和a相鄰的結(jié)點(diǎn)是d和e就可以了。
鄰接列表
和鄰接集合類似，只是將集合變?yōu)榱斜怼?br>
鄰接加權(quán)字典
可以使用鄰接加權(quán)字典表示有權(quán)值的圖。
好了，我們今天的學(xué)習(xí)就先到這里。
你學(xué)會(huì)了嗎？
好了，我們今天就學(xué)到這里吧！
如果遇到什么問題，咱們多多交流，共同解決。
我是貓妹，咱們下次見！
