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

本章概覽

一、知識結構

f圖的定義和基本術語

鄰接矩陣表示法

圖的存儲結構《

鄰接表表示法

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

圖圖的遍歷Y

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

圖的生成樹和最小生成樹

最短路徑

I拓撲排序

二、本章重難點

本章重點是圖的兩種存儲結構的實現(xiàn)及其遍歷算法。本章難點是求

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

求考生能讀懂這些算法并能進行性能分析，不要求更深層次的應用。

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

當前講授

一、圖的定義

圖是由頂點的非空有窮集合（用v表示該集合）與頂點之間的關系

（邊或?。┑募希ㄓ肊表示該集合）構成的結構。

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

其中，V為頂點的非空有窮集合，E為關系的有窮集合。

對于圖中任意一條邊(Vi,Vj)，若(Vi,Vj)是頂點的無序偶

對，這樣的圖稱為無向圖。若(Vi,Vj)是頂點的有序偶對，記作

<Vi,Vj>,這樣的圖稱為有向圖。直觀地判斷，無向圖中的所有邊都

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

邊上帶權的圖稱為帶權圖，帶權的連通圖稱為網(wǎng)絡。

二、圖的有關名詞術語

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

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

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

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

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

(V)+ID(V)O

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

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

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

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

Vil,Vi2，…，Vy,并且序列中相鄰兩個元素構成的頂點偶對分別表

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

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

為簡單路徑。

對于不帶權的圖，兩個頂點之間的路徑長度是指該路徑上所經(jīng)過的

邊的數(shù)目。對于帶權的圖，兩個頂點之間的路徑長度是指該路徑上所

經(jīng)過的邊上的權值之和。

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

E'GE,則稱G'是G的一個子圖。一個圖是其自身的子圖。

(4)圖的連通

無向圖的連通：若頂點Vx與Vy之間有路徑，就稱Vx與Vy是連

通的。若圖中任意兩個頂點之間都有路徑，就稱該無向圖是連通的。

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

之間也有路徑，就稱Vx與Vy是連通的。若圖中任意兩個頂點之間都

有連通，就稱該有向圖是強連通的。

連通有向圖非連通有向圖

連通分量：無向圖中的極大連通子圖。任何一個連通圖的的連通分

量只有一個，是它本身。

強連通分量：有向圖中的極大連通子圖。

（例題?單選題）在一個具有n個頂點的無向圖中，要連通全部頂

點至少需要（）條邊。

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

隱藏答案

【答案】C

【解析】用n-1條邊就可以將n個頂點串起來形成無向連通圖。

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

點至少需要（）條邊。

A.nB.n+1