通信原理大綜合課件軟件

在此幻燈片插入公司的徽標(biāo)從“插入”菜單選擇圖片找到徽標(biāo)文件單擊“確定”重新設(shè)置徽標(biāo)大小單擊徽標(biāo)內(nèi)任意位置?；諛?biāo)外部出現(xiàn)的方框是“調(diào)整控點(diǎn)”使用這些重新設(shè)置對(duì)象大小如果在使用尺寸調(diào)整控點(diǎn)前按下shift鍵，則對(duì)象改變大小但維持原比例。DATA1065865姓名學(xué)號(hào)成績(jī)班級(jí)李紅976105995機(jī)97.6ABCDEFG數(shù)據(jù)結(jié)構(gòu)2024/10/1622.6圖圖是一種非線性的數(shù)據(jù)結(jié)構(gòu)，結(jié)點(diǎn)之間的關(guān)系可以是任意的。圖中任意兩個(gè)元素之間都可能相關(guān)。2.6.1圖的基本概念2.6.2圖的存儲(chǔ)結(jié)構(gòu)

（1）圖的鄰接矩陣表示法（2）圖的鄰接表表示法2.6.3圖的遍歷

2024/10/163圖定義

圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：

Graph＝(V,E)

其中

V={x|x

某個(gè)數(shù)據(jù)對(duì)象}是頂點(diǎn)的有窮非空集合；

E={(x,y)|x,y

V}

是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。2024/10/164若<v,w>∈VR,則<v,w>表示從v到w的一條弧，且稱v為弧尾或初始點(diǎn),稱w為弧頭或終端點(diǎn),此時(shí)的圖稱為有向圖.V1V3V2V4V1V3V2V4弧的集合G={<V1

，V3>,<V3

，V4>,<V2

，V4>,<V4，V1>}若<v,w>∈VR，必有<w,v>∈VR，即VR是對(duì)稱的，則以無(wú)序?qū)Γ╲,w）代替這兩個(gè)有序?qū)?，表示v和w之間的一條邊，此時(shí)的圖稱為無(wú)向圖。邊的集合E={(V1,V3),(V1,V2),(V1,V4),(V2,V4)}具有邊的圖，稱做無(wú)向圖，而具有弧的圖，稱做有向圖。注意：在無(wú)向圖中，(x,y)與(y,x)表示同一條邊在有向圖中，<x,y>與<y,x>表示不同的弧2024/10/165假定圖的頂點(diǎn)數(shù)為n,那么具有n(n-1)/2條邊的圖為無(wú)向完全圖具有n(n-1)條弧的圖為有向完全圖V3V1V2V4V1V2V3V42024/10/166圖的一部分或自身都可稱為圖的子圖(Subgraph)。V3V4V1V3V1V2V4V1V2V4V1V2V4V1V2V3V4V1V1V3V1V3V2V4V1V3V2V42024/10/167V1V3V2V4V1V3V2V4度:依附于該頂點(diǎn)的邊數(shù)或弧數(shù)。出度和入度僅對(duì)有向圖而言，出度是指以該頂點(diǎn)為尾的弧數(shù)，

入度是指以該頂點(diǎn)為頭的弧數(shù)。2024/10/168在無(wú)向圖G=(V,E)中,如果存在頂點(diǎn)序列(Vp,Vi1,Vi2,...,Vin,Vq）使得(VP,Vi1),(Vi1,Vi2)，…，(Vin,Vq)都在E中，則稱從頂點(diǎn)VP到Vq存在一條路徑。若G是有向圖，則路徑也是有向的,即<VP,Vi1>,<Vi1，,Vi2>,…,<Vin,Vq>都在E中,VP為路徑的起點(diǎn)，Vq為路徑的終點(diǎn)。路徑上邊或弧的數(shù)目稱為該路徑的路徑長(zhǎng)度起點(diǎn)和終點(diǎn)相同的路徑稱為回路或環(huán)

頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。除了起點(diǎn)和終點(diǎn)相同外,其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路。V1V3V2V4V1V3V2V42024/10/169連通圖：對(duì)無(wú)向圖G而言,如果從Vi到Vj有路徑，則稱Vi到Vj是連通的。若圖中任意兩個(gè)頂點(diǎn)Vi和Vj(Vi≠Vj)都連通，則稱G是連通圖。一個(gè)無(wú)向圖的各連通分量定義為該圖的各個(gè)最大連通子圖。V1V2V3V4V5V6V1V2V3V4V5V6(a)無(wú)向圖G3(b)G3的兩個(gè)連通分量

對(duì)有向圖G而言，若任意兩個(gè)頂點(diǎn)Vi和Vj(Vi≠Vj)，都有一條從Vi至Vj

的路徑，同時(shí)還有一條從Vj

到Vi的路徑,則稱該有向圖為強(qiáng)連通圖，有向圖的各個(gè)極大強(qiáng)連通子圖稱作該有向圖的各個(gè)強(qiáng)連通分量。V2V3V1V4V1V3V2V42024/10/1610如果一個(gè)圖有n個(gè)頂點(diǎn)和小于n-1條邊，則是非連通圖。如果一個(gè)圖多于n-1條邊，則一定有環(huán)。2024/10/1611V1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010

V20001

V30001

V41000

V1V2V3V4

V1

0111

V21001

V31000

V41100圖的鄰接矩陣表示法是否唯一無(wú)向圖完全圖2024/10/1612V1V3V2V4V1V3V2V4432121∧113∧4∧4∧2圖的鄰接表表示法∧1∧3∧44321∧4是否唯一2024/10/1613鄰接表的形式說(shuō)明typedefstructnode{//表結(jié)點(diǎn)

intadjvex；

structnode*next；

//若要表示權(quán)值，則增加一個(gè)數(shù)據(jù)域

}EdgeNode;

typedefstructvnode{//表頭結(jié)點(diǎn)

VertexTypevertex；

EdgeNode*firstedge；//邊表頭指針

}VertexNode；頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)2024/10/16142．6．3圖的遍歷(深度優(yōu)先和廣度優(yōu)先兩種方式)圖的遍歷是指從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次的過(guò)程。由于圖中可能存在回路，容易造成頂點(diǎn)被重復(fù)訪問，為此設(shè)置一個(gè)輔助數(shù)組visited[0..n-1],初始值為“0”或“假”，當(dāng)頂點(diǎn)vi被訪問后，將visited[i]置為“真”或被訪問時(shí)的次序號(hào)。2024/10/16151.深度優(yōu)先遍歷（DFS)

