1、數(shù) 據(jù) 結(jié) 構(gòu)第三十八課 圖的定義與術(shù)語,第三十課 圖的定義與術(shù)語,本課主題： 圖的定義與術(shù)語 教學(xué)目的： 掌握圖的定義及常用術(shù)語 教學(xué)重點(diǎn)： 圖的常用術(shù)語 教學(xué)難點(diǎn)： 圖的常用術(shù)語 授課內(nèi)容：,一、圖的定義,圖是一種數(shù)據(jù)元素間為多對多關(guān)系的數(shù)據(jù)結(jié)構(gòu)，加上一組基本操作構(gòu)成的抽象數(shù)據(jù)類型。,圖的抽象數(shù)據(jù)類型定義(1),ADT Graph 數(shù)據(jù)對象V ：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。 數(shù)據(jù)關(guān)系R：R=VR VR=|v,wV且P(v,w),表示從v到w的弧， 謂詞P(v,w)定義了弧的意義或信息 基本操作P： CreateGraph( 初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。

2、操作結(jié)果：按V和VR的定義構(gòu)造圖G,圖的抽象數(shù)據(jù)類型定義(2),DestroyGraph( 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn) 操作結(jié)果：返回v的值。,FirstAdjVex(G,v); 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn) 操作結(jié)果：返回v的第一個(gè)鄰接頂點(diǎn)。若頂點(diǎn)在G中沒有鄰接 頂點(diǎn)，則返回“空” PutVex( 初始條件：圖G存在,v是G中某個(gè)頂點(diǎn),w是v的鄰接頂點(diǎn)。 操作結(jié)果：返回v的（相對于w的）下一個(gè)鄰接頂點(diǎn)。若w是v的 最后一個(gè)鄰接點(diǎn)，則返回“空”,圖的抽象數(shù)據(jù)類型定義(3),InsertVex( 初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn) 操作結(jié)果：在G中增添弧,若G是無向的，則

3、還增添對稱弧,圖的抽象數(shù)據(jù)類型定義(4),DeleteArc( 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，Visit是頂點(diǎn)的應(yīng)用函 數(shù) 操作結(jié)果：從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次。一旦Visit()失敗，則操作失敗。,圖的抽象數(shù)據(jù)類型定義(5),BFSTRaverse(G,v,Visit(); 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，Visit是頂點(diǎn)的應(yīng)用函數(shù) 操作結(jié)果：從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次。一旦Visit()失敗，則操作失敗。 ADT Graph,圖的抽象數(shù)據(jù)類型定義(6),二、圖的常用術(shù)語(1),有向圖、無向圖 ?。? 邊

4、(x,y)。,二、圖的常用術(shù)語(2),對于無向圖，e的取值范圍是0到n(n-1)/2, 有n(n-1)/2條邊的無向圖稱為無向完全圖。,如果用n表示圖中頂點(diǎn)數(shù)目，用e表示邊或弧的數(shù)目， 則有：,二、圖的常用術(shù)語(3),對于有向圖，e有取值范圍是0到n(n-1)。 具有n(n-1)條弧的有向圖稱為有向完全圖。,二、圖的常用術(shù)語(4),有很少條邊或弧的圖稱為稀疏圖，反之稱為稠密圖。,二、圖的常用術(shù)語(5),和邊（?。┫嚓P(guān)的數(shù)叫權(quán) 帶權(quán)的圖稱網(wǎng)。 鄰接、鄰接點(diǎn) 無向圖中, 一條邊連起來的兩個(gè)頂點(diǎn)，互稱鄰接點(diǎn)； 有向圖中,若從頂點(diǎn)x到頂點(diǎn)y有一條弧，則說頂點(diǎn)x鄰接到頂點(diǎn)y，而頂點(diǎn)y鄰接自頂點(diǎn)x。,對上

5、圖有：G1=(V1,A1) 其中：V1=v1,v2,v3,v4 A1=,二、圖的常用術(shù)語(6),二、圖的常用術(shù)語(7),度、出度、入度 無向圖中和頂點(diǎn)相關(guān)的邊(e)的個(gè)數(shù)叫頂點(diǎn)的度。 有向圖中從頂點(diǎn)出發(fā)的弧的個(gè)數(shù)叫該頂點(diǎn)的出度，入到該頂點(diǎn)的弧的個(gè)數(shù)叫該頂點(diǎn)的入度。TD(v)=ID(v)+OD(v),二、圖的常用術(shù)語(8),路徑、路徑長度、回路(環(huán))、簡單路徑 連通、連通圖、連通分量 無向圖頂點(diǎn)v1到頂點(diǎn)v2有路徑，則說v1和v2連通。若任意兩個(gè)頂點(diǎn)都連通，則說該圖是連通的。連通分量是無向圖中的極大連通子圖。 強(qiáng)連通圖、強(qiáng)連通分量,二、圖的常用術(shù)語(9),二、圖的常用術(shù)語(10),對有向圖，如果每一對頂點(diǎn)之間都有通路，則稱該圖 為強(qiáng)連通圖。,二、圖的常用術(shù)語(11),生成樹、有向樹、生成森林 一個(gè)連通圖的生成樹是一個(gè)極小連通子圖，它含有圖的全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。 若有向圖中只有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則該有向圖稱為有向