/?寫(xiě)在前面的話(huà)?/

蘇世機(jī)試小課堂，考研機(jī)試不再慌！

公主號(hào):蘇世學(xué)社考研 蘇世計(jì)算機(jī)考研

圖是計(jì)算機(jī)科學(xué)中常用的一類(lèi)數(shù)據(jù)結(jié)構(gòu)，有關(guān)圖的算法也是計(jì)算機(jī)科學(xué)中重要的圖和圖算法。有許多有趣的計(jì)算問(wèn)題都是用圖來(lái)定義的。在本文中，要介紹一些更為重要的圖和圖算法。

1.并查集

? 1.1 概念

并查集是一種樹(shù)形的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不交集的合并及查詢(xún)問(wèn)題。聯(lián)合-查找算法定義了兩個(gè)用于此數(shù)據(jù)結(jié)構(gòu)的操作：

Find：確定元素屬于哪一個(gè)集合。它可以被用來(lái)確定兩個(gè)元素是否屬于同一個(gè)子集。

Union：將兩個(gè)子集合并成同一個(gè)集合。

并查集主要運(yùn)用在合并元素以及查詢(xún)兩個(gè)元素是否在同一集合的問(wèn)題。

? 1.2? 典型例題

題目描述

今天是小蘇的生日，小蘇邀請(qǐng)了很多朋友，現(xiàn)在該吃晚飯了,小蘇想知道他至少需要多少?gòu)堊雷?。你必須注意到并不是所有的朋友都認(rèn)識(shí)對(duì)方，而且所有的朋友都不想和陌生人待在一起。這個(gè)問(wèn)題的一個(gè)重要規(guī)則是如果我告訴你A認(rèn)識(shí)B, B認(rèn)識(shí)C，這意味著A, B, C互相認(rèn)識(shí)，所以它們可以在一個(gè)表中。例如:如果我告訴你A認(rèn)識(shí)B, B認(rèn)識(shí)C, D認(rèn)識(shí)E，那么A, B, C可以在一個(gè)表中，D, E必須在另一個(gè)表中，小蘇至少需要兩張表。

輸入描述

輸入以一個(gè)整數(shù)T(1<=T<=25)開(kāi)始，它表示測(cè)試用例的數(shù)量。然后是T組測(cè)試用例，每個(gè)測(cè)試用例都以?xún)蓚€(gè)整數(shù)N和M開(kāi)始(1<=N,M<=1000)。N表示朋友的數(shù)量，朋友的數(shù)量從1到N進(jìn)行標(biāo)記，然后是M行。每一行由兩個(gè)整數(shù)A和B(A!=B)組成，這意味著朋友A和朋友B互相認(rèn)識(shí)。兩種情況之間會(huì)有一條空行。

輸出描述

對(duì)于每個(gè)測(cè)試用例，只輸出小蘇至少需要多少個(gè)表，不要打印任何空格。

思路

將認(rèn)識(shí)的人歸到一個(gè)集合里，然后計(jì)算集合的數(shù)量，用并查集即可。

代碼實(shí)現(xiàn)

2.最小生成樹(shù)

? 2.1?概念

給定一張邊帶權(quán)的無(wú)向圖G=(V,E)，其中V表示圖中點(diǎn)的集合，E表示圖中邊的集合，n=|V|，m=|E|。由V中的全部n個(gè)頂點(diǎn)和E中的n-1條邊構(gòu)成的無(wú)向連通圖被稱(chēng)為G的一棵生成樹(shù)，其中邊的權(quán)值之和最小的生成樹(shù)被稱(chēng)為無(wú)向圖G的最小生成樹(shù)。

簡(jiǎn)而言之：

一棵樹(shù)：無(wú)回路，V個(gè)頂點(diǎn)V-1條邊。

生成樹(shù)：包含全部頂點(diǎn)，V-1條邊都在圖里

邊的權(quán)重最小。

? 2.2算法介紹

（1）prim算法

①步驟

1.用兩個(gè)集合A{},B{}分別表示找到的點(diǎn)集合和未找到的點(diǎn)集。

