1、一、圖的入門1.1 圖的實(shí)際應(yīng)用：在現(xiàn)實(shí)生活中，有許多應(yīng)用場景會包含很多點(diǎn)以及點(diǎn)點(diǎn)之間的連接，而這些應(yīng)用場景我們都可以用即將要學(xué)習(xí)的圖 這種數(shù)據(jù)結(jié)構(gòu)去解決。地圖：我們生活中經(jīng)常使用的地圖，基本上是由城市以及連接城市的道路組成，如果我們把城市看做是一個一個的點(diǎn)，把 道路看做是一條一條的連接，那么地圖就是我們將要學(xué)習(xí)的圖這種數(shù)據(jù)結(jié)構(gòu)。電路圖：北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-9090下面是一個我們生活中經(jīng)常見到的集成電路板，它其實(shí)就是由一個一個觸點(diǎn)組成，并把觸點(diǎn)與觸點(diǎn)之間通過線進(jìn)行 連接，這也是我們即將要學(xué)習(xí)的圖這種數(shù)據(jù)結(jié)構(gòu)的應(yīng)用場景1.2 圖的定義及分類定義：圖是由一組

2、頂點(diǎn)和一組能夠?qū)蓚€頂點(diǎn)相連的邊組成的特殊的圖：北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-90901. 自環(huán)：即一條連接一個頂點(diǎn)和其自身的邊；2. 平行邊：連接同一對頂點(diǎn)的兩條邊；圖的分類：按照連接兩個頂點(diǎn)的邊的不同，可以把圖分為以下兩種： 無向圖：邊僅僅連接兩個頂點(diǎn)，沒有其他含義；有向圖：邊不僅連接兩個頂點(diǎn)，并且具有方向；1.3 無向圖1.3.1 圖的相關(guān)術(shù)語相鄰頂點(diǎn)：當(dāng)兩個頂點(diǎn)通過一條邊相連時，我們稱這兩個頂點(diǎn)是相鄰的，并且稱這條邊依附于這兩個頂點(diǎn)。 度：某個頂點(diǎn)的度就是依附于該頂點(diǎn)的邊的個數(shù)子圖：是一幅圖的所有邊的子集(包含這些邊依附的頂點(diǎn))組成的圖； 路徑：是由邊順序

3、連接的一系列的頂點(diǎn)組成環(huán)：是一條至少含有一條邊且終點(diǎn)和起點(diǎn)相同的路徑連通圖：如果圖中任意一個頂點(diǎn)都存在一條路徑到達(dá)另外一個頂點(diǎn)，那么這幅圖就稱之為連通圖北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-9090連通子圖：一個非連通圖由若干連通的部分組成，每一個連通的部分都可以稱為該圖的連通子圖1.3.2 圖的存儲結(jié)構(gòu)要表示一幅圖，只需要表示清楚以下兩部分內(nèi)容即可：1. 圖中所有的頂點(diǎn)；2. 所有連接頂點(diǎn)的邊；常見的圖的存儲結(jié)構(gòu)有兩種：鄰接矩陣和鄰接表1.3.2.1 鄰接矩陣1. 使用一個V*V的二維數(shù)組intVV adj,把索引的值看做是頂點(diǎn)；2. 如果頂點(diǎn)v和頂點(diǎn)w相連，我們只需要

4、將adjvw和adjwv的值設(shè)置為1,否則設(shè)置為0即可。北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-9090很明顯，鄰接矩陣這種存儲方式的空間復(fù)雜度是V2的，如果我們處理的問題規(guī)模比較大的話，內(nèi)存空間極有可能 不夠用。1.3.2.2 鄰接表1. 使用一個大小為V的數(shù)組 QueueV adj，把索引看做是頂點(diǎn)；2. 每個索引處adjv存儲了一個隊(duì)列，該隊(duì)列中存儲的是所有與該頂點(diǎn)相鄰的其他頂點(diǎn)很明顯，鄰接表的空間并不是是線性級別的，所以后面我們一直采用鄰接表這種存儲形式來表示圖。1.3.3 圖的實(shí)現(xiàn)1.3.3.1 圖的API設(shè)計(jì)北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-6

