軟件基礎(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〔隊

結(jié)

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

的Y

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

個

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

面IB鏈?zhǔn)酱鎯?/p>

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

N01

2011-7-4

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

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

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

其中：

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

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

例1：例2：

G1G2

2011-7-4

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

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

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

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

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

對，記為<v,w>,V,W是頂點，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是由兩個集合V(G)和E(G)組成的

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

E(G)是邊的有限集合，邊是頂點的無序?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個頂點的有向圖最大邊數(shù)是n(n?1)

&無向完全圖——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ù)語

&頂點的度

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

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

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

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

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

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

N072011-7-4

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

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

&頂點的度

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

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

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

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

卡對于具有n個頂點、e條邊的圖，頂點v的度TD(v)與頂點

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

e=(fTD(vi))/2

i=l

N082011-7-4

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

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

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

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

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

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

A回路——第一個頂點和最后一個頂點相同的路徑叫回路。

以簡單回路——除了第一個頂點和最后一個頂點外，其余頂點

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

路徑:25

例1,

度

路徑

長5

簡單

徑

路235

回路2563

?.

簡單1,

路

回3593

G1

N092011-7-4

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

&連通圖——圖中任意兩個頂點都是連通的叫連通圖。

&連通分量——非連通圖的每一個連通部分叫連通分量。

&強連通圖——有向圖中，如果對每一對ViWViwVj,從Vi到Vj

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

NO102011-7-4

?：.生成樹—連通圖G的生成樹是包含G中所有頂點的一個

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

特點：

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

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

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

連通圖GG的生成樹

N0112011-7-4

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

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

「圖中頂點的信息

圖的信息包括兩部分V

L邊或弧的信息

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

常用的存儲方式有：

①鄰接矩陣

②鄰接表

③十字鏈表

N0122011-7-4

一、鄰接矩陣

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

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

陣。

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

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

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

/憶刀=

o,其它

①②③④⑤

①0101o-

②10101

③01011

④10100

⑤01100

NO132011-7-4

一、鄰接矩陣

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

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

陣。

?:?定義：設(shè)G=(V,E)是有*1個頂點的圖，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

右鄰接矩陣的特點:

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

A鄰接矩陣A為對稱矩陣，可壓縮存儲；有n個頂點的無向

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

A第i行非0元素的個數(shù)為頂點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

*鄰接矩陣的特點：

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

A有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存

1諸空間為1；

A頂點Vi的出度是A中第i行元素之和;

＞頂點Vi的入度是A中第i列元素之和。

①②③④

①ro110

②0000

③0001

ID(1)=1@Li000

OD(1)=2

N0172011-7-4

右鄰接矩陣的特點：

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

A鄰接矩陣A為對稱矩陣，可壓縮存儲；有n個頂點的無向

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

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

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

A有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存

［諸空間為X；

＞頂點Vi的出度是A中第i行元素之和；

＞頂點Vi的入度是A中第i列元素之和。

?缺點：

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

N0182011-7-4

二、鄰接表

?:?鄰接表是一種順序存儲（頂點順序表）與鏈?zhǔn)酱鎯Γㄟ叺膯捂?/p>

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

typedefstructnode

{intadjvex;

structnode*next;

}JD;

adjvexnext

表頭接點：

typedefstructtnode

{intvdata;

vdatafirst

structnode*first;

}TD;

TDga[M];

N0192011-7-4

二、鄰接表

?:?鄰接表是一種順序存儲（頂點順序表）與鏈?zhǔn)酱鎯Γㄟ叺膯?/p>

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

vdatafirstadjvexnext

1a—24A

A

2b—1435

3c—2；45A

4

d—1.3A

5e—2.3A

NO202011-7-4

?:?特點

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

TD(a)=2

TD(b)=3

TD(c)=3

TD(d)=2

TD(e)=2

N0212011-7-4

二、鄰接表

?:?鄰接表是一種順序存儲（頂點順序表）與鏈?zhǔn)酱鎯Γㄟ叺膯?/p>

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

vdatafirstadjvexnext

a—32A

bA

c4A

d1A

NO222011-7-4

?:?特點

A有向圖中

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

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

OD(a)=2

OD(b)=0

0D(c)=1

0D(d)=1

NO232011-7-4

?:?特點

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

A有向圖中

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

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

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

例ID(a)=1vdatafirstadjvexnext

—A

ID(b)=1a4

ID(c)=1b1A

ID(d)=1c—1A

d—3A

NO242011-7-4

323圖的遍歷

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

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

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

所有和Vo相通的頂點都被訪問到；若此時圖中尚有頂點未

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

述過程，直至圖中所有頂點都被訪問為止。

例

假定從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）

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

問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接

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

點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問

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

程，直至圖中所有頂點都被訪問為止。

廣度遍歷：V1=>V2nV3=>

V4=>V5=>V6nV7=>V8

NO272011-7-4

廣度遍歷：VinV2nV3=>V4nV5nV6

nV7nV8

NO282011-7-4

6.4生成樹

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

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

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

圖的?

I?:?說明

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

?所有生成樹具有以下共同特點：0x70

來生成樹的頂點個數(shù)與圖的頂點個數(shù)相同T/

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

來一個有n個頂點的連通圖的生成樹有n?1條邊

來生成樹中任意兩個頂點間的路徑是唯一的

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

s”》含n個頂點面條邊的圖不一定是生成樹

NO292011.7.4

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

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

NO302011-7-4

例

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

N0312011-7-4

?:?最小生成樹

A問題提出

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

頂點——表示城市

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

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

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

問題分析

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

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

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

所有城市（頂點）均連起來，且總耗費

（各邊權(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中，找一條

代價最小的邊(uO,vO)

將(uO,vO)并入集合TE,同時vO并入U

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

為N的最小生成樹

NO332011-7-4

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

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

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

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

在E中選取代價最小的邊，若該邊依附的頂點落在T中不

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

邊，選取下一條代價最小的邊

依此類推，直至T中