軟件基礎(chǔ)第三章非線性數(shù)據(jù)結(jié)構(gòu)2

第三章非線性數(shù)據(jù)結(jié)構(gòu)

"線性表

「A線性結(jié)構(gòu)J棧

數(shù)

據(jù)&數(shù)據(jù)的邏輯結(jié)構(gòu)d〔隊(duì)

結(jié)

構(gòu)-B非線性結(jié)構(gòu)J樹形結(jié)構(gòu)

的Y

三［圖形結(jié)構(gòu)

個(gè)

方2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)［人順序存儲(chǔ)

面IB鏈?zhǔn)酱鎯?chǔ)

(3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。

N01

2011-7-4

3.2圖結(jié)構(gòu)

3.2.1圖的定義和術(shù)語

'圖(Graph)—圖G是由兩個(gè)集合V(G)和E(G)組成的，記為G=(V,E)

其中：

?:*V(G)是頂點(diǎn)的非空有限集

?:*E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?/p>

例1：例2：

G1G2

2011-7-4

3.2圖結(jié)構(gòu)

3.2.1圖的定義和術(shù)語

&有向圖——有向圖G是由兩個(gè)集合V(G)和E(G)組成的

其中：V(G)是頂點(diǎn)的非空有限集

E(G)是有向邊(也稱弧)的有限集合，弧是頂點(diǎn)的有序

對(duì)，記為<v,w>,V,W是頂點(diǎn)，V為弧尾，W為弧頭

例

圖G1中：

V(G1)={1,2,3,456}

E(G1)={<1,2>,<2,1>,<2,3>,<2,4>?<3,5>,<5,6>,<6,3>}

N032011-7-4

3.2圖結(jié)構(gòu)

3.2.1圖的定義和術(shù)語

'無向圖——無向圖G是由兩個(gè)集合V(G)和E(G)組成的

其中：V(G)是頂點(diǎn)的非空有限集

E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)Γ洖?v,w)

或(叫V),并且(v,w)=(w,v)的］

圖G2中：V(G2)={1,2,3,456,7}

