最短路徑

現(xiàn)實(shí)場(chǎng)景

1、一批貨從北京到廣州的的最快，或最省錢的走法。?
把路線中各城市當(dāng)作圖的頂點(diǎn)，各城市之間的花費(fèi)時(shí)間，或金錢當(dāng)作邊的權(quán)重，求兩點(diǎn)之間的最短路徑。?
2、在城市群中建一個(gè)倉(cāng)儲(chǔ)基地，建在什么位置可以讓各個(gè)城市的送貨速度都比較快。?
同1，把各城市間的送貨速度當(dāng)作邊的權(quán)重，求倉(cāng)儲(chǔ)基地到各城市間的最短路徑。

算法

1、Dijkstra，單源最短路徑。?
2、Floyd，兩點(diǎn)最短路徑。?
參考鏈接：http://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

社區(qū)發(fā)現(xiàn)

現(xiàn)實(shí)場(chǎng)景

用于社交網(wǎng)絡(luò)中的社區(qū)（或話題）發(fā)現(xiàn)，基本特點(diǎn)是，社區(qū)之間聯(lián)系稀疏，社區(qū)內(nèi)部聯(lián)系緊密。如，給定新浪微博的用戶關(guān)系數(shù)據(jù)，找出其中的的社區(qū)，以及核心節(jié)點(diǎn)。

算法

標(biāo)簽傳播、主要特征向量、多層模塊度、隨機(jī)游走、邊介數(shù)等幾個(gè)系列算法。

各算法的優(yōu)劣，有一個(gè)評(píng)價(jià)體系，即計(jì)算其 Modularity Measure(模塊化度量值）。?
具體的算法介紹，及Modularity Measure值計(jì)算，可以參考這里：http://blog.csdn.net/itplus/article/details/9286905?
關(guān)于Fast Unfolding更詳細(xì)的介紹，可以參考這里：http://blog.csdn.net/google19890102/article/details/48660239

網(wǎng)絡(luò)評(píng)價(jià)

現(xiàn)實(shí)場(chǎng)景

現(xiàn)實(shí)中存在各種的網(wǎng)絡(luò)：社區(qū)聚集、好友關(guān)系、電力網(wǎng)、交通網(wǎng)等，網(wǎng)絡(luò)特點(diǎn)各不相同，計(jì)算機(jī)科學(xué)上，把這些現(xiàn)實(shí)網(wǎng)絡(luò)劃分為隨機(jī)網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)、規(guī)則網(wǎng)絡(luò)、無(wú)標(biāo)度網(wǎng)絡(luò)等多種抽象的網(wǎng)絡(luò)模型，用網(wǎng)絡(luò)模型去解釋現(xiàn)實(shí)網(wǎng)絡(luò)。并定義了一套可量化的標(biāo)準(zhǔn)特征來(lái)描述各種網(wǎng)絡(luò)模型。

概念

1、平均路徑長(zhǎng)度。路徑長(zhǎng)度，是指網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)之間的最短路徑。平均路徑長(zhǎng)度是指所有節(jié)點(diǎn)之間的平均最短距離。?
2、網(wǎng)絡(luò)直徑。網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間的最大路徑長(zhǎng)度。?
3、度分布。度，是指網(wǎng)絡(luò)結(jié)構(gòu)中與某節(jié)點(diǎn)相連接的邊的數(shù)目為該節(jié)點(diǎn)的度。社交網(wǎng)絡(luò)中度數(shù)較多的節(jié)點(diǎn)通常是公眾人物。?
網(wǎng)絡(luò)中各個(gè)的節(jié)點(diǎn)度的分布情況就為度分布，如泊松分布、二項(xiàng)分布等。?
4、介數(shù)。節(jié)點(diǎn)的介數(shù)，指經(jīng)過(guò)該節(jié)點(diǎn)的最短路徑占整個(gè)網(wǎng)絡(luò)所有最短路徑的比例。如，社交網(wǎng)絡(luò)中的某些關(guān)鍵人物。?
5、接近中心度。一個(gè)節(jié)點(diǎn)通過(guò)最短路徑到達(dá)其它節(jié)點(diǎn)的難易程度。對(duì)于網(wǎng)絡(luò)中的邊緣節(jié)點(diǎn)，其接近中心度會(huì)比較小。如，偏遠(yuǎn)城市，社交網(wǎng)絡(luò)中的非主流人物。?
6、Clustering coefficient（聚集系數(shù)）。主要衡量一個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)之間的連接情況，鄰節(jié)點(diǎn)之間連接越多，聚集系數(shù)越大。?
7、網(wǎng)絡(luò)密度。網(wǎng)絡(luò)中節(jié)點(diǎn)固定情況下，邊數(shù)量越多，則密度越大，即節(jié)點(diǎn)之間聯(lián)系更緊密。?
8、互惠指數(shù)。即有向網(wǎng)絡(luò)中的無(wú)向程度。

