版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、圖的存儲(chǔ)遍歷圖的存儲(chǔ)遍歷 及拓?fù)渑判蚣巴負(fù)渑判?李云軍 引例 有n個(gè)島嶼,給出他們的坐標(biāo), 任意兩個(gè)島嶼間可以鋪設(shè)一條通信電纜, 如果需要實(shí)現(xiàn)任意兩個(gè)島嶼間都能 直接或間接通訊,求最少需要鋪設(shè)的 電纜長(zhǎng)度是多少? 某大學(xué)計(jì)算機(jī)專(zhuān)業(yè)的必修課及其先修課程如下表所示: 課程 代號(hào) C0 1 C2C3C4C5C6C7 課程 名稱(chēng) 高等 數(shù)學(xué) 程序 設(shè)計(jì) 語(yǔ)言 離散 數(shù)學(xué) 數(shù)據(jù) 結(jié)構(gòu) 編譯 技術(shù) 操作 系統(tǒng) 普通 物理 計(jì)算 機(jī)原 理 先修 課程 C0, C1 C1, C2 C3 C3, C7 C0C6 請(qǐng)給出一種合理的課程安排方案 圖的相關(guān)概念圖的相關(guān)概念 如果數(shù)據(jù)元素集合中的各元素之間存在任如果數(shù)據(jù)
2、元素集合中的各元素之間存在任 意的關(guān)系,則此數(shù)據(jù)結(jié)構(gòu)稱(chēng)為圖。如果將數(shù)據(jù)意的關(guān)系,則此數(shù)據(jù)結(jié)構(gòu)稱(chēng)為圖。如果將數(shù)據(jù) 元素抽象為頂點(diǎn),元素之間的關(guān)系用邊表示,元素抽象為頂點(diǎn),元素之間的關(guān)系用邊表示, 則圖亦可以表示為則圖亦可以表示為G=G=(V V,E E),其中),其中V V是頂點(diǎn)是頂點(diǎn) 的有窮(非空)集合,的有窮(非空)集合,E E為邊的集合。為邊的集合。 1 1、圖的分類(lèi):無(wú)向圖、有向圖、圖的分類(lèi):無(wú)向圖、有向圖、 帶權(quán)圖帶權(quán)圖 無(wú)向圖:邊集無(wú)向圖:邊集E(G)中為無(wú)向邊。)中為無(wú)向邊。 有向圖:邊集有向圖:邊集E(G)中為有向邊。)中為有向邊。 帶權(quán)圖帶權(quán)圖 :邊上帶有權(quán)的圖。也稱(chēng)為網(wǎng)。(有
3、向帶權(quán)圖、:邊上帶有權(quán)的圖。也稱(chēng)為網(wǎng)。(有向帶權(quán)圖、 無(wú)向帶權(quán)圖)無(wú)向帶權(quán)圖) 2、頂點(diǎn)的度、入度、出度、頂點(diǎn)的度、入度、出度 頂點(diǎn)的度:與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目,有奇點(diǎn)、偶點(diǎn)之分。頂點(diǎn)的度:與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目,有奇點(diǎn)、偶點(diǎn)之分。 對(duì)于有向圖:有入度和出度之分對(duì)于有向圖:有入度和出度之分 入度:該頂點(diǎn)的入邊的數(shù)目。入度:該頂點(diǎn)的入邊的數(shù)目。 出度:該頂點(diǎn)的出邊的數(shù)目。出度:該頂點(diǎn)的出邊的數(shù)目。 提問(wèn)提問(wèn)1:一個(gè)圖中,全部頂點(diǎn)的度數(shù)為所有邊數(shù)的一個(gè)圖中,全部頂點(diǎn)的度數(shù)為所有邊數(shù)的 倍倍; 2 提問(wèn)提問(wèn)2:有向圖中所有頂點(diǎn)的入度之和是有向圖中所有頂點(diǎn)的入度之和是(大于、等于、小于大于、等于、
4、小于) 所有頂點(diǎn)的出度之和;所有頂點(diǎn)的出度之和; 提問(wèn)提問(wèn)3:任意一個(gè)無(wú)向圖一定有(偶數(shù)、奇數(shù))個(gè)奇點(diǎn);任意一個(gè)無(wú)向圖一定有(偶數(shù)、奇數(shù))個(gè)奇點(diǎn); 完全圖:若是無(wú)向圖中,則每?jī)蓚€(gè)頂點(diǎn)之間都存在完全圖:若是無(wú)向圖中,則每?jī)蓚€(gè)頂點(diǎn)之間都存在 著一條邊;若是有向圖,則每?jī)蓚€(gè)頂點(diǎn)之間都存在著一條邊;若是有向圖,則每?jī)蓚€(gè)頂點(diǎn)之間都存在 著方向相反的兩條邊。著方向相反的兩條邊。 1 23 4 5 ab c d e f 3、完全圖、稠密圖、稀疏圖、完全圖、稠密圖、稀疏圖 稠密圖:當(dāng)一個(gè)圖的邊數(shù)接近完全圖時(shí)。稠密圖:當(dāng)一個(gè)圖的邊數(shù)接近完全圖時(shí)。 稀疏圖:當(dāng)一個(gè)圖的邊數(shù)遠(yuǎn)遠(yuǎn)少于完全圖時(shí)。稀疏圖:當(dāng)一個(gè)圖的邊數(shù)遠(yuǎn)
5、遠(yuǎn)少于完全圖時(shí)。 n*(n-1)/2 n*(n-1) 注意:注意:1 1)一個(gè))一個(gè)n n階的完全無(wú)向圖含有階的完全無(wú)向圖含有 條邊;條邊; 2 2)一個(gè))一個(gè)n n階的完全有向圖含有階的完全有向圖含有 條邊;條邊; 路徑:對(duì)于圖路徑:對(duì)于圖G=G=(V V,E E),對(duì)于頂點(diǎn)),對(duì)于頂點(diǎn)a a、b b,如果存在一些頂點(diǎn)序列,如果存在一些頂點(diǎn)序列 x x1 1=a,x=a,x2 2,x,xk k=b(k1)=b(k1),且(,且(x xi i,x,xi+1 i+1) )EE,i=1,2k-1i=1,2k-1,則稱(chēng)頂點(diǎn)序列,則稱(chēng)頂點(diǎn)序列 x x1 1,x,x2 2,x,xk k為頂點(diǎn)為頂點(diǎn)a a
6、到頂點(diǎn)到頂點(diǎn)b b的一條路徑,而路徑上邊的數(shù)目(即的一條路徑,而路徑上邊的數(shù)目(即k-1k-1) 稱(chēng)為該稱(chēng)為該路徑的長(zhǎng)度路徑的長(zhǎng)度。并稱(chēng)頂點(diǎn)集合。并稱(chēng)頂點(diǎn)集合x(chóng)x1 1,x,x2 2,x,xk k 為一個(gè)連通集。為一個(gè)連通集。 簡(jiǎn)單路徑:如果一條路徑上的頂點(diǎn)除了起點(diǎn)和終點(diǎn)可以相同外,其它頂簡(jiǎn)單路徑:如果一條路徑上的頂點(diǎn)除了起點(diǎn)和終點(diǎn)可以相同外,其它頂 點(diǎn)均不相同,則稱(chēng)此路徑為一條簡(jiǎn)單路徑;起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑點(diǎn)均不相同,則稱(chēng)此路徑為一條簡(jiǎn)單路徑;起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑 稱(chēng)為稱(chēng)為回路(或環(huán))回路(或環(huán))。 4 4、子圖、子圖 1 23 4 5 1 23 圖G圖G 設(shè)兩個(gè)圖設(shè)兩個(gè)圖G=(V,
7、E)和)和 G=(V,E),若若V是是V的子集的子集,且且E 是是E的子集的子集,則稱(chēng)則稱(chēng)G是是G的子圖。的子圖。 5、路徑和回路、路徑和回路 路徑和簡(jiǎn)單路徑的舉例:路徑和簡(jiǎn)單路徑的舉例: 左圖左圖123123是一條簡(jiǎn)單路徑,長(zhǎng)度為是一條簡(jiǎn)單路徑,長(zhǎng)度為2 2, 而而1341313413就不是簡(jiǎn)單路徑;就不是簡(jiǎn)單路徑; 右圖右圖121121為一個(gè)回路。為一個(gè)回路。 連通圖:連通圖:如果一個(gè)無(wú)向圖中,任意兩個(gè)頂點(diǎn)之間都是連通的,則稱(chēng)該如果一個(gè)無(wú)向圖中,任意兩個(gè)頂點(diǎn)之間都是連通的,則稱(chēng)該 無(wú)向圖為連通圖。否則稱(chēng)為非連通圖;左圖為一個(gè)連通圖。無(wú)向圖為連通圖。否則稱(chēng)為非連通圖;左圖為一個(gè)連通圖。 連通
8、分量:連通分量:一個(gè)無(wú)向圖的連通分支定義為該圖的最大連通子圖,左圖一個(gè)無(wú)向圖的連通分支定義為該圖的最大連通子圖,左圖 的連通分量是它本身。的連通分量是它本身。 連通:連通:在一個(gè)圖中,如果從頂點(diǎn)在一個(gè)圖中,如果從頂點(diǎn)U U到頂點(diǎn)到頂點(diǎn)V V有路徑,則稱(chēng)有路徑,則稱(chēng)U U和和V V是連通的;是連通的; 6 6、連通和連通分量、連通和連通分量 注意:注意:任何連通圖的連通分量只有一個(gè),即本身,而非任何連通圖的連通分量只有一個(gè),即本身,而非 連通圖有多個(gè)連通分量。連通圖有多個(gè)連通分量。 強(qiáng)連通分量:強(qiáng)連通分量:一個(gè)有向圖的強(qiáng)連通分量定義為該圖的最大的強(qiáng)連通子圖,一個(gè)有向圖的強(qiáng)連通分量定義為該圖的最大
9、的強(qiáng)連通子圖, 右圖含有兩個(gè)強(qiáng)連通分量,一個(gè)是右圖含有兩個(gè)強(qiáng)連通分量,一個(gè)是1 1和和2 2構(gòu)成的一個(gè)子圖,一個(gè)是構(gòu)成的一個(gè)子圖,一個(gè)是3 3獨(dú)立構(gòu)成獨(dú)立構(gòu)成 的一個(gè)子圖。的一個(gè)子圖。 強(qiáng)連通圖:強(qiáng)連通圖:在一個(gè)有向圖中,對(duì)于任意兩個(gè)頂點(diǎn)在一個(gè)有向圖中,對(duì)于任意兩個(gè)頂點(diǎn)U U和和V V,都存在著一條從,都存在著一條從U U到到V V 的有向路徑,同時(shí)也存在著一條從的有向路徑,同時(shí)也存在著一條從V V到到U U的有向路徑,則稱(chēng)該有向圖為強(qiáng)連通的有向路徑,則稱(chēng)該有向圖為強(qiáng)連通 圖;右圖不是一個(gè)強(qiáng)連通圖。圖;右圖不是一個(gè)強(qiáng)連通圖。 7 7、強(qiáng)連通圖和強(qiáng)連通分量強(qiáng)連通圖和強(qiáng)連通分量 注意:注意:強(qiáng)連通
10、圖只有一個(gè)強(qiáng)連通分量,即本身,非強(qiáng)連強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量,即本身,非強(qiáng)連 通圖有多個(gè)強(qiáng)連通分量。通圖有多個(gè)強(qiáng)連通分量。 圖的存儲(chǔ)圖的存儲(chǔ) 圖型結(jié)構(gòu)的存儲(chǔ)分為靜態(tài)存儲(chǔ)和動(dòng)態(tài)存儲(chǔ)。我們介紹下面三種:鄰圖型結(jié)構(gòu)的存儲(chǔ)分為靜態(tài)存儲(chǔ)和動(dòng)態(tài)存儲(chǔ)。我們介紹下面三種:鄰 接矩陣、鄰接表(用數(shù)組模擬),邊集數(shù)組。接矩陣、鄰接表(用數(shù)組模擬),邊集數(shù)組。 1 1、鄰接矩陣鄰接矩陣 相鄰矩陣是表示頂點(diǎn)間相鄰關(guān)系的矩陣。若相鄰矩陣是表示頂點(diǎn)間相鄰關(guān)系的矩陣。若G=G=(V V,E E) 是一個(gè)具有是一個(gè)具有n n個(gè)頂點(diǎn)的圖,則個(gè)頂點(diǎn)的圖,則G G的相鄰矩陣是如下定義的的相鄰矩陣是如下定義的 二維數(shù)組二維數(shù)組a
11、a,其規(guī)模為,其規(guī)模為n n* *n n 上圖中的3個(gè)圖對(duì)應(yīng)的鄰接矩陣分別如下: 0 1 1 1 0 1 1 5 8 3 G(A)= 1 0 1 1 G(B)= 0 0 1 5 2 6 1 1 0 0 0 1 0 G(C)= 8 2 10 4 1 1 0 0 10 11 3 6 4 11 下面是建立圖的鄰接矩陣的參考程序段: int i,j,k,e,n;double g101101;double w; int main() int i,j; for (i = 1; i = n; i+) for (j = 1; j e; for (k = 1; k i j w; gij = w; /對(duì)于不帶權(quán)的
12、圖gij=1 gji = w; /無(wú)向圖的對(duì)稱(chēng)性,如果是有向圖則不要有這句! return 0; 鄰接矩陣存儲(chǔ)的特點(diǎn) 1、占用的存儲(chǔ)單元數(shù)只與頂點(diǎn)數(shù)有關(guān)而與邊數(shù)無(wú)關(guān),占用的存儲(chǔ)單元數(shù)只與頂點(diǎn)數(shù)有關(guān)而與邊數(shù)無(wú)關(guān),n n* *n n的二維數(shù)組。的二維數(shù)組。 2 2、方便度數(shù)的計(jì)算。、方便度數(shù)的計(jì)算。 3 3、容易判斷兩點(diǎn)之間是否有邊相連。、容易判斷兩點(diǎn)之間是否有邊相連。 4 4、尋找一個(gè)點(diǎn)、尋找一個(gè)點(diǎn)相連的所有邊需要一個(gè)一到相連的所有邊需要一個(gè)一到n n的循環(huán)。的循環(huán)。 17 2 2、鄰接表鄰接表 1 2 5 3 4 2 3 4 2 1 3 2 1 2 3 4 5 223243 123153 12
13、2152 1354 233244 頭指針鄰接點(diǎn)指針 結(jié)點(diǎn)鄰接點(diǎn)指針 鄰接點(diǎn) 邊權(quán)值 下一個(gè)鄰接點(diǎn)指針 數(shù)組模擬鄰接表方法一 int g101101; 尋找頂點(diǎn)i有邊相連的點(diǎn)可以這樣來(lái)做,gi0表示i發(fā)出的邊的數(shù)量, gij表示i發(fā)出的第j條邊是通向哪個(gè)頂點(diǎn)的。 for (int j = 1; j = gi0; j+) .gij. 這樣就可以處理i發(fā)出的每條邊,也就能找到頂點(diǎn)i有邊相連的頂點(diǎn)。 5 6 0 4 1 0 1 2 2 0 2 3 3 4 01234 1356 0123456 next002040 to402034 數(shù)組模擬鄰接表方法二 0123456 next002040 to402
14、034 01234 1356 計(jì)算每個(gè)點(diǎn)的出度計(jì)算每個(gè)點(diǎn)的出度 鄰接表存儲(chǔ)特點(diǎn) 1、對(duì)于稀疏圖,用鏈表實(shí)現(xiàn)的鄰接表,可以節(jié)省內(nèi)存。 2、可以快速找到與當(dāng)前頂點(diǎn)相連的點(diǎn)。 3、判斷兩點(diǎn)是否相連不如鄰接矩陣快速。 3 3、邊集數(shù)組邊集數(shù)組 邊集數(shù)組:邊集數(shù)組:是利用一維數(shù)組存儲(chǔ)圖中所有邊的一種圖的表是利用一維數(shù)組存儲(chǔ)圖中所有邊的一種圖的表 示方法。示方法。 V1 V2V3 V4 5 7 12 3 8 起點(diǎn)起點(diǎn) 終點(diǎn)終點(diǎn) 權(quán)權(quán) 無(wú)向帶權(quán)圖的邊集數(shù)組表示法無(wú)向帶權(quán)圖的邊集數(shù)組表示法 從圖中某一頂點(diǎn)出發(fā)系統(tǒng)地訪問(wèn)圖中所有頂點(diǎn),使從圖中某一頂點(diǎn)出發(fā)系統(tǒng)地訪問(wèn)圖中所有頂點(diǎn),使 每個(gè)頂點(diǎn)恰好被訪問(wèn)一次,這種運(yùn)
15、算操作被稱(chēng)為圖的遍每個(gè)頂點(diǎn)恰好被訪問(wèn)一次,這種運(yùn)算操作被稱(chēng)為圖的遍 歷歷。 遍歷可以采取兩種方法進(jìn)行:遍歷可以采取兩種方法進(jìn)行: 深度優(yōu)先深度優(yōu)先遍歷遍歷 廣度優(yōu)先廣度優(yōu)先遍歷遍歷 1 1、圖的深度優(yōu)先遍歷、圖的深度優(yōu)先遍歷 對(duì)下面兩個(gè)圖分別進(jìn)行深度優(yōu)先遍歷,寫(xiě)出對(duì)下面兩個(gè)圖分別進(jìn)行深度優(yōu)先遍歷,寫(xiě)出 遍歷結(jié)果。注意:分別從遍歷結(jié)果。注意:分別從a a和和V1V1出發(fā)。出發(fā)。 左圖從頂點(diǎn)左圖從頂點(diǎn)a a出發(fā),進(jìn)行深度優(yōu)先遍歷的結(jié)果為:出發(fā),進(jìn)行深度優(yōu)先遍歷的結(jié)果為: a a,b b,c c,d d,e e,g g,f f 右圖從右圖從V V1 1出發(fā)進(jìn)行深度優(yōu)先遍歷的結(jié)果為:出發(fā)進(jìn)行深度優(yōu)先遍
16、歷的結(jié)果為: V V1 1,V V2 2,V V4 4,V V8 8,V V5 5,V V3 3,V V6 6,V V7 7 圖的遍歷分為圖的遍歷分為深度優(yōu)先遍歷和廣度(寬度)優(yōu)先遍歷深度優(yōu)先遍歷和廣度(寬度)優(yōu)先遍歷兩種方法。兩種方法。 為了避免重復(fù)訪問(wèn)某個(gè)頂點(diǎn),可以設(shè)一個(gè)標(biāo)志數(shù)組visi, 未訪問(wèn)時(shí)值為0,訪問(wèn)一次后就改為1。 /DFS參考代碼/DFS參考代碼 #include #include const int maxn=1010;const int maxn=1010; int amaxnmaxn;int amaxnmaxn; int vismaxn;int vismaxn; int
17、 n,m;int n,m; void dfs(int u)void dfs(int u) printf(%dn,u);printf(%dn,u); visu=1;visu=1; for(int i=1;i=n;i+)for(int i=1;i=n;i+) if(aui=1if(aui=1 對(duì)下面兩個(gè)圖分別從對(duì)下面兩個(gè)圖分別從a a和和V1V1出發(fā)進(jìn)行廣度優(yōu)先出發(fā)進(jìn)行廣度優(yōu)先 遍歷,寫(xiě)出遍歷結(jié)果。遍歷,寫(xiě)出遍歷結(jié)果。 2 2、圖的廣度優(yōu)先遍歷、圖的廣度優(yōu)先遍歷 左圖從頂點(diǎn)左圖從頂點(diǎn)a a出發(fā),進(jìn)行廣度優(yōu)先遍歷的結(jié)果為:出發(fā),進(jìn)行廣度優(yōu)先遍歷的結(jié)果為: a a,b b,d d,e e,f f,c
18、c,g g 右圖從右圖從V1V1出發(fā)進(jìn)行廣度優(yōu)先遍歷的結(jié)果為:出發(fā)進(jìn)行廣度優(yōu)先遍歷的結(jié)果為: V V1 1,V V2 2,V V3 3,V V4 4,V V5 5,V V6 6,V V7 7,V V8 8 廣度優(yōu)先遍歷廣度優(yōu)先遍歷的實(shí)現(xiàn):的實(shí)現(xiàn): 為避免重復(fù)訪問(wèn),也需要一個(gè)狀態(tài)數(shù)組為避免重復(fù)訪問(wèn),也需要一個(gè)狀態(tài)數(shù)組 visn,用來(lái),用來(lái) 存儲(chǔ)各頂點(diǎn)的訪問(wèn)狀態(tài)。如果存儲(chǔ)各頂點(diǎn)的訪問(wèn)狀態(tài)。如果 visi = 1,則表示頂點(diǎn),則表示頂點(diǎn) i 已已 經(jīng)訪問(wèn)過(guò);如果經(jīng)訪問(wèn)過(guò);如果 visi = 0,則表示頂點(diǎn),則表示頂點(diǎn) i 還未訪問(wèn)過(guò)。初還未訪問(wèn)過(guò)。初 始時(shí),各頂點(diǎn)的訪問(wèn)狀態(tài)均為始時(shí),各頂點(diǎn)的訪問(wèn)狀態(tài)
19、均為 0。 為了實(shí)現(xiàn)逐層訪問(wèn),為了實(shí)現(xiàn)逐層訪問(wèn), BFS 算法在實(shí)現(xiàn)時(shí)需要使用一個(gè)算法在實(shí)現(xiàn)時(shí)需要使用一個(gè) 隊(duì)列隊(duì)列. BFS( 頂點(diǎn)頂點(diǎn) i ) /從頂點(diǎn)從頂點(diǎn) i 進(jìn)行廣度優(yōu)先搜索進(jìn)行廣度優(yōu)先搜索 visitedi = 1; /將頂點(diǎn)將頂點(diǎn) i 的訪問(wèn)標(biāo)志置為的訪問(wèn)標(biāo)志置為 1 將頂點(diǎn)將頂點(diǎn) i 入隊(duì)列入隊(duì)列; while( 隊(duì)列不為空隊(duì)列不為空 ) 取出隊(duì)列頭的頂點(diǎn),設(shè)為取出隊(duì)列頭的頂點(diǎn),設(shè)為 k for( j=0; jn; j+ ) /對(duì)其他所有頂點(diǎn)對(duì)其他所有頂點(diǎn) j /j是是k的鄰接頂點(diǎn),且頂點(diǎn)的鄰接頂點(diǎn),且頂點(diǎn)j沒(méi)有訪問(wèn)過(guò)沒(méi)有訪問(wèn)過(guò) if( akj=1 using namespac
20、e std; const int maxn=1010;const int maxn=1010; int qmaxn;int qmaxn; int amaxnmaxn;int amaxnmaxn; int vismaxn;int vismaxn; int n,m;int n,m; void bfs(int u)void bfs(int u) int head=0,tail=1;int head=0,tail=1; q0=u;q0=u; 如果是非連通圖,主程序做如下修改如果是非連通圖,主程序做如下修改: int main() memset(vis,0,sizeof(vis); for (int i
21、 = 1; i = n; i+) if (visi=0) dfs(i); return 0; 1 2 3 4 5 以3為起點(diǎn)根本不能 遍歷整個(gè)圖 這個(gè)非連通無(wú)向圖任何一 個(gè)點(diǎn)為起點(diǎn)都不能遍歷整 個(gè)圖 1 4 5 2 3 例例1:公司數(shù)量1:公司數(shù)量 【問(wèn)題描述】【問(wèn)題描述】 在某個(gè)城市里住著n個(gè)人,現(xiàn)在給定關(guān) 在某個(gè)城市里住著n個(gè)人,現(xiàn)在給定關(guān) 于 n個(gè)人的m條信息(即某2個(gè)人認(rèn)識(shí)),假于 n個(gè)人的m條信息(即某2個(gè)人認(rèn)識(shí)),假 設(shè)所有認(rèn)識(shí)(直接或間接認(rèn)識(shí)都算認(rèn)識(shí))的設(shè)所有認(rèn)識(shí)(直接或間接認(rèn)識(shí)都算認(rèn)識(shí))的 人一定屬于同一個(gè)公司。人一定屬于同一個(gè)公司。 若是某兩人不在給出的信息里,那么他 若是某
22、兩人不在給出的信息里,那么他 們不認(rèn)識(shí),屬于兩個(gè)不同的公司。們不認(rèn)識(shí),屬于兩個(gè)不同的公司。 已知人的編號(hào)從1至n。 已知人的編號(hào)從1至n。 請(qǐng)計(jì)算該城市最多有多少公司。 請(qǐng)計(jì)算該城市最多有多少公司。 【輸入】【輸入】 第一行:n(=10000,人數(shù)), 第一行:n(=10000,人數(shù)), city.incity.out 11 9 1 2 4 5 3 4 1 3 5 6 7 10 5 10 6 10 8 9 3 【數(shù)據(jù)規(guī)模】【數(shù)據(jù)規(guī)?!?100%的的數(shù)據(jù):數(shù)據(jù): n=10000; m=100000。 分析分析 以人為圖的頂點(diǎn),相互認(rèn)識(shí)的建立無(wú)向邊,求無(wú)向圖以人為圖的頂點(diǎn),相互認(rèn)識(shí)的建立無(wú)向邊,求
23、無(wú)向圖 的連通分量數(shù)的連通分量數(shù)。 4 45 5 6 6 7 71010 8 83 31 12 2 9 9 1111 /深度優(yōu)先參考代碼/深度優(yōu)先參考代碼 #include #include const int maxn=10010;const int maxn=10010; int amaxnmaxn;int amaxnmaxn; int vismaxn;int vismaxn; int n,m,cnt;int n,m,cnt; void dfs(int k)void dfs(int k) visk=1;visk=1; for(int i=1;i=n;i+)for(int i=1;i=n;i
24、+) if(!visiif(!visi int main()int main() scanf(%d%d,scanf(%d%d, int x,y;int x,y; for(int i=1;i=m;i+)for(int i=1;i=m;i+) /廣度優(yōu)先參考代碼/廣度優(yōu)先參考代碼 #include #include const int maxn=10010;const int maxn=10010; int amaxnmaxn;int amaxnmaxn; int vismaxn;int vismaxn; int qmaxn;int qmaxn; int n,m,cnt;int n,m,cnt;
25、void bfs(int k)void bfs(int k) int head=0,tail=1;int head=0,tail=1; q0=k;q0=k; visk=1;visk=1; while(headtail)while(headtail) int p=qhead+;int p=qhead+; for(int i=1;i=n;i+)for(int i=1;i=n;i+) if(!visiusing namespace std; const int maxn=110;const int maxn=110; const int dx8=-1,1,0,0,-1,1,-1,1;const in
26、t dx8=-1,1,0,0,-1,1,-1,1; const int dy8=0,0,-1,1,-1,1,1,-1; const int dy8=0,0,-1,1,-1,1,1,-1; int gmaxnmaxn;int gmaxnmaxn; int n,m,cnt;int n,m,cnt; void dfs(int x,int y)void dfs(int x,int y) gxy=0;gxy=0; /BFS:油田/BFS:油田 #include #include #include #include #include #include using namespace std;using n
27、amespace std; const int maxn=110;const int maxn=110; const int dx8=-1,1,0,0,-1,1,-1,1;const int dx8=-1,1,0,0,-1,1,-1,1; const int dy8=0,0,-1,1,-1,1,1,-1; const int dy8=0,0,-1,1,-1,1,1,-1; int gmaxnmaxn;int gmaxnmaxn; int n,m,cnt;int n,m,cnt; struct nodestruct node int x,y;int x,y; 例例3紅與黑(zoj2165 poj
28、1979)3紅與黑(zoj2165 poj1979) 題目描述: 題目描述: 有一個(gè)長(zhǎng)方形的房間,房間里的地面上 有一個(gè)長(zhǎng)方形的房間,房間里的地面上 布滿(mǎn)了正方形的瓷磚,瓷磚要么是紅色,要布滿(mǎn)了正方形的瓷磚,瓷磚要么是紅色,要 么是黑色。一男子站在其中一塊黑色的瓷磚么是黑色。一男子站在其中一塊黑色的瓷磚 上。男子可以向他四周的瓷磚上移動(dòng),但不上。男子可以向他四周的瓷磚上移動(dòng),但不 能移動(dòng)到紅色的瓷磚上,只能在黑色的瓷磚能移動(dòng)到紅色的瓷磚上,只能在黑色的瓷磚 上移動(dòng)。 上移動(dòng)。 本題的目的就是要編寫(xiě)程序,計(jì)算他在 本題的目的就是要編寫(xiě)程序,計(jì)算他在 這個(gè)房間里可以到達(dá)的黑色瓷磚的數(shù)量。這個(gè)房間里
29、可以到達(dá)的黑色瓷磚的數(shù)量。 輸入描述:輸入描述: 輸入文件中包含多個(gè)測(cè)試數(shù)據(jù)。 輸入文件中包含多個(gè)測(cè)試數(shù)據(jù)。 每個(gè)測(cè)試數(shù)據(jù)的第 1 行為兩個(gè)整數(shù) W 每個(gè)測(cè)試數(shù)據(jù)的第 1 行為兩個(gè)整數(shù) W 和 H,分別表示長(zhǎng)方形房間里 x 方向和 y 和 H,分別表示長(zhǎng)方形房間里 x 方向和 y 方向上瓷磚的數(shù)目。W 和 H 的值不超過(guò)方向上瓷磚的數(shù)目。W 和 H 的值不超過(guò) 分析:分析: 求男子所在位置能到達(dá)的黑色求男子所在位置能到達(dá)的黑色 的連通塊的大小。的連通塊的大小。 從起點(diǎn)遍歷圖即可。從起點(diǎn)遍歷圖即可。 樣例輸入:樣例輸入: 6 9 6 9 .#.#. .#.# . . . . . #.#.# .#
30、.#.#.#. 11 911 9 /DFS:紅與黑/DFS:紅與黑 #include #include #include #include #include #include using namespace std;using namespace std; const int maxn=110;const int maxn=110; const int dx4=-1,1,0,0;const int dx4=-1,1,0,0; const int dy4=0,0,-1,1; const int dy4=0,0,-1,1; int gmaxnmaxn;int gmaxnmaxn; int n,m,
31、sx,sy,cnt;int n,m,sx,sy,cnt; void dfs(int x,int y)void dfs(int x,int y) cnt+;cnt+; gxy=0;gxy=0; for(int i=0;i4;i+)for(int i=0;i4;i+) int xx=x+dxi;int xx=x+dxi; /BFS:紅與黑/BFS:紅與黑 #include #include #include #include #include #include using namespace std;using namespace std; const int maxn=110;const int
32、 maxn=110; const int dx4=-1,1,0,0;const int dx4=-1,1,0,0; const int dy4=0,0,-1,1; const int dy4=0,0,-1,1; int gmaxnmaxn;int gmaxnmaxn; int n,m,sx,sy;int n,m,sx,sy; struct nodestruct node int x,y;int x,y; cur,nxt;cur,nxt; node qmaxn*maxn;node qmaxn*maxn; void bfs(int x,int y)void bfs(int x,int y) 1 2
33、 3 5 6 7 8 94 12 34 拓?fù)渑判蛩惴?A B C E D A B C D 開(kāi)始時(shí),只有A 入度為0,A入棧。 棧:A B C D 棧頂元素A出棧并輸出A, A的后繼B、C入度減1,相 當(dāng)于刪除A的所有關(guān)聯(lián)邊 棧:空 拓?fù)湫蛄校篈 B C D B、C的入度都變成0, 依次將B、C入棧。 棧:BC(入棧順序不唯一) 拓?fù)湫蛄校篈 B D 棧頂元素C出棧并輸出 C,C的后繼D入度減1 棧:B 拓?fù)湫蛄校篈C D 棧頂元素B出棧并輸出B, B的后繼D入度再減1。這 時(shí)D入度為0,入棧。 棧:D 拓?fù)湫蛄校篈CB D 棧頂元素D出棧并輸出 D。棧空,結(jié)束 棧:空 拓?fù)湫蛄校篈CBD(不唯
34、一) 【例【例4】、家譜樹(shù)4】、家譜樹(shù) 【問(wèn)題描述】【問(wèn)題描述】 有個(gè)人的家族很大,輩分關(guān)系很混亂, 有個(gè)人的家族很大,輩分關(guān)系很混亂, 請(qǐng)你幫整理一下這種關(guān)系。請(qǐng)你幫整理一下這種關(guān)系。 給出每個(gè)人的孩子的信息。 給出每個(gè)人的孩子的信息。 輸出一個(gè)序列,使得每個(gè)人的后輩都比 輸出一個(gè)序列,使得每個(gè)人的后輩都比 那個(gè)人后列出。那個(gè)人后列出。 【輸入格式】【輸入格式】 第1行一個(gè)整數(shù)N(1=N=100),表示 第1行一個(gè)整數(shù)N(1=N=100),表示 家族的人數(shù)。家族的人數(shù)。 接下來(lái)N行,第I行描述第I個(gè)人的兒 接下來(lái)N行,第I行描述第I個(gè)人的兒 子。子。 每行最后是0表示描述完畢。 每行最后是0
35、表示描述完畢。 【輸出格式】【輸出格式】 輸出一個(gè)序列,使得每個(gè)人的后輩都比 輸出一個(gè)序列,使得每個(gè)人的后輩都比 #include#include #include#include using namespace std;using namespace std; int a101101,c101,r101,ansint a101101,c101,r101,ans 101;101; int i,j,tot,temp,num,n,m;int i,j,tot,temp,num,n,m; int main()int main() cin n; cin n; for (i = 1; i = n; i+) for (i = 1; i j; cin j; if
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度木飾面原材料進(jìn)口與分銷(xiāo)合同3篇
- 2025年親子遺贈(zèng)協(xié)議草案
- 2025年代理商代理加盟采購(gòu)合資合作協(xié)議
- 2025年合資合作收益分配協(xié)議
- 2025年企業(yè)外包勞務(wù)協(xié)議
- 2025年智慧城市物業(yè)管理服務(wù)標(biāo)準(zhǔn)合同范本6篇
- 漫談加強(qiáng)物資管理提高企業(yè)經(jīng)濟(jì)效益-圖文
- 《皮質(zhì)醇增多征荊》課件
- 2025年度醫(yī)院病理科診斷服務(wù)承包合同4篇
- 2025年度汽車(chē)轉(zhuǎn)讓及二手車(chē)交易稅費(fèi)減免合同
- 個(gè)體工商戶(hù)章程(標(biāo)準(zhǔn)版)
- 七年級(jí)英語(yǔ)閱讀理解55篇(含答案)
- 廢舊物資買(mǎi)賣(mài)合同極簡(jiǎn)版
- 2024年正定縣國(guó)資產(chǎn)控股運(yùn)營(yíng)集團(tuán)限公司面向社會(huì)公開(kāi)招聘工作人員高頻考題難、易錯(cuò)點(diǎn)模擬試題(共500題)附帶答案詳解
- 智能衣服方案
- 李克勤紅日標(biāo)準(zhǔn)粵語(yǔ)注音歌詞
- 教科版六年級(jí)下冊(cè)科學(xué)第一單元《小小工程師》教材分析及全部教案(定稿;共7課時(shí))
- 中藥材產(chǎn)地加工技術(shù)規(guī)程 第1部分:黃草烏
- 危險(xiǎn)化學(xué)品經(jīng)營(yíng)單位安全生產(chǎn)考試題庫(kù)
- 案例分析:美國(guó)紐約高樓防火設(shè)計(jì)課件
- 移動(dòng)商務(wù)內(nèi)容運(yùn)營(yíng)(吳洪貴)任務(wù)一 用戶(hù)定位與選題
評(píng)論
0/150
提交評(píng)論