通信原理大綜合課件軟件

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

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

2024/10/163圖定義

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

Graph＝(V,E)

其中

V={x|x

某個數(shù)據(jù)對象}是頂點的有窮非空集合；

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

V}

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

，V3>,<V3

，V4>,<V2

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

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

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

對有向圖G而言，若任意兩個頂點Vi和Vj(Vi≠Vj)，都有一條從Vi至Vj

的路徑，同時還有一條從Vj

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

V1V2V3V4

V1

0010

V20001

V30001

V41000

V1V2V3V4

V1

0111

V21001

V31000

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

intadjvex；

structnode*next；

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

}EdgeNode;

typedefstructvnode{//表頭結(jié)點

VertexTypevertex；

EdgeNode*firstedge；//邊表頭指針

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

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

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

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

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

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

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