K-Core

現(xiàn)實(shí)場(chǎng)景

社交網(wǎng)絡(luò)中，有一批KOL存在，他們的影響力遠(yuǎn)超普通大眾。

算法

關(guān)于K-Core的詳細(xì)解釋，及其算法實(shí)現(xiàn)，可以參考這里：網(wǎng)絡(luò)節(jié)點(diǎn)度、H指數(shù)與核數(shù)之間的優(yōu)美關(guān)系（http://blog.sciencenet.cn/blog-3075-950475.html）

二分圖匹配

現(xiàn)實(shí)場(chǎng)景

1、通過(guò)數(shù)代人的努力，你終于趕上了剩男剩女的大潮，假設(shè)你是一位光榮的新世紀(jì)媒人，在你的手上有N個(gè)剩男，M個(gè)剩女，每個(gè)人都可能對(duì)多名異性有好感，請(qǐng)為他們兩兩配對(duì)，最大程度減少剩男剩女個(gè)數(shù)。?
2、有一些員工要完成一些任務(wù)。各個(gè)員工完成不同任務(wù)所花費(fèi)的時(shí)間都不同。每個(gè)員工只分配一項(xiàng)任務(wù)。每項(xiàng)任務(wù)只被分配給一個(gè)員工。怎樣分配員工與任務(wù)以使所花費(fèi)的時(shí)間最少？

算法

1、匈牙利算法?
2、任務(wù)分配問(wèn)題一般可以在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化成最大流量問(wèn)題（Maximum Flow Problem）

匈牙利算法參考文章：http://blog.csdn.net/dark_scope/article/details/8880547

二分圖匹配問(wèn)題轉(zhuǎn)最大流問(wèn)題的方法可參考這里：?
http://blog.csdn.net/caipeichao2/article/details/35306659

最小費(fèi)用、最大流

現(xiàn)實(shí)場(chǎng)景

1、從城市A到城市B之間運(yùn)輸一批貨物，中間路過(guò)多個(gè)城市，有多條路線可供選擇，兩兩城市之間的運(yùn)輸費(fèi)用不等，找出一條費(fèi)用最小的路線。?
2、把一批快遞經(jīng)由鐵路由城市A運(yùn)到城市B，中間路過(guò)多個(gè)城市。在做任意兩個(gè)城市間的鐵路線上可運(yùn)送的物資數(shù)量是有限的，我們要考慮使鐵路線承載量最大，不讓鐵路資源閑置，同時(shí)讓快遞運(yùn)輸時(shí)經(jīng)過(guò)更多的城市，以承攬更多快遞業(yè)務(wù)。如果把鐵路網(wǎng)上的車站看作是圖的頂點(diǎn)，兩個(gè)車站間的鐵路線看作是圖的邊，把任意兩城市間的鐵路線上的允許最大運(yùn)送量稱為容量。這就是一個(gè)經(jīng)典的求網(wǎng)絡(luò)最大流問(wèn)題。

概念

1、邊權(quán)重的意義。不同場(chǎng)景下，每條邊的值有不同的意義，問(wèn)題1中，邊的權(quán)重為費(fèi)用，問(wèn)題2中，邊的權(quán)重為剩余容量。?
2、增廣路徑。在圖中，可能存在多條從源點(diǎn)到目標(biāo)點(diǎn)的可行路徑，每一條都是一條增廣路徑。最小費(fèi)用、最大流問(wèn)題就是找到多條增廣路徑中滿足最小費(fèi)用、最大流條件的一條。

算法

1、最小費(fèi)用問(wèn)題可轉(zhuǎn)化為求最短路徑問(wèn)題。?
2、Edmond-Karp算法。?
可參考文檔：http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html?
3、Ford-Fulkerson算法。?
可參考文檔：http://www.cnblogs.com/kuangbin/archive/2011/07/26/2117636.html

最大連通子圖

現(xiàn)實(shí)場(chǎng)景

