目錄 第六章 圖

第一節(jié) 基本概念

1.1 定義和術(shù)語
1.2 基本操作

第二節(jié) 存儲(chǔ)結(jié)構(gòu)

2.1 鄰接矩陣
2.2 鄰接表

第三節(jié) 圖的遍歷

3.1 深度優(yōu)先搜索（Depth First Search，DFS）
3.2 廣度優(yōu)先搜索（Breadth First Search，BFS）

第四節(jié) 圖的應(yīng)用

4.1 最小生成樹

本章小結(jié)

第六章 圖

圖狀結(jié)構(gòu)是一種比樹形結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。在樹形結(jié)構(gòu)中，結(jié)點(diǎn)間具有分支層次關(guān)系，每一層上的結(jié)點(diǎn)只能和上一層的至多一個(gè)結(jié)點(diǎn)相關(guān)，但可能和下一層的多個(gè)結(jié)點(diǎn)相關(guān)。而在圖狀結(jié)構(gòu)中，任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)，即結(jié)點(diǎn)之間的鄰接關(guān)系可以是任意的。因此，圖是比樹更一般、更復(fù)雜的非線性結(jié)構(gòu)，常被用于描述各種復(fù)雜的數(shù)據(jù)對(duì)象，在自然科學(xué)、社會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域有著非常廣泛的應(yīng)用。

第一節(jié) 基本概念

1.1 定義和術(shù)語

（1）定語：

圖（Graph）是由非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間的關(guān)系——邊（或者弧）的集合組成的，其形式化定義為：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj之間有一條直接連線，即偶對(duì)(v1,vj）表示一條邊。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

（2）術(shù)語:

1、無向圖：在一個(gè)圖中，如果任意兩個(gè)頂點(diǎn)構(gòu)成的偶對(duì)(vi,vj）包含E是無序的，即頂點(diǎn)之間的連線是沒有方向的，則稱該圖為無向圖。

2、有向圖：在一個(gè)圖中，如果任意兩個(gè)頂點(diǎn)構(gòu)成的偶對(duì)<vj,vj>包含E是有序的（有序?qū)Τ３Ｓ眉饫ㄌ?hào)“<>”表示），即頂點(diǎn)之間的連線是有方向的，則稱該圖為有向圖。

