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