1、計(jì)算機(jī)網(wǎng)絡(luò)中的病毒通常會(huì)基于一種病毒存在多種變種病毒，變種病毒與原病毒之間大部分代碼相似。因此，把兩種病毒之間的函數(shù)調(diào)用關(guān)系用圖表示出來(lái)，分析其最大連通子圖是否相似，就可以判斷是否變種病毒。?
2、圖像分割中，尋找圖像的最大連通域。

概念

最大連通子圖。是指把圖劃分為N個(gè)子圖后，子圖內(nèi)所有節(jié)點(diǎn)相連，子圖間沒(méi)有節(jié)點(diǎn)相連。這N個(gè)子圖就是原圖的最大連通子圖。

歐拉回路

現(xiàn)實(shí)場(chǎng)景

1、七橋問(wèn)題。?
2、去北京動(dòng)物園瀏覽，能否設(shè)計(jì)一條這樣的路線：既可以游遍所有景點(diǎn)，又不走重復(fù)路。

概念

1、歐拉回路。是指，通過(guò)圖（無(wú)向圖或有向圖）中所有邊一次且僅一次行遍圖中所有頂點(diǎn)的通路(回路)稱為歐拉通路(回路)。?
2、滿足特定條件的圖才能稱為歐拉圖。

算法

Fleury算法

哈密頓回路

現(xiàn)實(shí)場(chǎng)景

導(dǎo)游帶團(tuán)北京一日游遍，需要設(shè)計(jì)一條路線，可以走遍所有景點(diǎn)，且只走一次。

概念

1、哈密頓回路。在一個(gè)圖中，由指定的起點(diǎn)前往指定的終點(diǎn)，途中經(jīng)過(guò)所有其他節(jié)點(diǎn)且只經(jīng)過(guò)一次。?
2、哈密頓回路并不一定存在。?
3、屬NP完全問(wèn)題，難以在有效時(shí)間內(nèi)找到解決方案。

最小生成樹(shù)

現(xiàn)實(shí)場(chǎng)景

1、在電路設(shè)計(jì)中，常常需要把一些電子元件的插腳用電線連接起來(lái)。如果每根電線連接兩個(gè)插腳，把所有n個(gè)插腳連接起來(lái)，只要用n-1根電線就可以了。在所有的連接方案中，我們通常對(duì)電線總長(zhǎng)度最小的連接方案感興趣。?
2、要在n個(gè)城市之間鋪設(shè)光纜，主要目標(biāo)是要使這 n 個(gè)城市的任意兩個(gè)之間都可以通信，找出一條使用最短的光纖連通這些城市的鋪設(shè)方法。

算法

1、Prim算法?
2、Kruskal算法

拓?fù)渑判?/h2>

現(xiàn)實(shí)場(chǎng)景

1、一個(gè)大工程，通常由多個(gè)任務(wù)組成，這些子工程之間有的有依賴關(guān)系，有的沒(méi)有，假設(shè)同時(shí)只能做一個(gè)任務(wù)，請(qǐng)排出一個(gè)順序來(lái)。?
2、一個(gè)計(jì)算機(jī)專業(yè)的學(xué)生必須完成一系列課程才能畢業(yè)。如學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》課程就必須安排在學(xué)完它的兩門先修課程《離散數(shù)學(xué)》和《算法語(yǔ)言》之后。學(xué)習(xí)《高等數(shù)學(xué)》課程則可以隨時(shí)安排，因?yàn)樗腔A(chǔ)課程，沒(méi)有先修課。

概念

1、有向無(wú)環(huán)圖（DAG）。?
2、AOV表示法。圖的節(jié)點(diǎn)表示任務(wù)，有向邊表示先后順序，最終形成的是一個(gè)有向無(wú)環(huán)圖，才能進(jìn)行拓?fù)渑判颉?/p>

算法

1、Kahn算法?
2、DFS

關(guān)鍵路徑

現(xiàn)實(shí)場(chǎng)景

一個(gè)工程如何優(yōu)化任務(wù)的安排，才能最大程度縮短工期？

概念

1、在拓?fù)渑判蛑?#xff0c;才能進(jìn)行關(guān)鍵路徑的優(yōu)化。?
2、AOE表示法。用圖的節(jié)點(diǎn)表示任務(wù)，有向邊表示任務(wù)的先后順序，邊的權(quán)重表示任務(wù)所花時(shí)間。?
3、找到兩個(gè)關(guān)鍵點(diǎn)進(jìn)行優(yōu)化：完成整項(xiàng)工程至少需要多少時(shí)間？哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的常见算法及问题场景——图的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。