3、頂點(diǎn)、邊、弧、弧頭、弧尾：在圖中，數(shù)據(jù)元素vi稱為頂點(diǎn)（Vertex）；（vj，vj）表示在頂點(diǎn)vi和頂點(diǎn)vj之間有一條直接連線。如果是在無向圖中，則稱這條連線為邊；如果是在有向圖中，一般稱這條連線為弧。邊用頂點(diǎn)的無序偶對(duì)（vi，vj）來表示，稱頂點(diǎn)vi和vj互為鄰接點(diǎn)，邊<vi,vj>依附于頂點(diǎn)vi與頂點(diǎn)vj；弧用頂點(diǎn)的有序偶對(duì)<vi,vj>來表示，有序偶對(duì)的第一個(gè)節(jié)點(diǎn)vi被稱為始點(diǎn)(或弧尾），在圖中就是不帶箭頭的一端；有序偶對(duì)的第二個(gè)節(jié)點(diǎn)vj被稱為終點(diǎn)(或弧頭），在圖中就是帶箭頭的一端。

4、無向完全圖：在一個(gè)無向圖中，如果任意兩頂點(diǎn)都有一條直接邊相連接，則稱該圖為無向完全圖?？梢宰C明，在一個(gè)含有n個(gè)頂點(diǎn)的無向完全圖中，有n（n-1）/2條邊。

5、有向完全圖：在有一個(gè)有向圖中，如果任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，有n(n-1)條邊。

6、頂點(diǎn)的度、入度、出度：頂點(diǎn)的度（Degree）是指依附于某頂點(diǎn)v的邊數(shù)，通常記為TD(v)。頂點(diǎn)v的入度是指以頂點(diǎn)v為終點(diǎn)的弧的數(shù)目，記為ID(V)；出度是指以頂點(diǎn)v為始點(diǎn)的弧的數(shù)目，記為OD(V)。有TD(V)=ID(v)+OD(v)。

7、邊的權(quán)、網(wǎng)：與邊有關(guān)的數(shù)據(jù)信息稱為權(quán)(Weight)。在實(shí)際應(yīng)用中，權(quán)值可以有某種含義。例如，在一個(gè)反映城市交通線路的圖中，邊上的權(quán)值可以表示該條線路的長(zhǎng)度或等級(jí)；對(duì)于一個(gè)電子線路圖，邊上的權(quán)值可以表示兩個(gè)端點(diǎn)之間的電阻、電流或電壓值；對(duì)于反映工程進(jìn)度的圖而言，邊上的權(quán)值可以表示從前一個(gè)工程到后一個(gè)工程所需要的時(shí)間或其他代價(jià)等。邊上帶權(quán)的圖稱為網(wǎng)或網(wǎng)絡(luò)（network）。

8、路徑、路徑長(zhǎng)度：頂點(diǎn)vp到頂點(diǎn)vq之間的路徑（path）是指頂點(diǎn)序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長(zhǎng)度。

9、簡(jiǎn)單路徑、回路、簡(jiǎn)單回路：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。路徑中第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同的 路徑稱為回路或環(huán)（Cycle）。除第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)之外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路，或者簡(jiǎn)單環(huán)。

10、子圖：對(duì)于圖G=（V，E），G'=（V',E'），若存在 V'是V的子集， E'是E的子集，則稱圖 G'是G的的一個(gè)子圖。

11、連通、連通圖、連通分量：在無向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i=!j)存在路徑，則稱頂點(diǎn)vi和vj是連通的。如果圖中任意兩個(gè)頂點(diǎn)都是連通的，則稱該圖是連通圖。無向圖的極大連通子圖稱為連通分量，極大連通子圖是指在保證連通與子圖的條件下，包含原圖中所有的頂點(diǎn)與邊。 如下圖：

image.png

12、強(qiáng)連通圖、強(qiáng)連通分量：對(duì)于有向圖來說，若圖中任意一對(duì)頂點(diǎn)vi和vj（i=!j）均存在從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj和從vj到vi的路徑，則稱該有向圖是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量，極大強(qiáng)連通子圖的含義同上。

13、生成樹：所謂連通圖G的生成樹，是G的包含其全部n個(gè)頂點(diǎn)的一個(gè)極小連通子圖，所謂極小連通子圖是指在包含所有頂點(diǎn)且保證連通的前提下盡可能少地包含原圖中的邊。生成樹必定包含且僅包含連通圖G的n-1條邊。在生成樹中添加任意一條屬于原圖中的邊必定會(huì)產(chǎn)生回路，因?yàn)樾绿砑拥倪吺蛊渌栏降膬蓚€(gè)頂點(diǎn)之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。

14、生成森林：在非連通圖中，由每個(gè)連通分量都可得到一個(gè)極小連通子圖，即一棵生成樹。這些連通分量的生成樹就組成了一個(gè)非連通圖的生成森林。

1.2 基本操作

