數(shù)據(jù)結(jié)構(gòu)導(dǎo)論-圖

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論-圖第五章圖圖：是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。線性表各結(jié)點(diǎn)間存在著一對(duì)一的關(guān)系，每個(gè)結(jié)點(diǎn)有惟一的直接前驅(qū)和惟一的直接后繼。樹形結(jié)構(gòu)中，節(jié)點(diǎn)間具有一對(duì)多的分支層次關(guān)系，每層上的結(jié)點(diǎn)可以與它下面一層中的多個(gè)結(jié)點(diǎn)相關(guān)，但只能與上一層中的至多一個(gè)結(jié)點(diǎn)相關(guān)，而在圖結(jié)構(gòu)中，任意兩個(gè)節(jié)點(diǎn)之間均有可能相關(guān)，圖存在著多對(duì)多的關(guān)系。A城A城A城A城E城B城D城C城B城B城E城C城C城D城最低造價(jià)通訊網(wǎng)一、圖的定義：圖G是由頂點(diǎn)集V和頂點(diǎn)間的關(guān)系集合E（邊的集合）組成的一種數(shù)據(jù)結(jié)構(gòu)，用二元組定義表示為：G=（V，E）其中，G表示一個(gè)圖，V是頂點(diǎn)的有窮非空集合，E是邊的集合，而邊是V中頂點(diǎn)的偶對(duì)。若頂點(diǎn)的偶對(duì)是有序的，則稱圖為有向圖，有序偶對(duì)用尖括號(hào)括起來，若頂點(diǎn)偶對(duì)是無序的，則稱此圖為無向圖，無序偶對(duì)用園括號(hào)括起來。若<x，y>∈E,表示有向圖G中從x到y(tǒng)的一條弧，x稱為弧尾，y稱為弧頭。若(x,y)∈E，表示無向圖G中x，y之間有一條邊。ABABCADAABCA圖a圖b圖a是一有向圖，圖b是一無向圖。圖a用二元組表示如下：G1=(V,E)V={A，B，C}E={<A,B>,<B,C>,<C,A>,<C,B>,<B,A>}圖b用二元組表示如下：G2=(V,E)V={A,B,C,D}E={(A,B),(A,C),(A,D),(B,D),(C,D)}二、圖的基本術(shù)語(yǔ)1、完全圖數(shù)據(jù)結(jié)構(gòu)導(dǎo)論-圖全文共3頁(yè)，當(dāng)前為第1頁(yè)。任何兩點(diǎn)間都有關(guān)聯(lián)的無向圖稱為無向完全圖。其邊數(shù)=點(diǎn)數(shù)*(點(diǎn)數(shù)-1)/2數(shù)據(jù)結(jié)構(gòu)導(dǎo)論-圖全文共3頁(yè)，當(dāng)前為第1頁(yè)。AACABCABDADA任何兩點(diǎn)間都有弧的有向圖稱為有向完全圖。其弧數(shù)=點(diǎn)數(shù)*(點(diǎn)數(shù)-1)AABCA2、頂點(diǎn)的度、入度和出度：ABABCADAABCABCA三、最小生成樹對(duì)于一個(gè)圖，從圖中任一頂點(diǎn)出發(fā)，無論是進(jìn)行深度優(yōu)先搜索或是進(jìn)行廣度優(yōu)先搜索，都可以訪問到圖中的所有頂點(diǎn)。V1V2V1V2V5V6V3V4V1V2V5V6V3V4V1V2V5V6V3V4數(shù)據(jù)結(jié)構(gòu)導(dǎo)論-圖全文共3頁(yè)，當(dāng)前為第2頁(yè)。數(shù)據(jù)結(jié)構(gòu)導(dǎo)論-圖全文共3頁(yè)，當(dāng)前為第2頁(yè)。深度優(yōu)