2.以A中的點(diǎn)為起點(diǎn)a，在B中找一個(gè)點(diǎn)為終點(diǎn)b，這兩個(gè)點(diǎn)構(gòu)成的邊(a,b)的權(quán)值是其余邊中最小的，將b加入集合A。

3.重復(fù)上述步驟2’，直至B中的點(diǎn)集為空，A中的點(diǎn)集為滿(mǎn)。

（2）圖文表示

先將源點(diǎn)0加入集合A，然后遍歷A中的點(diǎn)外接的所有邊，找到最小的那條邊

發(fā)現(xiàn)最小邊對(duì)應(yīng)的集合B里面的點(diǎn)是2，將結(jié)點(diǎn)2加入集合A中，然后繼續(xù)找長(zhǎng)度最小的邊

發(fā)現(xiàn)集合B里的結(jié)點(diǎn)3離A最近，將它加入到集合A里，繼續(xù)找

發(fā)現(xiàn)結(jié)點(diǎn)1到集合A的距離為13，將結(jié)點(diǎn)1加入A中，繼續(xù)找

發(fā)現(xiàn)節(jié)點(diǎn)4到1的距離為13最短，此時(shí)發(fā)現(xiàn)所有頂點(diǎn)已經(jīng)都在集合A里面了，滿(mǎn)足題目條件，終止尋找

經(jīng)典例題

題目描述

某佛大學(xué)要進(jìn)行用電線(xiàn)路改造，現(xiàn)在校長(zhǎng)要求設(shè)計(jì)師設(shè)計(jì)出一種布線(xiàn)方式，該布線(xiàn)方式需要滿(mǎn)足以下條件：
1、把所有的樓都供上電。
2、所用電線(xiàn)花費(fèi)最少。

輸入

第一行是一個(gè)整數(shù)n表示有n組測(cè)試數(shù)據(jù)。(n<5)?
每組測(cè)試數(shù)據(jù)的第一行是兩個(gè)整數(shù)v,e. v表示學(xué)校里樓的總個(gè)數(shù)(v<=500) 隨后的e行里，每行有三個(gè)整數(shù)a,b,c表示a與b之間如果建鋪設(shè)線(xiàn)路花費(fèi)為c(c<=100)。（哪兩棟樓間如果沒(méi)有指明花費(fèi)，則表示這兩棟樓直接連通需要費(fèi)用太大或者不可能連通） 隨后的1行里，有v個(gè)整數(shù),其中第i個(gè)數(shù)表示從第i號(hào)樓接線(xiàn)到外界供電設(shè)施所需要的費(fèi)用。( 0<e<v*(v-1)/2 ) （樓的編號(hào)從1開(kāi)始），由于安全問(wèn)題，只能選擇一個(gè)樓連接到外界供電設(shè)備。
數(shù)據(jù)保證至少存在一種方案滿(mǎn)足要求。

輸出

每組測(cè)試數(shù)據(jù)輸出一個(gè)正整數(shù),表示鋪設(shè)滿(mǎn)足校長(zhǎng)要求的線(xiàn)路的最小花費(fèi)。

樣例輸入

1

4 6

1 2 10

2 3 10

3 1 10

1 4 1

2 4 1

3 4 1

1 3 5 6

樣例輸出

4

示例代碼

3.Kruskal算法

? 3.1?思想和步驟

從prim算法我們可以知道，它是從“頂點(diǎn)”這個(gè)角度來(lái)思考的，然后采用“貪心思想”，一步一步擴(kuò)大化，最后形成總體最優(yōu)解。而Kruskal是站在“邊”這個(gè)角度來(lái)考慮的，使用并查集，先初始化為孤立集合，再按權(quán)值大小排序，把權(quán)值小的邊加入集合，直到點(diǎn)全部在集合中。

? 3.2圖文表示

初始化，選擇結(jié)點(diǎn)0作為原點(diǎn)

找到最小的邊權(quán)值為2，將它加入到集合中

接著找到最小的邊權(quán)值為4將加入到集合中

同樣權(quán)值為4的邊因?yàn)閮蓚€(gè)結(jié)點(diǎn)都在集合里了，所以選擇下一個(gè)最小邊權(quán)值為6，加入到集合中