1、GreatGraph(G) ： 輸入圖G的頂點(diǎn)和邊，建立圖G的存儲(chǔ)。
2、DestroyGraph(G) ：釋放圖G占用的存儲(chǔ)空間。
3、GetVex(G，v)：在圖G中找到頂點(diǎn)v，并返回頂點(diǎn)v的相關(guān)信息。
4、PutVex(G,V,value)：在圖G中找到頂點(diǎn)v，并將value值賦予給頂點(diǎn)v。
5、InsertVex(G,v）：在圖G中增添新頂點(diǎn)v。
6、DeleteVex(G,v)：在圖G中，刪除頂點(diǎn)v及所有和頂點(diǎn)v相關(guān)的邊或弧。
7、InsertArc(G,v,w)：在圖G中增添一條從頂點(diǎn)v到頂點(diǎn)w的邊或弧。
8、DeleteArc(G,v,w)：在圖G中刪除一條從頂點(diǎn)v到頂點(diǎn)w的邊或弧。
9、DFSTraverse(G,v)：在圖G中，從頂點(diǎn)v出發(fā)深度優(yōu)化遍歷圖G。
10、BFSTtaverse(G,v)：在圖G中，從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷圖G。

在一個(gè)圖中，頂點(diǎn)是沒有先后次序的，但當(dāng)采用某一種確定的存儲(chǔ)方式存儲(chǔ)后，存儲(chǔ)結(jié)構(gòu)中頂點(diǎn)的存儲(chǔ)次序成了頂點(diǎn)之間的相對(duì)次序，這里用頂點(diǎn)在圖中的位置表示該頂點(diǎn)的存儲(chǔ)順序；同樣的道理，對(duì)一個(gè)頂點(diǎn)的所有鄰接點(diǎn)，采用該頂點(diǎn)的第i個(gè)鄰接點(diǎn)表示與該頂點(diǎn)相鄰接的某個(gè)頂點(diǎn)的存儲(chǔ)順序，在這種意義下，圖還有以下的基本操作。

11、LocateVex（G，u）：在圖G中找到頂點(diǎn)u，返回該頂點(diǎn)在圖中位置。
12、FirstAdjVex（G，v）：在圖G中，返回v的第一個(gè)鄰接點(diǎn)。若頂點(diǎn)在G中沒有鄰接頂點(diǎn)，則返回“空”。
13、NextAdjVex(G，v，w)：在圖G中， 返回v的（相對(duì)于w的）下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接點(diǎn)，則返回"空”。

第二節(jié) 存儲(chǔ)結(jié)構(gòu)

圖是一種結(jié)構(gòu)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，表現(xiàn)在不僅各個(gè)頂點(diǎn)的度可以千差萬別，而且頂點(diǎn)之間的邏輯關(guān)系也錯(cuò)綜復(fù)雜。從圖的定義可知，一個(gè)圖的信息包括兩部分，即圖中頂點(diǎn)的信息及描述頂點(diǎn)之間的關(guān)系——邊或弧的信息。因此，無論采用什么方法建立圖的存儲(chǔ)結(jié)構(gòu)，都要完整、準(zhǔn)確地反映這兩方面的信息。

2.1 鄰接矩陣

所謂鄰接矩陣（Adjacency Matrix）的存儲(chǔ)結(jié)構(gòu)，就是用一維數(shù)組存儲(chǔ)圖中的頂點(diǎn)信息，用矩陣表示圖中各頂點(diǎn)之間的鄰接關(guān)系。假設(shè)圖G=(V,E)有n個(gè)確定的頂點(diǎn)，即V ={v0,v1，···，vn-1}，則表示G中各頂點(diǎn)相鄰關(guān)系的矩陣為一個(gè)n×n的矩陣，矩陣的元素為：

A[i][j]={1,若(vi,vj)或<vi,vj>是E(G)中的邊 ；2，若(vi,vj）或<vi,vj>不是E(G)中的邊。

若G是網(wǎng)，則鄰接矩陣可定義為：

A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的邊 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的邊。
其中，wij表示邊(Vi,vj)或<vi,vj>上的權(quán)值；表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。

（1）無向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。因此，在具體存放鄰接矩陣時(shí)只需存放上或下三角矩陣的元素即可。

（2）對(duì)于無向圖，鄰接矩陣的第i行或第i列非零元素或非&元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度TD(vi)。

（3）對(duì)于有向圖，鄰接矩陣的第i行和第i列非零元素或非&元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度OD(vi)或入度ID(vi)。

（4）用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測(cè)，所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣存儲(chǔ)圖的局限性。

在實(shí)際應(yīng)用鄰接矩陣存儲(chǔ)圖時(shí)，除了用一個(gè)二維數(shù)組存儲(chǔ)用于表示頂點(diǎn)間相鄰關(guān)系的鄰接矩陣外，還需用一個(gè)一維數(shù)組來存儲(chǔ)頂點(diǎn)信息，另外，還有圖的頂點(diǎn)數(shù)和邊數(shù)。故可將其形式描述如下：

#define MaxVertexNum 100 
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType vexs[MaxVertexNum];//頂點(diǎn)表
    EdgeType edges[MaxVertexNum] [MaxVertexNum];//相鄰矩陣，即邊表
    int n,e;//頂點(diǎn)數(shù)和邊數(shù)
 }MGraph;

2.2 鄰接表

鄰接表（Adjacency List）是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對(duì)于圖G中的每個(gè)頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表，再將所有頂點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖鄰接表。

在鄰接表表示中有兩種結(jié)點(diǎn)結(jié)構(gòu)：一種是頂點(diǎn)表的結(jié)點(diǎn)結(jié)構(gòu)，它由頂點(diǎn)域（vertex）和指向第一條鄰接邊的指針域（firstedge）構(gòu)成。另一種是邊表即鄰接表結(jié)點(diǎn)，它由鄰接點(diǎn)域（adjvex）和指向下一條鄰接邊的指針域（next）構(gòu)成。對(duì)于圖的邊表需再增設(shè)一個(gè)存儲(chǔ)邊上的信息（如權(quán)值等）的域（info）。形式如下：

#define MaxVerNu
typedef struct node{
    int adjvex;
    struct node*next;
}EdgeNode;
 
typedef struct vnode{
    VertexType vertex;
    EdgeNode *firstedge;
}VertexNode;
 
typedef VertexNode AdjList[MaxVertexNum];
 
typedef struct{
    AdjList adjlist;
    int n ,e;
}ALGraph;

若無向圖中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。顯然，在邊稀疏（e<<n(n-1)/2）的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲(chǔ)空間，當(dāng)和邊相關(guān)的信息較多時(shí)更是如此。在無向圖的鄰接表中，頂點(diǎn)vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)；而在有向圖中，第i個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)v1的出度，求入度，必須遍歷整個(gè)整個(gè)鄰接表。在所有鏈表中其鄰接點(diǎn)域的值為i的結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的入度。有時(shí)，為了便于確定頂點(diǎn)的入度或以頂點(diǎn)vi為頭的弧，可以建立一個(gè)有向的逆鄰接表，即對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)鏈接以vi為頭的弧的鏈表。

