PDA

View Full Version : تشخیص دو بخشی بودن گراف



fatemegm
شنبه 05 تیر 1389, 11:51 صبح
قبلن این سوال (85)جواب دادن ولی به نظرم اشتباهه
می شه خیلی سریع یکی جواب بده من همین الان جوابو لازم دارم:خجالت:

qwerty11
شنبه 05 تیر 1389, 15:11 عصر
سلام !
از جستجوی اول سطح یا اول عمق میتونی استفاده کنی !

به یکی از گره ها رنگ سفید نسبت بده، پس به فرزنداش باید رنگ سیاه نسبت داده بشه و به همین ترتیب ... تو هر مرحله اگر رنگ 2 تا راس که با یه یال به هم وصل هستن یکی بود در این صورت گراف دو بخشی نیست ! سودو کدش اینجوریه مثلاً : من با جستجوی اول عمق نوشتم.

boolean isBipartite(){
for(i=0; i<n; i++){
if(!mark[i]){
color i = WHITE
if(!dfs(i)) return false
}
}
return true;
}
boolean dfs(int i){
mark[i]=true
for each node x in e[i] {
if(i & x have same color) return false
color x = symmetry color i
if(!mark[i]) if(!dfs(i)) return false
}
return true
}