?知識點
?引入
?圖的定義和相關(guān)術(shù)語
?圖的實現(xiàn)
?廣度優(yōu)先搜索
?深度優(yōu)先搜索
最短路徑問題：?
? ?
? ? ?
?還有其他前往金門大橋的路線，但它們更遠(yuǎn)（需要四步）。這個算法發(fā)現(xiàn)，前往金門大橋的最短路徑需要三步。
?這種問題被稱為最短路徑問題（shortest-path problem）。
?生活中經(jīng)常要找出最短路徑，這可能是前往朋友家的最短路徑，也可能是國際象棋中把對方將死的最少步數(shù)。
?解決最短路徑問題的算法被稱為廣度優(yōu)先(breadth-first search,BFS)搜索。
圖的定義
標(biāo)準(zhǔn)定義：在數(shù)學(xué)中，圖是描述于一組對象的結(jié)構(gòu)，其中某些對象對在某種意義上是“相關(guān)的”。這些對象對應(yīng)于稱為頂點的數(shù)學(xué)抽象（也稱為節(jié)點或點），并且每個相關(guān)的頂點對都稱為邊（也稱為鏈接或線）。通常，圖形以圖解形式描繪為頂點的一組點或環(huán)，并通過邊的線或曲線連接。
?二元組的定義: 圖G是一個有序二元組(V,E)，其中V稱為頂集(Vertices Set)，E稱為邊集(Edges set)，E與V不相交。它們亦可寫成V(G)和E(G)。其中，頂集的元素被稱為頂點(Vertex)，邊集的元素被稱為邊(edge)。E的元素都是二元組，用(x,y)表示，其中x,y∈V。
?三元組的定義: 圖G是指一個三元組(V,E,I)，其中V稱為頂集，E稱為邊集，E與V不相交；I稱為關(guān)聯(lián)函數(shù)，I將E中的每一個元素映射到V。如果e被映射到(u,v)，那么稱邊e連接頂點u,v，而u,v則稱作e的端點，u,v此時關(guān)于e相鄰。同時，若兩條邊i,j有一個公共頂點u，則稱i,j關(guān)于u相鄰。
圖：Graph=(V,E)
V：頂點(數(shù)據(jù)元素)的有窮非空集合；
E：邊的有窮集合。
無向圖：每條邊都是無方向的
有向圖：每條邊都是有方向的
一個是無向圖一個是有向圖?
完全圖：任意兩個點都有一條邊相連
?n(n-1)/2 條邊? ? ? ? ? ? ? ? ? ?n(n-1) 條邊
?
稀疏圖：有很少邊或弧的圖。
稠密圖：有較多邊或弧的圖。
權(quán)和網(wǎng)：圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。帶權(quán)的圖稱為網(wǎng)。
鄰接：有邊/弧相連的兩個頂點之間的關(guān)系。存在(vi, vj)，則稱vi和vj互為鄰接點；
存在<vi, vj>，則稱vi鄰接到vj，vj鄰接于vi
關(guān)聯(lián)(依附)：邊/弧與頂點之間的關(guān)系。
存在(vi, vj)/ <vi, vj>，則稱該邊/弧關(guān)聯(lián)于vi和vj
頂點的度：與該頂點相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)
在有向圖中, 頂點的度等于該頂點的入度與出度之和。
頂點v 的入度：是以v 為終點的有向邊的條數(shù), 記作ID(v)
頂點v 的出度：是以v 為始點的有向邊的條數(shù), 記作OD(v)
當(dāng)有向圖中僅1個頂點的入度為0,其余頂點的入度均為1，此時是何形狀？
是樹！而且是一棵有向樹！
路徑：接續(xù)的邊構(gòu)成的頂點序列。
路徑長度：路徑上邊或弧的數(shù)目/權(quán)值之和。（有兩種可能，弧或者邊）
回路(環(huán))：第一個頂點和最后一個頂點相同的路徑。
簡單路徑：除路徑起點和終點可以相同外，其余頂點均不相同的路徑。
簡單回路(簡單環(huán))：除路徑起點和終點相同外，其余頂點均不相同的路徑。
連通圖（強連通圖）：在無（有）向圖G=( V, {E} )中，若對任何兩個頂點v、u 都存在從v 到u 的路徑，則稱G是連通圖（強連通圖）。
?子圖：
設(shè)有兩個圖G=（V，{E}）、G1=（V1，{E1}），若V1εV，E1 εE，則稱G1是G的子圖。例:(b)、(c) 是(a) 的子圖：
連通分量（強連通分量）
?無向圖G 的極大連通子圖稱為G的連通分量。
極大連通子圖意思是：該子圖是G 連通子圖，將G 的任何不在該子圖中的頂點加入，子圖不再連通。
?
?
?圖的遍歷
1遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。
2遍歷實質(zhì)：找每個頂點的鄰接點的過程
3圖的特點：圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。
圖常用的遍歷：
?深度優(yōu)先搜索
?廣度優(yōu)先搜索
?廣度優(yōu)先搜索
?廣度優(yōu)先Breadth-First-Search(BFS)搜索是一種用于圖的查找算法，可幫助回答兩類問題。
?第一類問題：從節(jié)點A出發(fā)，有前往節(jié)點B的路徑嗎？（能否連通）
?第二類問題：從節(jié)點A出發(fā)，前往節(jié)點B的哪條路徑最短？（最短路徑問題）
?前面計算從雙子峰前往金門大橋的最短路徑，這個問題屬于第二類問題：哪條路徑最短。
?
?第一類問題：先找自己連通的，再找自己連通的連通的
?回答第二類問題：朋友是一度關(guān)系，朋友的朋友是二度關(guān)系。一度關(guān)系勝過二度關(guān)系，二度關(guān)系勝過三度關(guān)系，以此類推。
??廣度優(yōu)先搜索先在一度關(guān)系中查找，再在二度關(guān)系中查找。
?因此找到的是關(guān)系最近的芒果銷售商。廣度優(yōu)先搜索不僅查找從A到B的路徑，而且找到的是最短的路徑。
?注意，只有按添加順序查找時，才能實現(xiàn)這樣的目的。
?有一個可實現(xiàn)這種按添加順序檢查的數(shù)據(jù)結(jié)構(gòu)，那就是隊列（queue）。
用隊列實現(xiàn)：廣度優(yōu)先搜索找賣菠蘿的朋友（一個入隊一個出隊）
??隊列是一種先進(jìn)先出（First In First Out，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu)，而棧是一種后進(jìn)先出（Last In First Out，LIFO）的數(shù)據(jù)結(jié)構(gòu)。
?知道隊列的工作原理，就可以實現(xiàn)廣度優(yōu)先搜索
具體代碼實現(xiàn)
?
?
??Peggy既是Alice的朋友又是Bob的朋友，因此她將被加入隊列兩次：一次是在添加Alice的朋友時，另一次是在添加Bob的朋友時。因此，搜索隊列將包含兩個Peggy。
??但你只需檢查Peggy一次，看她是不是芒果銷售商。如果你檢查兩次，就做了無用功。
?因此，檢查完一個人后，應(yīng)將其標(biāo)記為已檢查，且不再檢查他。
?否則就可能會導(dǎo)致無限循環(huán)。
檢查一個人之前，要確認(rèn)之前沒檢查過他。
?可使用一個列表來記錄檢查過的人。
?廣度優(yōu)先搜索的時間
?運行時間
?若在整個人際關(guān)系網(wǎng)中搜索芒果銷售商，就意味著你將沿每條邊前行，因此運行時間至少為O(邊數(shù))。
?你還使用了一個隊列，其中包含要檢查的每個人。將一個人添加到隊列需要的時間是固定的，即為O(1)，因此對每個人都這樣做需要的總時間為O(人數(shù))。
?所以，廣度優(yōu)先搜索的運行時間為O(人數(shù)+ 邊數(shù))，這通常寫作O(V + E)，其中V為頂點（vertice）數(shù)，E為邊數(shù)。
廣度優(yōu)先搜索的基本思想文章來源：http://www.zghlxwxcb.cn/news/detail-523236.html
基本思想：——仿樹的層次遍歷過程文章來源地址http://www.zghlxwxcb.cn/news/detail-523236.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)圖論的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
