資源描述：
《數(shù)據(jù)結(jié)構(gòu)第7章圖1圖的定義和術(shù)語.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、數(shù)據(jù)結(jié)構(gòu)DataStructures張凱計算機(jī)學(xué)院軟件工程系2011年3月12日圖的連通性問題第7章圖圖的定義和術(shù)語圖的存儲結(jié)構(gòu)圖的遍歷有向無環(huán)圖及其應(yīng)用最短路徑基本術(shù)語§7.1圖的定義和術(shù)語有向圖：圖G中的每條邊都是有方向的；基本術(shù)語§7.1圖的定義和術(shù)語無向圖：圖G中的每條邊都是無方向的基本術(shù)語§7.1圖的定義和術(shù)語完全圖：圖G任意兩個頂點(diǎn)都有一條邊相連接；若n個頂點(diǎn)的無向圖有n(n-1)/2條邊,稱為無向完全圖基本術(shù)語§7.1圖的定義和術(shù)語完全圖：圖G任意兩個頂點(diǎn)都有一條邊相連接；若n個頂點(diǎn)的有向
2、圖有n(n-1)條邊,稱為有向完全圖基本術(shù)語§7.1圖的定義和術(shù)語稀疏圖：稠密圖：邊較少的圖。通常邊數(shù)e小于nlogn邊很多的圖。通常邊數(shù)e大于nlogn基本術(shù)語§7.1圖的定義和術(shù)語設(shè)有兩個圖G＝(V,E)和G’＝(V’,E’)。若V’?V且E’?E,則稱圖G’是圖G的子圖。子圖：G基本術(shù)語§7.1圖的定義和術(shù)語設(shè)有兩個圖G＝(V,E)和G’＝(V’,E’)。若V’?V且E’?E,則稱圖G’是圖G的子圖。子圖：G基本術(shù)語§7.1圖的定義和術(shù)語帶權(quán)圖：即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義
3、的數(shù)值（即與邊相關(guān)的數(shù)）。＝帶權(quán)圖網(wǎng)絡(luò)：基本術(shù)語§7.1圖的定義和術(shù)語路徑：在圖G＝(V,E)中,若從頂點(diǎn)vi出發(fā),沿一些邊經(jīng)過一些頂點(diǎn)vp1,vp2,…,vpm，到達(dá)頂點(diǎn)vj。則稱頂點(diǎn)序列(vivp1vp2...vpmvj)為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。它經(jīng)過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應(yīng)當(dāng)是屬于E的邊。V1V2V3V4V5V6V1V2V3V4V5V6基本術(shù)語§7.1圖的定義和術(shù)語路徑長度：非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)；帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)
4、之和。V1V2V3V4V5V62317812基本術(shù)語§7.1圖的定義和術(shù)語簡單路徑：路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù)?；芈罚喝袈窂缴系谝粋€頂點(diǎn)v1與最后一個頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。V1V2V3V4V5V6V1V2V3V4V5V6(a)簡單路徑(b)非簡單路徑基本術(shù)語§7.1圖的定義和術(shù)語簡單路徑：路徑上各頂點(diǎn)v1,v2,...,vm均不互相重復(fù)?；芈罚喝袈窂缴系谝粋€頂點(diǎn)v1與最后一個頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。V1V2V3V4V5V6(c)回路基本術(shù)語§7.1
5、圖的定義和術(shù)語連通圖：在無向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對頂點(diǎn)都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。在有向圖中,若對于每一對頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。強(qiáng)連通圖：基本術(shù)語§7.1圖的定義和術(shù)語連通圖基本術(shù)語§7.1圖的定義和術(shù)語非連通圖三個連通分量基本術(shù)語§7.1圖的定義和術(shù)語強(qiáng)連通圖基本術(shù)語§7.1圖的定義和術(shù)語非強(qiáng)連通圖兩個強(qiáng)連通
6、分量基本術(shù)語§7.1圖的定義和術(shù)語基本術(shù)語§7.1圖的定義和術(shù)語基本術(shù)語§7.1圖的定義和術(shù)語鄰接點(diǎn)對于無向圖G=(V,E)，若邊(v,v’)∈E，則稱頂點(diǎn)v和v’互為鄰接點(diǎn)，即v和v’相鄰接?；蚍Q邊(v,v’)依附于頂點(diǎn)v和v’，或稱(v,v’)和頂點(diǎn)v和v’相關(guān)聯(lián)?；拘g(shù)語§7.1圖的定義和術(shù)語鄰接點(diǎn)對于有向圖G=(V，E)，若弧∈E，則稱頂點(diǎn)v鄰接到頂點(diǎn)v’，或稱頂點(diǎn)v’鄰接自頂點(diǎn)v，或弧和頂點(diǎn)v,v’相關(guān)聯(lián)。基本術(shù)語§7.1圖的定義和術(shù)語頂點(diǎn)v的入度/出度以頂點(diǎn)v為終點(diǎn)有
7、向邊的條數(shù)稱v的入度，記為ID(v)；以頂點(diǎn)v為起點(diǎn)有向邊的條數(shù)稱v的出度，記為OD(v)。頂點(diǎn)v的度TD(v)=ID(v)＋OD(v)頂點(diǎn)v的度(Degree)是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)基本術(shù)語§7.1圖的定義和術(shù)語一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。如果在一棵生成樹上添加一條邊，必定構(gòu)成一個環(huán)，因為這條邊使得它依附的那兩個頂點(diǎn)之間有了第二條路徑。生成樹V1V4V6V5V2V3156554636215432V1V3V5V2V4V6基本
8、術(shù)語§7.1圖的定義和術(shù)語如果一個有向圖恰有一個頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹。一個有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。生成森林基本術(shù)語§7.1圖的定義和術(shù)語如果一個有向圖恰有一個頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹。一個有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。生成森林圖的抽象類型定義§7.1
