




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
第三章非線性數(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中
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025屆四川省雙流藝體中學(xué)高一化學(xué)第二學(xué)期期末學(xué)業(yè)水平測試試題含解析
- 2025屆云南省曲靖市羅平縣一中化學(xué)高二下期末監(jiān)測模擬試題含解析
- 山西省孝義市2025屆化學(xué)高二下期末聯(lián)考模擬試題含解析
- 2025屆上海市上海交大附中高一化學(xué)第二學(xué)期期末復(fù)習(xí)檢測試題含解析
- 2025屆山東省蓬萊第二中學(xué)化學(xué)高二下期末學(xué)業(yè)質(zhì)量監(jiān)測試題含解析
- 吉林省舒蘭一中2025屆化學(xué)高一下期末復(fù)習(xí)檢測模擬試題含解析
- 湖北省當(dāng)陽市第二高級中學(xué)2025屆高一下化學(xué)期末達(dá)標(biāo)檢測試題含解析
- 福建泉州市2025年高二下化學(xué)期末達(dá)標(biāo)檢測試題含解析
- 機耕道路維護(hù)管理辦法
- 內(nèi)部成員沖突管理辦法
- 小兒腸梗阻護(hù)理課件
- 2024-2025學(xué)年譯林版新七年級英語上冊Unit2《Hobbies》單元卷(含答案解析)
- 遼寧省大連市甘井子區(qū)2023-2024學(xué)年七年級下學(xué)期期末生物學(xué)試題(原卷版)
- 5國家機構(gòu)有哪些 第一課時(教學(xué)設(shè)計)部編版道德與法治六年級上冊
- 實驗室生物安全手冊
- AQ/T 1118-2021 礦山救援培訓(xùn)大綱及考核規(guī)范(正式版)
- 2024屆甘南市語文八年級第二學(xué)期期末聯(lián)考試題含解析
- 無人機航空測繪與后期制作 課件 第十二課時 現(xiàn)場飛行流程
- 2024年梅州市大埔縣重點中學(xué)小升初語文入學(xué)考試卷含答案
- 2022-2023學(xué)年北京市東城區(qū)高二(下)期末化學(xué)試卷(含解析)
- 防溺水老師培訓(xùn)課件
評論
0/150
提交評論