還有權(quán)值為6的邊，繼續(xù)加入集合中

邊數(shù)已經(jīng)是頂點(diǎn)數(shù)-1了，剩下的邊連接的兩個(gè)頂點(diǎn)都在集合中，所以不用加入了，流程結(jié)束。

代碼實(shí)現(xiàn)

4.最短路徑

? 4.1概念

最短路徑問(wèn)題旨在尋找圖中兩結(jié)點(diǎn)的最短路徑。算法具體形式包括：

（1）確定起點(diǎn)的最短路徑問(wèn)題-即已知起始結(jié)點(diǎn)，求最短路徑的問(wèn)題。

（2）確定終點(diǎn)的最短路徑問(wèn)題 - 與確定起點(diǎn)的問(wèn)題相反，該問(wèn)題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問(wèn)題。在無(wú)向圖中該問(wèn)題與確定起點(diǎn)的問(wèn)題完全等同，在有向圖中該問(wèn)題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問(wèn)題。

（3）確定起點(diǎn)終點(diǎn)的最短路徑問(wèn)題 - 即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。

（4）全局最短路徑問(wèn)題 - 求圖中所有的最短路徑。

Dijkstra算法

?

4.2概念

Dijkstra算法（迪杰斯特拉）是典型的最短路徑路由算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低?？梢杂枚褍?yōu)化。

?4.3實(shí)現(xiàn)步驟

①將所有的頂點(diǎn)分為兩個(gè)部分，已知最短路徑的頂點(diǎn)集合P和未知的頂點(diǎn)集合Q，初始時(shí)，P中只有一個(gè)源頂點(diǎn)1號(hào)。這里用book數(shù)組來(lái)標(biāo)記頂點(diǎn)是否在P中，1表示在P中，0表示在Q中。

dis數(shù)組來(lái)記錄最短路徑，數(shù)組下標(biāo)來(lái)表示頂點(diǎn)的下標(biāo)。

設(shè)置源點(diǎn)1到到其他頂點(diǎn)的路徑值，放置到dis中。

②在dis中找到源點(diǎn)s到其他頂點(diǎn)的最短路徑u頂點(diǎn)，將其加入P集合，并考察以x頂點(diǎn)為起點(diǎn)的出邊，然后對(duì)dis 進(jìn)行更新。即：如果存在一條從u到v的邊，那么可以拓展一條從s到u再到v的邊，路徑長(zhǎng)度為dis[u]+edge[u] [v] ,如果這個(gè)值比目前的值dis[v]小，那么就進(jìn)行更新。

③重復(fù)第2步，直到Q為空，即book都被標(biāo)記，此時(shí)dis數(shù)組中就是源點(diǎn)到各個(gè)頂點(diǎn)的最短路徑。

代碼實(shí)現(xiàn)

Floyd算法

4.4概念

Floyd算法又稱(chēng)為插點(diǎn)法，是一種利用動(dòng)態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑的算法，與Dijkstra算法類(lèi)似。

?4.5核心思路

①?gòu)娜我庖粭l單邊路徑開(kāi)始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒(méi)有邊相連，則權(quán)為無(wú)窮大。

②對(duì)于每一對(duì)頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。

把圖用鄰接矩陣G表示出來(lái)，如果從Vi到Vj有路可達(dá)，則G[i][j]=d，d表示該路的長(zhǎng)度；否則G[i][j]=無(wú)窮大。定義一個(gè)矩陣D用來(lái)記錄所插入點(diǎn)的信息，D[i][j]表示從Vi到Vj需要經(jīng)過(guò)的點(diǎn)，初始化D[i][j]=j。把各個(gè)頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來(lái)的距離，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值變小，則D[i][j]=k。在G中包含有兩點(diǎn)之間最短道路的信息，而在D中則包含了最短通路徑的信息。

代碼實(shí)現(xiàn)

蘇世學(xué)社旗下品牌，專(zhuān)注于計(jì)算機(jī)考研

計(jì)算機(jī)考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學(xué)習(xí)分享丨咨詢(xún)前輩丨個(gè)性化指導(dǎo)