在建立鄰接表或逆鄰表時(shí)，若輸入的頂點(diǎn)信息即為頂點(diǎn)的編號(hào)，則建立鄰接表的復(fù)雜度為O(n+e)，否則，需要通過查找才能得到頂點(diǎn)在圖中位置，則時(shí)間復(fù)雜度為O(ne)。

在鄰接表上容易找到任意頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰結(jié)點(diǎn)，但要判定任意兩個(gè)頂點(diǎn)(vi和vj)之間是否有邊或弧相連，則需查找第i個(gè)或第j個(gè)鏈表，因此，不如鄰接矩陣方便。

第3節(jié) 圖的遍歷

圖的遍歷是指從圖中的任意頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其他操作都是建立在遍歷操作的基礎(chǔ)之上的。

3.1 深度優(yōu)先搜索（Depth First Search，DFS）

類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設(shè)初始化狀態(tài)是圖中所有頂點(diǎn)未曾被訪問，則深度優(yōu)先搜索可從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問此頂點(diǎn)，然后依然從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)化遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。如下圖：

image.png

a所示的無向圖G4，進(jìn)行圖的深度優(yōu)先搜索。假設(shè)從頂點(diǎn)v1出發(fā)進(jìn)行搜索，在訪問了頂點(diǎn)v1之后，選擇鄰接點(diǎn)v2。因?yàn)関2未曾訪問，則從v2出發(fā)進(jìn)行搜索，以此類推，接著從v4,v8,v5出發(fā)進(jìn)行搜索。在訪問了v5之后，由于其鄰接點(diǎn)都已經(jīng)被訪問了，則搜索回到v8，同理，搜索繼續(xù)回到到v4,v2,v1。此時(shí)，由于v1的另一個(gè)鄰接點(diǎn)未被訪問，則查找又從v1到v3，v6，v7。顯然，這是一個(gè)遞歸的過程。為了遍歷過程中便于區(qū)分頂點(diǎn)是否已被訪問，需要附設(shè)訪問標(biāo)志數(shù)組visited[0:n-1]，其初值為FALSE,一旦某個(gè)頂點(diǎn)被訪問，則其相應(yīng)的分量置為TRUE。