5、18-90901.3.3.2 代碼實(shí)現(xiàn)北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-90901 public class Graph 2 /頂點(diǎn)數(shù)目3 private final int V;4 /邊的數(shù)目5 private int E;6 /鄰接表7 private Queue adj; 89public Graph(int V)10 /初始化頂點(diǎn)數(shù)量11 this.V = V;12 /初始化邊的數(shù)量13 this.E=0;14 /初始化鄰接表15 this.adj = new QueueV;16 /初始化鄰接表中的空隊(duì)列17 for (int i = 0; i adj.len

6、gth; i+) 18 adji = new Queue(); 1920212223 /獲取頂點(diǎn)數(shù)目24 public int V()25 return V; 262728 /獲取邊的數(shù)目29 public int E()30 return E; 313233 /向圖中添加一條邊 v-w34 public void addEdge(int v, int w) 35 /把w添加到v的鏈表中，這樣頂點(diǎn)v就多了一個相鄰點(diǎn)w類名Graph構(gòu)造方法Graph(int V)：創(chuàng)建一個包含V個頂點(diǎn)但不包含邊的圖成員方法1.public int V():獲取圖中頂點(diǎn)的數(shù)量2.public int E():獲取

7、圖中邊的數(shù)量3.public void addEdge(int v,int w):向圖中添加一條邊 v-w 4.public Queue adj(int v)：獲取和頂點(diǎn)v相鄰的所有頂點(diǎn)成員變量1.private nal int V: 記錄頂點(diǎn)數(shù)量2.private int E: 記錄邊數(shù)量3.private Queue adj: 鄰接表1.3.4 圖的搜索在很多情況下，我們需要遍歷圖，得到圖的一些性質(zhì)，例如，找出圖中與指定的頂點(diǎn)相連的所有頂點(diǎn)，或者判定某 個頂點(diǎn)與指定頂點(diǎn)是否相通，是非常常見的需求。有關(guān)圖的搜索，最經(jīng)典的算法有深度優(yōu)先搜索和廣度優(yōu)先搜索，接下來我們分別講解這兩種搜索算法。1.

8、3.4.1 深度優(yōu)先搜索所謂的深度優(yōu)先搜索，指的是在搜索時，如果遇到一個結(jié)點(diǎn)既有子結(jié)點(diǎn)，又有兄弟結(jié)點(diǎn)，那么先找子結(jié)點(diǎn)，然后找 兄弟結(jié)點(diǎn)。北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-909036 adjv.enqueue(w);37 /把v添加到w的鏈表中，這樣頂點(diǎn)w就多了一個相鄰點(diǎn)v38 adjw.enqueue(v);39 /邊的數(shù)目自增140E+;414243 /獲取和頂點(diǎn)v相鄰的所有頂點(diǎn)44 public Queue adj(int v)45 return adjv; 464748很明顯，在由于邊是沒有方向的，所以，如果4和5頂點(diǎn)相連，那么4會出現(xiàn)在5的相鄰鏈表中，5也會

9、出現(xiàn)在4的相 鄰鏈表中，那么為了不對頂點(diǎn)進(jìn)行重復(fù)搜索，應(yīng)該要有相應(yīng)的標(biāo)記來表示當(dāng)前頂點(diǎn)有沒有搜索過，可以使用一個布 爾類型的數(shù)組 booleanV marked,索引代表頂點(diǎn)，值代表當(dāng)前頂點(diǎn)是否已經(jīng)搜索，如果已經(jīng)搜索，標(biāo)記為true， 如果沒有搜索，標(biāo)記為false；API設(shè)計(jì)：代碼：北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-9090類名DepthFirstSearch構(gòu)造方法DepthFirstSearch(Graph G,int s)：構(gòu)造深度優(yōu)先搜索對象，使用深度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相通頂點(diǎn)成員方法1.private void dfs(Graph G, int

10、 v)：使用深度優(yōu)先搜索找出G圖中v頂點(diǎn)的所有相通頂點(diǎn)2.public boolean marked(int w):判斷w頂點(diǎn)與s頂點(diǎn)是否相通3.public int count():獲取與頂點(diǎn)s相通的所有頂點(diǎn)的總數(shù)成員變量1. private boolean marked: 索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索2. private int count：記錄有多少個頂點(diǎn)與s頂點(diǎn)相通1.3.4.2 廣度優(yōu)先搜索所謂的深度優(yōu)先搜索，指的是在搜索時，如果遇到一個結(jié)點(diǎn)既有子結(jié)點(diǎn)，又有兄弟結(jié)點(diǎn)，那么先找兄弟結(jié)點(diǎn)，然后 找子結(jié)點(diǎn)。北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-90901

