資訊專欄INFORMATION COLUMN
這篇講的是連通分量，連通分量是深度優(yōu)先搜索算法的一個(gè)應(yīng)用。
每進(jìn)行了一次dfs，就會(huì)找到一條連通分量。
定義如下的API
public class CC
CC(Graph g) 預(yù)處理構(gòu)造函數(shù)
boolean connected(int v,in w) v和w連通嗎
int count() 改圖中的連通分量個(gè)數(shù)
int id(int v) 頂點(diǎn)v所在的連通分量編號(hào)
具體實(shí)現(xiàn)如下：
package Graph;
public class CC {
/*
* 計(jì)算一個(gè)圖中的連通分量，從起始點(diǎn)開始進(jìn)行dfs算法，同時(shí)用一個(gè)以頂點(diǎn)作為索引的數(shù)組id[]來保存該點(diǎn)所在的連通分量的起始點(diǎn)，也就是id
* 這樣，判斷兩個(gè)點(diǎn)是否處于同一個(gè)連通分量，只要判斷id是否相同
*/
private boolean[] marked;
private int[] id;
private int count;
public CC(Graph G){
marked = new boolean[G.V()];
id = new int[G.V()];
for(int s = 0;s < G.V();s++){
if(!marked[s]){
dfs(G,s);
count++;
}
}
}
private void dfs(Graph G,int v){
marked[v] = true;
id[v] = count; //該連通分量的起始節(jié)點(diǎn)
for(int w:G.adj(v)){
if(!marked[w])
dfs(G,w);
}
}
public boolean connected(int v,int w){
return id[v] == id[w];
}
public int id(int v){
return id[v];
}
public int count(){
return count;
}
}
同樣還能解決雙色問題，即“能夠用兩種不同顏色將頂點(diǎn)著色，使得相鄰的頂點(diǎn)顏色不同嗎？等價(jià)于這個(gè)圖是一個(gè)二分圖嗎？
/*
* 使用dfs算法，來判斷一個(gè)圖中的頂點(diǎn)是否可以用兩種顏色染色，使得相鄰的頂點(diǎn)顏色不同
* 也就是，判斷該圖是否是一個(gè)二分圖：
* 設(shè)G=(V,E)是一個(gè)無向圖，如果頂點(diǎn)V可分割為兩個(gè)互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn)i和j分別屬于這兩個(gè)不同的頂點(diǎn)集(i in A,j in B)，則稱圖G為一個(gè)二分圖。
*
*/
public class TwoColor {
private boolean[] marked;
private boolean[] color;
private boolean isTwoColorable = true;
public TwoColor(Graph G){
marked = new boolean[G.V()];
color = new boolean[G.V()];
for(int s = 0;s < G.V();s++){
if(!marked[s])
dfs(G,s);
}
}
private void dfs(Graph G,int v){
marked[v] = true;
for(int w: G.adj(v)){
if(!marked[w]){
color[w] =!color[v];
}
else if (color[w] == color[v])
isTwoColorable = false;
}
}
public boolean isTwoColorable(){
return isTwoColorable;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64338.html
摘要：樹是一副無環(huán)連通圖?；ゲ幌噙B的樹組成的集合稱為森林。表示無向圖的數(shù)據(jù)類型圖的基本操作的兩個(gè)構(gòu)造，得到頂點(diǎn)數(shù)和邊數(shù)，增加一條邊。該方法不符合第一個(gè)條件，上百萬個(gè)頂點(diǎn)的圖是很常見的空間不滿足。 四種重要的圖模型： 無向圖（簡(jiǎn)單連接） 有向圖（連接有方向性） 加權(quán)圖（連接帶有權(quán)值） 加權(quán)有向圖（連接既有方向性又帶有權(quán)值） 無向圖 定義：由一組頂點(diǎn)和一組能夠?qū)蓚€(gè)頂點(diǎn)相連的邊組成。 特殊：...
摘要：邊僅由兩個(gè)頂點(diǎn)連接，并且沒有方向的圖稱為無向圖。用分隔符當(dāng)前為空格，也可以是分號(hào)等分隔。深度優(yōu)先算法最簡(jiǎn)搜索起點(diǎn)構(gòu)造函數(shù)找到與起點(diǎn)連通的其他頂點(diǎn)。路徑構(gòu)造函數(shù)接收一個(gè)頂點(diǎn)，計(jì)算到與連通的每個(gè)頂點(diǎn)之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...
摘要：在實(shí)際的測(cè)試中，算法的運(yùn)行效率也比算法高左右。此外，該算法與求無向圖的雙連通分量割點(diǎn)橋的算法也有著很深的聯(lián)系。學(xué)習(xí)該算法，也有助于深入理解求雙連通分量的算法，兩者可以類比組合理解。固屬于同一連通分支。 參考資料http://blog.csdn.net/acmmmm/a...https://www.byvoid.com/blog/s...http://blog.csdn.net/noth...
摘要：實(shí)現(xiàn)這個(gè)想法之后就發(fā)現(xiàn)，時(shí)間復(fù)雜度真的太高了。本期算法小分享就到這里咯剛做完探索里的初級(jí)，還有好多已經(jīng)說爛了的題就不分享了。如果有什么意見或者想法歡迎在評(píng)論區(qū)和我交流 題目 input: n // 代表無向圖的頂點(diǎn)數(shù) // 從1開始 m // 無向圖的邊數(shù) arr1 // 各邊的情況，形如[[1, 2], [3, 4],...]（代表頂點(diǎn)0和頂點(diǎn)2相連，頂點(diǎn)3和頂點(diǎn)4相連） ...
閱讀 2397·2021-11-22 14:56
閱讀 1205·2019-08-30 15:55
閱讀 3234·2019-08-29 13:29
閱讀 1384·2019-08-26 13:56
閱讀 3547·2019-08-26 13:37
閱讀 589·2019-08-26 13:33
閱讀 3377·2019-08-26 13:33
閱讀 2255·2019-08-26 13:33