深度優(yōu)先遍歷是從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪問此結(jié)點(diǎn)，然后選擇一個(gè)與V0相鄰且未被訪問過(guò)的頂點(diǎn)Vi訪問，再?gòu)腣i出發(fā)選擇一個(gè)與Vi相鄰且未被訪問的頂點(diǎn)Vj訪問，...，如果當(dāng)前被訪問的頂點(diǎn)的所有鄰接點(diǎn)都已被訪問，則退回到已被訪問的頂點(diǎn)序列中最后一個(gè)擁有未被訪問的相鄰頂點(diǎn)的w，從w出發(fā)按同樣的方式向前搜索，直至圖中所有連通的頂點(diǎn)都被訪問。如果圖中還有頂點(diǎn)未被訪問，那么再?gòu)倪@些未被訪問的頂點(diǎn)中的某個(gè)出發(fā)，按深度優(yōu)先方式遍歷，…，直至圖中所有頂點(diǎn)都被訪問。fbcdeagh從頂點(diǎn)a出發(fā)的可能次序?yàn)?/p>

abcdefghabecdfhg...等多種序列。2024/10/1616

2.廣度優(yōu)先遍歷（BFS）廣度優(yōu)先遍歷是指從圖中某個(gè)頂點(diǎn)v0出發(fā)，在訪問了v0之后依次訪問v0的各個(gè)未曾訪問的鄰接點(diǎn)，然后再依次從這些鄰接點(diǎn)出發(fā)廣度優(yōu)先遍歷圖，直到圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)圖中還有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)做起始點(diǎn),重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問到為止。fbcdeagh例如，從a頂點(diǎn)出發(fā)訪問右圖,那么可以得到

abfceghdafbghced...等多種序列。2024/10/16172．6．4最小生成樹對(duì)于一個(gè)連通圖，無(wú)論是深度優(yōu)先遍歷和廣度優(yōu)先遍歷，最終必然所有頂點(diǎn)都被訪問到，且在遍歷過(guò)程中一定要經(jīng)過(guò)一些邊，把這些頂點(diǎn)，用經(jīng)過(guò)的邊連起來(lái)就是生成樹。fbcdeaghfbcdeaghfbcdeagh(a)(b)深度優(yōu)先生成樹(c)廣度優(yōu)先生成樹如果連通圖G的一個(gè)子圖是一棵包含G的所有頂點(diǎn)的樹，則該子圖稱為G的生成樹(SpanningTree)。2024/10/1618圖的生成樹不惟一，從不同的頂點(diǎn)出發(fā)進(jìn)行遍歷，可以得到不同的生成樹。一顆有n個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊。如果在生成樹上添加一條邊，必定構(gòu)成環(huán)。

有時(shí)圖的邊或弧具有與它相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)，這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。這種帶權(quán)的圖通常稱做網(wǎng)。2024/10/1619生成樹中最有意義的問題是：

在n個(gè)城市之間建立通訊網(wǎng)絡(luò)，如果每?jī)蓚€(gè)城市之間都設(shè)置一條線路，最多可設(shè)置n(n-1)/2條線路，而實(shí)際上只需要n-1條線路即可連通這n個(gè)城市。由于每條線路所付出的經(jīng)濟(jì)代價(jià)是不同的，如何在所有可能的線路中選擇n-1條線路，使總的耗費(fèi)最小，即是構(gòu)造連通網(wǎng)的最小代價(jià)生成樹（簡(jiǎn)稱最小生成樹〕問題。普里姆算法的思想是：從頂點(diǎn)集合和邊集合為空開始，從圖的任一頂點(diǎn)選起，把這個(gè)頂點(diǎn)加入到頂點(diǎn)集合中,然后選取依附于該頂點(diǎn)的權(quán)值最小的邊，加入到邊集合中，通過(guò)該邊又得到一個(gè)頂點(diǎn)，把這個(gè)頂點(diǎn)也加入集合中，然后再通過(guò)這兩個(gè)頂點(diǎn)選取不構(gòu)成回路的、權(quán)值最小的、其依附的另外一個(gè)頂點(diǎn)不在新建的頂點(diǎn)集合中的頂點(diǎn)，把這個(gè)頂點(diǎn)和邊也加入到集合中，……，直到n個(gè)頂點(diǎn)和n-