E(G1尸{(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}

N042011-7-4

3.2圖結(jié)構(gòu)

3.2.1圖的定義和術(shù)語

；」有向完全圖----n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n?1)

&無向完全圖——n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2

例

有向完全圖無向完全圖

?權(quán)-----與圖的邊或弧相關(guān)的數(shù)據(jù)信息叫權(quán)。

。網(wǎng)圖------帶權(quán)的圖叫網(wǎng)圖。

N052011-7-4

3.2圖結(jié)構(gòu)

3.2.1圖的定義和術(shù)語

*子圖——如果圖G(V,E)和圖G，(V'E)滿足:

?V9oV

OE七E

則稱G，為G的子圖

圖與子圖

N062011-7-4

3.2圖結(jié)構(gòu)

3.2.1圖的定義和術(shù)語

&頂點(diǎn)的度

?:?無向圖中，頂點(diǎn)的度TD(Vi)為與Vi頂點(diǎn)相連的邊數(shù)

?:?有向圖中，頂點(diǎn)的度分成入度ID(V)與出度OD(V)

A入度ID(V)：以該頂點(diǎn)為頭的弧的數(shù)目

A出度OD(V)：以該頂點(diǎn)為尾的弧的數(shù)目

頂點(diǎn)5的度TD(5尸3頂點(diǎn)2入度ID(2)=1出度OD(2)=3

頂點(diǎn)2的度TD(2尸4頂點(diǎn)4入度ID(4)=1出度OD(4尸0

N072011-7-4

3.2圖結(jié)構(gòu)

3.2.1圖的定義和術(shù)語

&頂點(diǎn)的度

?:?無向圖中，頂點(diǎn)的度TD(Vi)為與Vi頂點(diǎn)相連的邊數(shù)

?:?有向圖中，頂點(diǎn)的度分成入度ID(V)與出度OD(V)

A入度ID(V)：以該頂點(diǎn)為頭的弧的數(shù)目

A出度OD(V)：以該頂點(diǎn)為尾的弧的數(shù)目

卡對(duì)于具有n個(gè)頂點(diǎn)、e條邊的圖，頂點(diǎn)v的度TD(v)與頂點(diǎn)

的個(gè)數(shù)以及邊的數(shù)目滿足關(guān)系：(書139頁有錯(cuò)，請(qǐng)改正)

e=(fTD(vi))/2

i=l

N082011-7-4

3.2圖結(jié)構(gòu)

3.2.1圖的定義和術(shù)語

&路徑——路徑是頂點(diǎn)的序列V={ViO,V“……Vin},滿足(VMM)￡E

或<Vw,Vij>￡E,(1<j?n)

及簡單路徑——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫簡單路徑。

&路徑長度——沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和。

A回路——第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫回路。

以簡單回路——除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)

不重復(fù)出現(xiàn)的回路叫簡單回路。

路徑:25

例1,

度

路徑

長5

簡單

徑

路235

回路2563

?.

簡單1,

路

回3593

G1

N092011-7-4

&連通——從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說V和W是連通的。

&連通圖——圖中任意兩個(gè)頂點(diǎn)都是連通的叫連通圖。

&連通分量——非連通圖的每一個(gè)連通部分叫連通分量。

&強(qiáng)連通圖——有向圖中，如果對(duì)每一對(duì)ViWViwVj,從Vi到Vj

和從Vj到Vi都存在路徑，則稱G是強(qiáng)連通圖。

NO102011-7-4

?：.生成樹—連通圖G的生成樹是包含G中所有頂點(diǎn)的一個(gè)

極小連通子圖，它有且僅有面條邊。

特點(diǎn)：

1）任意兩頂點(diǎn)間有且僅有一條路經(jīng)

2）在生成樹中添加任意一條屬于G的邊必定會(huì)產(chǎn)生回路

3）若生成樹中減少任意一條邊，則必然成為非連通圖

連通圖GG的生成樹

N0112011-7-4

3.2圖結(jié)構(gòu)

3.2.2圖的存儲(chǔ)結(jié)構(gòu)

「圖中頂點(diǎn)的信息

圖的信息包括兩部分V

L邊或弧的信息

圖的存儲(chǔ)結(jié)構(gòu)應(yīng)完整、準(zhǔn)確地反映這兩部分信息。

常用的存儲(chǔ)方式有：

①鄰接矩陣

②鄰接表

③十字鏈表

N0122011-7-4

一、鄰接矩陣

鄰接矩陣存儲(chǔ)結(jié)構(gòu)是用一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，用

矩陣表示圖中各頂點(diǎn)的鄰接關(guān)系——表示頂點(diǎn)間相聯(lián)關(guān)系的矩

陣。

?:?定義：設(shè)G=(V,E)是有侖1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具

有以下性質(zhì)的n階方陣：

1,若Vj)或<vi?Vj>eE(G)

/憶刀=

o,其它

①②③④⑤

①0101o-

②10101

③01011

④10100

⑤01100

NO132011-7-4

一、鄰接矩陣

鄰接矩陣存儲(chǔ)結(jié)構(gòu)是用一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，用

矩陣表示圖中各頂點(diǎn)的鄰接關(guān)系——表示頂點(diǎn)間相聯(lián)關(guān)系的矩

陣。

?:?定義：設(shè)G=(V,E)是有*1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具

有以下性質(zhì)的n階方陣：

1,若(v「Vj)或<vi9v.>eE(G)

①②③④

N0142011-7-4

?:?若G=(V,E)是網(wǎng)圖，貝IJG的鄰接矩陣的元素值為邊的權(quán)值。

%，(Vi，Vj),VVj>eE(G)

/必力=

00，其它

①②③④⑤

例

①0057oo3一

②5000048

③700821

④0042006

⑤L381600

N0152011-7-4

右鄰接矩陣的特點(diǎn):

?:?若G為無向圖，貝ij：

A鄰接矩陣A為對(duì)稱矩陣，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無向

圖需存儲(chǔ)空間為n(n+1)/2；

A第i行非0元素的個(gè)數(shù)為頂點(diǎn)Vi的度，TD(Vi)

①②③④⑤

①「o10101

②10101

③01011

TD(1)=2④10100

TD(2)=3⑤Lo1100

TD(3)=3

TD(4)=2

TD(5)=2

N0162011-7-4

*鄰接矩陣的特點(diǎn)：

?:?若G為有向圖，則:

A有向圖鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存

1諸空間為1；

A頂點(diǎn)Vi的出度是A中第i行元素之和;

＞頂點(diǎn)Vi的入度是A中第i列元素之和。

①②③④

①ro110

②0000

③0001

ID(1)=1@Li000

OD(1)=2

N0172011-7-4

右鄰接矩陣的特點(diǎn)：

?:?若G為無向圖，貝IJ：

A鄰接矩陣A為對(duì)稱矩陣，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無向

圖需存儲(chǔ)空間為n(n+1)/2；

A第i行非0元素的個(gè)數(shù)為頂點(diǎn)Vi的度，TD(Vi)o

?:?若G為有向圖，貝IJ：

A有向圖鄰接矩陣不一定對(duì)稱；有n個(gè)頂點(diǎn)的有向圖需存

［諸空間為X；

＞頂點(diǎn)Vi的出度是A中第i行元素之和；

＞頂點(diǎn)Vi的入度是A中第i列元素之和。

?缺點(diǎn)：

統(tǒng)計(jì)圖中邊的總數(shù)時(shí)，需按行按列逐個(gè)檢測、代價(jià)大。

N0182011-7-4

二、鄰接表

?:?鄰接表是一種順序存儲(chǔ)（頂點(diǎn)順序表）與鏈?zhǔn)酱鎯?chǔ)（邊的單鏈

表）結(jié)合的存儲(chǔ)方法，類似于樹的孩子鏈表表示法。

typedefstructnode

{intadjvex;

structnode*next;

}JD;

adjvexnext

表頭接點(diǎn)：

typedefstructtnode

{intvdata;

vdatafirst

structnode*first;

}TD;

TDga[M];

N0192011-7-4

二、鄰接表

?:?鄰接表是一種順序存儲(chǔ)（頂點(diǎn)順序表）與鏈?zhǔn)酱鎯?chǔ)（邊的單