void DFS(Graph G,int v){
    //從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G
    visited[v] =TRUE;
    //訪問第v個(gè)點(diǎn)
    VisitFunc(v);
    for(w=FirstAdjVex(G,V) ;w ;w =NextAdjVex(G,v,w))
    //對(duì)v的尚未訪問鄰接頂點(diǎn)w遞歸調(diào)用DFS
    if(!visited[w]) 
        DFS(G,W);
}

深度優(yōu)化搜索算法實(shí)現(xiàn)：

void DFSTraverseAL(ALGraph *G){
        /*深度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖G*/
        int i;
        for (i=0; i<G ->n; i++)
             visited[i]=FALSE;              /*標(biāo)志向量初始化*/
        for (i=0; i<G ->n; i++)
             if (!visited[i]) DFSAL(G, i);  /*vi 未訪問過，從vi開始DFS搜索*/
}                                    
 
   /*DFSTraveseAL*/
void DFSAL(ALGraph *G , int i) {
     /*以Vi為出發(fā)點(diǎn)對(duì)鄰接表存儲(chǔ)的圖G進(jìn)行DFS搜索*/
      EdgeNode *p;
      printf ("visit vertex:V%c\n", G ->adjlist[i].vertex); /*訪問頂點(diǎn)vi*/
      visited[i]=TRUE;                      /*標(biāo)記vi已訪問*/
      p=G ->adjlist[i].firstedge;
      //取vi邊表的頭指針    
      while(p){
        if(!visited[p->adjvex])
            DFSAL(G,p->adjvex);
        p = p->next;
      }
}

3.2 廣度優(yōu)先搜索（Breadth First Search，BFS）

類似于樹的按層次遍歷的過程。假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的鄰接點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過程，直至所有頂點(diǎn)都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起始點(diǎn)，由近至遠(yuǎn)，依次訪問和v有路徑相通且路徑長(zhǎng)度為1，2，···的頂點(diǎn)。

如上圖中的c，首先訪問v1和v1的鄰接點(diǎn)v2和v3，然后依次訪問v2的鄰接點(diǎn)v4和v5及v3的鄰接點(diǎn)v6和v7，最后訪問v4的鄰接點(diǎn)v8。得到訪問序列為：v1 →v2→v3→v4→v5→v6→v7→v8。和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個(gè)訪問標(biāo)志數(shù)組。并且為了順次訪問路徑長(zhǎng)度為1，2，3···的頂點(diǎn)，需要附設(shè)隊(duì)列以存儲(chǔ)已被訪問的路徑長(zhǎng)度為1，2，···的頂點(diǎn)。從圖的某一點(diǎn)v出發(fā)，非遞歸地進(jìn)行廣度優(yōu)先遍歷的過程算法如下所示：

