大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第六章：圖-第一節(jié)-圖的基本定義和術(shù)語(yǔ)

本章概覽

一、知識(shí)結(jié)構(gòu)

f圖的定義和基本術(shù)語(yǔ)

鄰接矩陣表示法

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

鄰接表表示法

深度優(yōu)先搜索遍歷

圖圖的遍歷Y

廣度優(yōu)先搜索遍歷

圖的生成樹(shù)和最小生成樹(shù)

最短路徑

I拓?fù)渑判?/p>

二、本章重難點(diǎn)

本章重點(diǎn)是圖的兩種存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)及其遍歷算法。本章難點(diǎn)是求

最小生成樹(shù)的基本思想和算法，求最短路徑的基本思想及算法，只要

求考生能讀懂這些算法并能進(jìn)行性能分析，不要求更深層次的應(yīng)用。

第一節(jié)圖的基本定義和術(shù)語(yǔ)

當(dāng)前講授

一、圖的定義

圖是由頂點(diǎn)的非空有窮集合（用v表示該集合）與頂點(diǎn)之間的關(guān)系

（邊或?。┑募希ㄓ肊表示該集合）構(gòu)成的結(jié)構(gòu)。

可以形式化表示為G=（V,E）

其中，V為頂點(diǎn)的非空有窮集合，E為關(guān)系的有窮集合。

對(duì)于圖中任意一條邊(Vi,Vj)，若(Vi,Vj)是頂點(diǎn)的無(wú)序偶

對(duì)，這樣的圖稱(chēng)為無(wú)向圖。若(Vi,Vj)是頂點(diǎn)的有序偶對(duì)，記作

<Vi,Vj>,這樣的圖稱(chēng)為有向圖。直觀地判斷，無(wú)向圖中的所有邊都

不帶有箭頭，而有向圖中的所有邊(習(xí)慣稱(chēng)之為弧)都帶有箭頭。

邊上帶權(quán)的圖稱(chēng)為帶權(quán)圖，帶權(quán)的連通圖稱(chēng)為網(wǎng)絡(luò)。

二、圖的有關(guān)名詞術(shù)語(yǔ)

(1)頂點(diǎn)的度：所謂某個(gè)頂點(diǎn)V的度是指依附于該頂點(diǎn)的邊或弧

的數(shù)量，記為D(V)。對(duì)于無(wú)向圖而言，僅此而已。而對(duì)于有向

圖，要區(qū)分頂點(diǎn)的出度與入度的概念。所謂一個(gè)頂點(diǎn)V的出度是指以

該頂點(diǎn)為出發(fā)點(diǎn)的弧的數(shù)量，記為0D(V)。所謂一個(gè)頂點(diǎn)V的入度

是指以該頂點(diǎn)為終止點(diǎn)的弧的數(shù)量，記為ID(V)。D(V)=0D

(V)+ID(V)O

結(jié)論：①所有頂點(diǎn)的度之和等于邊或弧的條數(shù)2倍。

②具有n個(gè)頂點(diǎn)的無(wú)向圖中邊的數(shù)目最多為n(n-1)/2,

具有n個(gè)頂點(diǎn)的有向圖中邊(弧)的數(shù)目最多為n(n-l)o

(2)路徑：頂點(diǎn)Vx與Vy之間有路徑是指存在著頂點(diǎn)序列Vx,

Vil,Vi2，…，Vy,并且序列中相鄰兩個(gè)元素構(gòu)成的頂點(diǎn)偶對(duì)分別表

示圖中的一條邊或弧。這里，稱(chēng)Vx為出發(fā)點(diǎn)，Vy為終止點(diǎn)，出發(fā)點(diǎn)

與終止點(diǎn)相同的路徑稱(chēng)為環(huán)或回路。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱(chēng)

為簡(jiǎn)單路徑。

對(duì)于不帶權(quán)的圖，兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度是指該路徑上所經(jīng)過(guò)的

邊的數(shù)目。對(duì)于帶權(quán)的圖，兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度是指該路徑上所

經(jīng)過(guò)的邊上的權(quán)值之和。

(3)子圖：對(duì)于圖G=(V,E)與G'=(V,，E')，若有V'￡V,

E'GE,則稱(chēng)G'是G的一個(gè)子圖。一個(gè)圖是其自身的子圖。

(4)圖的連通

無(wú)向圖的連通：若頂點(diǎn)Vx與Vy之間有路徑，就稱(chēng)Vx與Vy是連

通的。若圖中任意兩個(gè)頂點(diǎn)之間都有路徑，就稱(chēng)該無(wú)向圖是連通的。

有向圖的連通：若頂點(diǎn)Vx與Vy之間有路徑,并且頂點(diǎn)Vy與Vx

之間也有路徑，就稱(chēng)Vx與Vy是連通的。若圖中任意兩個(gè)頂點(diǎn)之間都

有連通，就稱(chēng)該有向圖是強(qiáng)連通的。

連通有向圖非連通有向圖

連通分量：無(wú)向圖中的極大連通子圖。任何一個(gè)連通圖的的連通分

量只有一個(gè)，是它本身。

強(qiáng)連通分量：有向圖中的極大連通子圖。

（例題?單選題）在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂

點(diǎn)至少需要（）條邊。

A.nB.n+1C.n-1D.2n

隱藏答案

【答案】C

【解析】用n-1條邊就可以將n個(gè)頂點(diǎn)串起來(lái)形成無(wú)向連通圖。

（例題?單選題）在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，要連通全部頂

點(diǎn)至少需要（）條邊。

A.nB.n+1