11、 public class DepthFirstSearch 2 /索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索3 private boolean marked;4 /記錄有多少個頂點(diǎn)與s頂點(diǎn)相通5 private int count; 67 /構(gòu)造深度優(yōu)先搜索對象，使用深度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相鄰頂點(diǎn)8 public DepthFirstSearch(Graph G,int s)9 /創(chuàng)建一個和圖的頂點(diǎn)數(shù)一樣大小的布爾數(shù)組10 marked = new booleanG.V();11 /搜索G圖中與頂點(diǎn)s相同的所有頂點(diǎn)12 dfs(G,s); 131415 /使用深度優(yōu)先搜索找出G圖

12、中v頂點(diǎn)的所有相鄰頂點(diǎn)16 private void dfs(Graph G, int v)17 /把當(dāng)前頂點(diǎn)標(biāo)記為已搜索18 markedv=true;19 /遍歷v頂點(diǎn)的鄰接表，得到每一個頂點(diǎn)w20 for (Integer w : G.adj(v)21 /如果當(dāng)前頂點(diǎn)w沒有被搜索過，則遞歸搜索與w頂點(diǎn)相通的其他頂點(diǎn)22 if (!markedw)23 dfs(G,w);242526 /相通的頂點(diǎn)數(shù)量+127 count+;282930 /判斷w頂點(diǎn)與s頂點(diǎn)是否相通31 public boolean marked(int w)32 return markedw; 333435 /獲取與頂點(diǎn)

13、s相通的所有頂點(diǎn)的總數(shù)36 public int count()37 return count; 383940API設(shè)計(jì)：代碼：北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-90901 public class BreadthFirstSearch 2 /索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索3 private boolean marked;4 /記錄有多少個頂點(diǎn)與s頂點(diǎn)相通5 private int count;6 /用來存儲待搜索鄰接表的點(diǎn)7 private Queue waitSearch;8類名BreadthFirstSearch構(gòu)造方法BreadthFirstSea

14、rch(Graph G,int s)：構(gòu)造廣度優(yōu)先搜索對象，使用廣度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相鄰頂點(diǎn)成員方法1.private void bfs(Graph G, int v)：使用廣度優(yōu)先搜索找出G圖中v頂點(diǎn)的所有相鄰頂點(diǎn)2.public boolean marked(int w):判斷w頂點(diǎn)與s頂點(diǎn)是否相通3.public int count():獲取與頂點(diǎn)s相通的所有頂點(diǎn)的總數(shù)成員變量1. private boolean marked: 索引代表頂點(diǎn)，值表示當(dāng)前頂點(diǎn)是否已經(jīng)被搜索2. private int count：記錄有多少個頂點(diǎn)與s頂點(diǎn)相通3.private Queue w

15、aitSearch: 用來存儲待搜索鄰接表的點(diǎn)1.3.5 案例-暢通工程續(xù)1某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計(jì)表，表中列出了每條道路直接連通的城鎮(zhèn)。省“暢通工程”的目標(biāo)是使全省任何兩個城鎮(zhèn)間都可以實(shí)現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過道路可達(dá)即可）。目 前的道路狀況，9號城市和10號城市是否相通？9號城市和8號城市是否相通？在我們的測試數(shù)據(jù)文件夾中有一個trc_project.txt文件，它就是誠征道路統(tǒng)計(jì)表，下面是對數(shù)據(jù)的解釋：北京市昌平區(qū)建材城西路金燕龍辦公樓一層電話：400-618-90909 /構(gòu)造廣度優(yōu)先搜索對象，使用廣度優(yōu)先搜索找出G圖中s頂點(diǎn)的所有相鄰頂點(diǎn)1

16、0 public BreadthFirstSearch(Graph G, int s) 11 /創(chuàng)建一個和圖的頂點(diǎn)數(shù)一樣大小的布爾數(shù)組12 marked = new booleanG.V();13 /初始化待搜索頂點(diǎn)的隊(duì)列14 waitSearch = new Queue();15 /搜索G圖中與頂點(diǎn)s相同的所有頂點(diǎn)16 dfs(G, s); 171819 /使用廣度優(yōu)先搜索找出G圖中v頂點(diǎn)的所有相鄰頂點(diǎn)20 private void dfs(Graph G, int v) 21 /把當(dāng)前頂點(diǎn)v標(biāo)記為已搜索22 markedv=true;23 /把當(dāng)前頂點(diǎn)v放入到隊(duì)列中，等待搜索它的鄰接表24 waitSearch.enqueue(v);25 /使用while循環(huán)從隊(duì)列中拿出待搜索的頂點(diǎn)wait，進(jìn)行搜索鄰接表26 while(!waitSearch.isEmpty()27 Integer wait = waitSearch.dequeue();28 /遍歷wait頂點(diǎn)的鄰接表，得到每一個頂點(diǎn)w29 for (Integer w : G.