voidBFSTraverse(Grapg G,Status （*Visit）（int v)){
    //按廣度優(yōu)先非遞歸遍歷圖G，使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visied
    for(v =0 ;v =G.vexnum ;++v)
        visited[v] =FALSE;
 
  //置空隊(duì)列Q
    Init_Queue(Q);
  
//v尚未被訪問
    if(!visited[v]){
        In_Queue(Q,v);//v入隊(duì)列
        while(!QueueEmpty(Q)){
            Out_Queue(Q,u);
            visited[u] =TURE;
            visit(u);
            for(w =FirstAdjVex(G,u) ; w ;w =NextAdjVex(G,u,w))
            if(!visited[w] 
                In_Queue(Q,W);
        }
    }
}

下面算法給出了對(duì)以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的圖G進(jìn)行廣度優(yōu)先搜索實(shí)現(xiàn)的C語言描述。廣度優(yōu)先搜索算法：

 /*廣度優(yōu)先遍歷以鄰接矩陣存儲(chǔ)的圖G*/
void BFSTraverseAL(MGraph *G)              
{   int i;
    for (i=0; i<G ->n; i++)
          visited[i]=FALSE;                 /*標(biāo)志向量初始化*/
          for (i=0; i<G ->n; i++)
            if (!visited[i]) BFSM(G, i);    /* vi 未訪問過，從vi開始BFS查找*/
}    
 
/*BFSTraverseAL*/
void BFSM(Mgraph *G , int k)                /*以vk為出發(fā)點(diǎn)，對(duì)圖G進(jìn)行BFS查找*/
    { int i, j;
        C_Queue Q;
        Init_Queue(&Q);
        printf("visit vertex:V%c\n",G ->vexs[k]); /*訪問原點(diǎn)vk*/
        visited[k]=TRUE;
    In_Queue(&Q, k);                        /*原點(diǎn)vk入隊(duì)列*/
    while (!QueueEmpty(&Q))
        { i=Out_Queue(&Q);                  /*vi 出隊(duì)列*/
          for (j=0; j<G ->n; j++)           /*依次查找vi的鄰接點(diǎn)vj*/
            if (G ->edges[i][j]= =1 && !visited[j]) /*若vj未訪問*/
              { printf("visit vertex:V%c\n", G ->vexs[j]); /*訪問vj */
                visited[j]=TRUE;
                In_Queue(&Q, j);            /*訪問過的vj入隊(duì)列*/
               }
        }
  } /*BFSM*/

分析上述算法，每個(gè)頂點(diǎn)最多進(jìn)一次隊(duì)列。遍歷圖的過程實(shí)質(zhì)是通過邊或弧找鄰接點(diǎn)的過程，因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者的不同之處僅在于對(duì)頂點(diǎn)訪問的順序不同。

第4節(jié) 圖的應(yīng)用

4.1 最小生成樹

（1）基本概念：由于生成樹的定義可知，無向連通圖的生成樹不是唯一的。連通圖的一次遍歷所經(jīng)過的邊的集合及圖中所有頂點(diǎn)的集合就構(gòu)成了該圖的一棵生成樹，對(duì)連通圖的不同遍歷，就可能得到不同的生成樹。對(duì)于有n個(gè)頂點(diǎn)的無向連通圖，無論其生成樹的形態(tài)如何，所有生成樹中都有且僅有n-1條邊。

如果無向連通圖是一個(gè)網(wǎng)，那么，它的所有生成樹中必有一棵生成樹的邊的權(quán)值總和最小，稱這樣的一棵生成樹為最小代價(jià)生成樹（Minimum Cost Spanning Tree），簡(jiǎn)稱最小生成樹（MST）。一棵生成樹的代價(jià)就是樹中所有的邊的代價(jià)之和。

最小生成樹的概念可以應(yīng)用到許多實(shí)際問題中。例如，以盡可能低的總價(jià)建造城市間的通信網(wǎng)絡(luò)，把十個(gè)城市聯(lián)系在一起。在這十個(gè)城市中，任意兩個(gè)城市之間都可以建造通信線路，通信線路的造價(jià)依據(jù)城市間的距離不同而不同，可以構(gòu)造一個(gè)通信線路造價(jià)網(wǎng)絡(luò)，在網(wǎng)絡(luò)中，每個(gè)頂點(diǎn)表示城市，頂點(diǎn)之間的邊表示城市之間可構(gòu)造通信線路，每條邊的權(quán)值表示該條通信線路的造價(jià)，要想使總的造價(jià)最低，實(shí)際上就是尋找該網(wǎng)絡(luò)的最小生成樹。

構(gòu)造最小生成樹的方法很多，其中大多數(shù)算法都利用了MST性質(zhì)。MST性質(zhì)描述如下：
設(shè)G=(V,E)是一個(gè)連通網(wǎng)，其中V為網(wǎng)中所有頂點(diǎn)的集合，E為網(wǎng)中所有帶權(quán)邊的集合，再設(shè)集合U用于存放G的最小生成樹的頂點(diǎn)。若邊（u，v）是G中所有一端在U中而另一端在V-U中 具有最小權(quán)值的一條邊，則存在一棵包含邊（u，v）的最小生成樹。關(guān)于MST性質(zhì)的證明請(qǐng)參閱有關(guān)書籍，這里略去。

（2）Prim算法和Kruskal算法

假設(shè)G =（V，E）為一連通網(wǎng)，其中V為網(wǎng)中所有頂點(diǎn)的集合，E為網(wǎng)中所有帶權(quán)邊的集合。設(shè)置兩個(gè)新的集合U和T，其中集合U用于存放G的最小生成樹中的頂點(diǎn)，集合T存放G的最小生成樹中的邊。令集合U的初值為U={u1}（假設(shè)構(gòu)造最小生成樹時(shí)，從頂點(diǎn)u1出發(fā)），集合T的初值為T={}。Prim算法的思想是，從所有u包含U，u包含V-U的邊中，選取具有最小權(quán)值的邊（u，v），將頂點(diǎn)v加入集合U中，將邊（u，v）加入集合T中，如此不斷重復(fù)，直到U=V時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合T中包含了最小生成樹的所有邊。

Prim算法可用下述過程描述，其中用wuv表示頂點(diǎn)u與頂點(diǎn)v邊上的權(quán)值。

1、U ={U1},T={};
 
2、while(U=!V)do
 
(u,v) =min{wun;u包含U，v包含V-U}
 
T =T+{(u,v)}
 
U=U+{V}
 
3、結(jié)束

Prim算法構(gòu)造最小生成樹的過程示意圖如下：

image.png

為實(shí)現(xiàn)Prim算法，需設(shè)置兩個(gè)輔助一維數(shù)組lowcost和closevertex，其中，lowcost用來保存集合V-U中各頂點(diǎn)與集合U中各頂點(diǎn)構(gòu)成的邊中具有最小權(quán)值的邊的權(quán)值；數(shù)組closevertex用來保存依附于該邊的在集合U中的頂點(diǎn)。假設(shè)初始化狀態(tài)時(shí)，U={u1（出發(fā)的頂點(diǎn)）},這時(shí)有l(wèi)owcost[0]=0,它表示頂點(diǎn)u1已加入集合中，數(shù)組lowcost的其他各分量的值是頂點(diǎn)u1到其余各頂點(diǎn)所構(gòu)成的直接邊的權(quán)值。然后不斷選取最小的邊（ui，uk）（u包含U,uk包含V-U），每選取一條邊，就將lowcost（k）置為0，表示頂點(diǎn)uk已加入集合U中。由于頂點(diǎn)uk從集合V-U進(jìn)入集合U后，這兩個(gè)集合的內(nèi)容發(fā)生了變化，就需依據(jù)具體情況更新數(shù)組lowcost和closevertex中部分分量的內(nèi)容。

當(dāng)無向網(wǎng)采用二維數(shù)組存儲(chǔ)的鄰接矩陣存儲(chǔ)時(shí)，Prim算法如下：

void Prim(int gm[][MAXNODE],int n,int closevertex[]){
    //    從序號(hào)為0的頂點(diǎn)出發(fā)，建立的最小生成樹存于數(shù)組closevertex中
    int lowcost[100],mincost;
    int i,j,k;
    for(i=1;i<n;i++){
        lowcost[i] =gm[0][i];
        closevertex[i] =0;
    }
    lowcost[0] = 0;//從序號(hào)0的頂點(diǎn)出發(fā)生成最小生成樹
    closevvertex[0] = 0;
    for(i =1 ;i<n; i++){
        mincost =MAXCOST;
        j =1;        
        k =1;
        while(j<n){
            if(lowcost[j]<mincost&&lowcost[j]!=0){
                mincost =lowcost[j];
                k = j;
            }
            j ++;
        }
        lowcost[k] = 0 ;
        for(j =1 ;j<n;j++){
            if(gm[k][j] <lowcost[j]){
                lowcost[j] =gm[k][j];
                closevertex[j] = k;
            }
        }
    }
}

在上述算法中，第一個(gè)for循環(huán)的執(zhí)行次數(shù)為n-1，第二個(gè)for循環(huán)中又包含了一個(gè)while循環(huán)和一個(gè)for循環(huán)，執(zhí)行次數(shù)為2（n-1）2，所以Prim算法的時(shí)間復(fù)雜度為O(n2）。

Kruskal算法基本思想如下：設(shè)G=(V, E)是連通網(wǎng)，集合T存放G的最小生成樹中的邊。初始時(shí)，最小生成樹中已經(jīng)包含G中的全部頂點(diǎn)，集合T的初值為T={}，這樣每個(gè)頂點(diǎn)就自成一個(gè)連通分量。最小生成樹的生成過程是，在圖G的邊集E中按權(quán)值自小至大依次選擇邊（u, v），若該邊端點(diǎn)u、v分別屬于當(dāng)前兩個(gè)不同的連通分量，則將該邊（u, v）加入到T，由此這兩個(gè)連通分量連接成一個(gè)連通分量，整個(gè)連通分量數(shù)量就減少了一個(gè)；若u、v是當(dāng)前同一個(gè)連通分量的頂點(diǎn)，則舍去此邊，繼續(xù)尋找下一條兩端不屬于同一連通分量的權(quán)值最小的邊，依此類推，直到所有的頂點(diǎn)都在同一個(gè)連通分量上為止。這時(shí)集合T中包含了最小生成樹的所有邊。算法描述如下：

T={};
while(T中的邊數(shù)<n-1){//n為G中的頂點(diǎn)數(shù)
從E中選取當(dāng)前最短邊(u,v)
刪除E中條邊（u，v）
if((u,v)并入T之后不產(chǎn)生回路)
    將(u,v)并入T中
}

Kruskal 算法構(gòu)造最小生成樹的過程示意圖：

image.png

本章小結(jié)

圖是一種重要的非線性結(jié)構(gòu)。它的特點(diǎn)是每一個(gè)頂點(diǎn)都可以與其他頂點(diǎn)相關(guān)聯(lián)，與樹不同，圖中各個(gè)頂點(diǎn)的地位都是平等的，對(duì)頂點(diǎn)的編號(hào)都是人為的。

通常，定義圖由兩個(gè)集合構(gòu)成：一是頂點(diǎn)的非空有限集合；二是頂點(diǎn)與頂點(diǎn)之間關(guān)系（邊）的有限集合。

對(duì)圖的處理要區(qū)分有向圖和無向圖。它的存儲(chǔ)表示可以使用鄰接矩陣，也可以使用鄰接表，前者屬順序存儲(chǔ)結(jié)構(gòu)，后者屬鏈接表示。

本章還著重討論了圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法。

對(duì)于帶權(quán)圖，給出了構(gòu)造最小生成樹的方法：

Prim算法和Kruskal算法。在解決最短路徑問題時(shí)，采用了逐步求解的策略。最后討論的主要概念是拓?fù)渑判颍诮鉀Q應(yīng)用問題時(shí)它們十分有用。

本章的要點(diǎn)簡(jiǎn)述如下。

（1）主要要求理解圖的基本概念，包括圖的定義和術(shù)語、圖的連通性、圖的路徑和路徑長(zhǎng)度、圖中各頂點(diǎn)的度、無向連通圖和有向強(qiáng)連通圖的最大邊數(shù)和最小邊數(shù)、最小生成樹，以及拓?fù)渑判蚝妥疃搪窂降取?/p>

（2）掌握?qǐng)D的存儲(chǔ)表示，包括鄰接矩陣和鄰接表，以及這些存儲(chǔ)表示上的典型操作，如圖的構(gòu)造、插入和刪除頂點(diǎn)與邊、查找一個(gè)頂點(diǎn)的某一個(gè)鄰接頂點(diǎn)與鄰接邊等操作的實(shí)現(xiàn)算法。要求掌握?qǐng)D的兩種遍歷算法：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）算法，以及求解連通性問題的方法。

原文鏈接：https://blog.csdn.net/csdn_aiyang/java/article/details/85047153