鏈表）結(jié)合的存儲(chǔ)方法，類似于樹的孩子鏈表示法。

vdatafirstadjvexnext

1a—24A

A

2b—1435

3c—2；45A

4

d—1.3A

5e—2.3A

NO202011-7-4

?:?特點(diǎn)

A無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)

TD(a)=2

TD(b)=3

TD(c)=3

TD(d)=2

TD(e)=2

N0212011-7-4

二、鄰接表

?:?鄰接表是一種順序存儲(chǔ)（頂點(diǎn)順序表）與鏈?zhǔn)酱鎯?chǔ)（邊的單

鏈表）結(jié)合的存儲(chǔ)方法，類似于樹的孩子鏈表示法。

vdatafirstadjvexnext

a—32A

bA

c4A

d1A

NO222011-7-4

?:?特點(diǎn)

A有向圖中

來頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)；

來頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)。

OD(a)=2

OD(b)=0

0D(c)=1

0D(d)=1

NO232011-7-4

?:?特點(diǎn)

A無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)；

A有向圖中

來頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)；

來頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù)。

I逆鄰接表：有向圖中對(duì)每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表。

例ID(a)=1vdatafirstadjvexnext

—A

ID(b)=1a4

ID(c)=1b1A

ID(d)=1c—1A

d—3A

NO242011-7-4

323圖的遍歷

一、深度優(yōu)先遍歷(DFS)

?:?方法：從圖的某一頂點(diǎn)Vo出發(fā)，訪問此頂點(diǎn)；然后依次從

Vo的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中

所有和Vo相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未

被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上

述過程，直至圖中所有頂點(diǎn)都被訪問為止。

例

假定從V1出發(fā)，遍歷次序如何?

深度遍歷:V?:nV4nV8-5^V3^V6^V7

NO252011-7-4

例

深度遍歷：vx=>v2=>v4V8=>V5=>v6=>v3=>V7

NO262011-7-4

3.2.3圖的遍歷

二、廣度優(yōu)先遍歷（BFS）

方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪

問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接

點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂

點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問

,則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過

程，直至圖中所有頂點(diǎn)都被訪問為止。

廣度遍歷：V1=>V2nV3=>

V4=>V5=>V6nV7=>V8

NO272011-7-4

廣度遍歷：VinV2nV3=>V4nV5nV6

nV7nV8

NO282011-7-4

6.4生成樹

I?:?定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫?

I?:?深度優(yōu)先生成樹與廣度優(yōu)先生成樹

I?:?生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通

圖的?

I?:?說明

A一個(gè)圖可以有許多棵不同的生成樹?

?所有生成樹具有以下共同特點(diǎn)：0x70

來生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同T/

來生成樹是圖的極小連通子圖@

來一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n?1條邊

來生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的

來在生成樹中再加一條邊必然形成回路

s”》含n個(gè)頂點(diǎn)面條邊的圖不一定是生成樹

NO292011.7.4

廣度優(yōu)先生成樹

深度優(yōu)先生成樹

NO302011-7-4

例

B深度優(yōu)先生成森林

N0312011-7-4

?:?最小生成樹

A問題提出

要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，

頂點(diǎn)——表示城市

權(quán)—城市間建立通信線路所需花費(fèi)代價(jià)

希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立

該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小-----最小代價(jià)生成樹

問題分析

n個(gè)城市間，最多可設(shè)置n（n?l）/2條線路

n個(gè)城市間建立通信網(wǎng)，只需n?l條線路

問題轉(zhuǎn)化為：如何在可能的線路中選擇n?l條，能把

所有城市（頂點(diǎn)）均連起來，且總耗費(fèi)

（各邊權(quán)值之和）最小

NO322011-7-4

A構(gòu)造最小生成樹方法

來方法一：普里姆(Prim)算法

》算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上

最小生成樹中邊的集合

初始令U={llo},(UowV),TE=O>

在所有U￡U,V￡V?U的邊(U,V)￡E中，找一條

代價(jià)最小的邊(uO,vO)

將(uO,vO)并入集合TE,同時(shí)vO并入U(xiǎn)

重復(fù)上述操作直至U=V為止，貝|JT=(V,{TE})

為N的最小生成樹

NO332011-7-4

崇方法二：克魯斯卡爾(Kruskal)算法

》算法思想：設(shè)連通網(wǎng)N=(V,{E}),令最小生成樹

初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖

T=(V,{<D}),每個(gè)頂點(diǎn)自成一個(gè)連通分量

在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不

同的連通分量上，則將此邊加入到T中；否則，舍去此

邊，選取下一條代價(jià)最小的邊

依此類推，直至T中