Problem ve Çözüm Yöntemi
Öncelikle bizden ne istendiğini
anlamak gereklidir. Programımızda bizden kaç adet bağlı bileşen olduğunu, bu
bileşenlerin içerisindeki düğüm sayılarını ve bunların hangileri olduklarını
bulmamız isteniyor.
Programımıza geçtiğimizde
öncelikle kullandığımız değişkenleri ve ya dizileri tanımlıyoruz. Kullanıcıdan
öncelikle düğüm sayısını ve düğümler arası kaç tane bağlantı olduğunu girmesini
istiyoruz ve bunları dugum ile kenarsayisi değişkenlerine atıyoruz. Kaç
bağlantı olduğunu öğrendikten sonra dugum1 ve dugum2 dizilerine kenar sayısı
kadar yer açıyoruz. dugum1 ve dugum2 dizileri girilen her iki düğümü sırasıyla
tutuyor. Girdiğimiz ilk değer dugum1 dizisinin ilk elemanı girdiğimiz ikinci
değer de dugum2 dizisinin ilk elemanı oluyor. For döngüsü kullanarak bu iki
diziyi dolduruyoruz. Bu işlemi tamamladıktan sonra ise tutaç adında bir diziyi
calloc kullanarak açıyoruz. Dizinin büyüklüğü düğüm sayısı kadar oluyor. Bu
dizimiz ise hangi düğümlerin birbirine bağlı olduğunu bulmamızda yardımcı
olacak. Dizimizi doldururken teker teker dugum1 ve dugum2 dizilerini okuyarak
ilerliyoruz. Her okuma işleminde şu yolları izliyoruz:
· Dugum1 ile dugum2
dizisinin gösterdiği düğümleri tutaç dizisinde ikisinin de sıfır olup
olmadığını kontrol ediyoruz. Bu işlemi toplamlarının sıfır olup olmadığına
bakarak yapıyoruz.
· Eğer ikisi de
sıfırsa bu değerlere tutaç dizisinde cmp değişkenin değerini atıyoruz
·
Diğer dizilerimizden ilki sayaç
adlı dizimiz oluyor. Bu dizimiz ise bize kaç farklı bileşen olduğunu bulmamızda
yardımcı olacak. Sayac dizisini doldururken ise şu yolları izliyoruz:
· Tek tek tutaç
dizisinin elemanlarına bakıyoruz. Gördüğümüz her değeri indis kabul eden sayaç
dizisini 1’liyoruz.
· Burada dikkat
etmemiz gereken bir şey var o da sayaç dizisinde 0 olarak kalan her eleman
farklı bir bileşeni belirtiyor bu yüzden indis sıfır olduğunda diğer
işlemlerden farklı olarak sayaçtaki 0 adresini bir artıracağız.
· Bu işlemin
sonunda sıfırıncı adresteki değer bize kaç tane bir düğümlü bileşen olduğunu,
diğer adresteki değerleri-yani 1’lenen değerleri- de bunlarla toplayarak ise
kaç farklı bileşen olduğuna ulaşıyoruz.
Son olarak da sıra icsayac adlı
dizimizi doldurmaya geliyor. Bu diziyi de bileşenlerin içerisinde kaç tane
düğüm olduğunu bulmak için kullanıyoruz. Diziyi doldururken şu işlemleri
yapıyoruz:
· Tutaç dizisini
baştan sona arama yaparak ilerliyoruz. Gördüğümüz her değerin icsayac
dizisindeki o indisli değerini bir artırarak ilerliyoruz.
· İşlem sonunda
icsayac dizisindeki sıfırdan farklı elemanlar herhangi bir bileşenin kaçar düğüm
içerdiğini belirtiyor.
· Sonra tekrar bu
sıfırdan farklı olan elemanların indislerini tutaç dizisinde arıyoruz ve
bulduğumuz değerleri ekrana ayrı ayrı yazdırıyoruz. Bunlar herhangi bir
bileşenin içerisindeki düğümler oluyor. Tabi bunları yaparken sıraya göre
yazmak gerekiyor.
Programın C Dilindeki Kodu
#include <stdio.h>
#include <stdlib.h>
//tek düğümler ayrı hesaplandığı için bunları yazdırırken ayrı fonksiyon uygularız
void TekDugumleriYazdir(int dugum,int *icsayac,int *tutac,int index){
int j;
for(j=0;j<icsayac[0];j++){//sıfırıncı gözde sakladıgımız bilgi kaç tane tek düğüm olduğudur
printf("\n%d. bilesende 1 dugum bulunmaktadir!!\n",index);
index++;//kaçıncı bileşeni yazdırdığımızı gösteren değişken
}
printf("\n1 dugum bulunan bilesenler sunlardir :\n");
for(j=0;j<dugum;j++){//bir düğüm bulunan bileşenleri yazdırdığımız yer
if(tutac[j]==0){//sıfır olması hiç kullanılmamış olması demektir yani tek kalmış/kullanılmamış düğüm
printf("%d ",j);
}
}
}//TekDugumleriYazdir fonksiyonu bitiş
//İçerisinde birden fazla düğüm olan grafı yazdırmak için kullanacağımız fonksiyon
int CokDugumleriYazdir(int dugum,int *icsayac,int *tutac){
int index=1;
int j,i;
for(j=1;j<dugum;j++){
if(icsayac[j]!=0){//icsayac dizisinin sıfırdan farklı olan elemanları index bileşeninde kaç düğün olduğunu gösteriyor
printf("\n%d. bilesende %d dugum bulunmaktadir!!\n",index,icsayac[j]);
printf("%d dugum sunlardir :",icsayac[j]);
for(i=0;i<dugum;i++){
if(tutac[i]==j){
printf("%d ",i);
}//if
}//for
printf("\n");
index++;
}//if
}//for
return index;
}//CokDugumleriYazdir fonksiyonu bitiş
int ToplamBilesenBul(int dugum,int *sayac,int *icsayac){
int toplambilesen=0,i;
for(i=0;i<dugum;i++){//sayac dizisinin elemanlarını toplayarak toplam bileşenlere ulaşabiliyoruz
toplambilesen=sayac[i]+toplambilesen;
}
return toplambilesen;
}
void DiziDuzelt(int k,int ata,int *tutac,int dugum){
//farklı iki sayıları tek bir sayıda toplamak için kullandığımız fonksiyon
int j;
for(j=0;j<dugum;j++){
if(tutac[j]==k){
tutac[j]=ata;
}
}
}
int main()
{ int dugum;//düğum sayısını tuttuğumuz bileşen
int kenarsayisi;//düğümler arası bağlantıları gösteren kenar sayısını tutan değişken
int *dugum1,*dugum2;//girilecek iki düğümü tutacağımız iki dizi
int *tutac;// hangi düğümlerin birbirine bağlı oldugunu tutacak dizimiz
int *sayac;//toplam bileşen sayısını bulmamızı sağlaması için farklı her agacı '1' leyecek dizimiz
int *icsayac;//her bağlı ağaçta kaç tane düğüm olduğunu tutacak dizimiz
int i,j;//döngü değişkenleri
int cmp;//sadece iki düğüm sıfır ise kaç atanacağını belirtmesi için kullanacağımız değişken
int index;//tek düğümlerin indislerini tutmak için kullandığımız değişken
int toplambilesen=0;//toplam bileşeni tutmak için kullandığımız değişken
int u,v;//dizilerde index kullanımı için kullanıyoruz
printf("Dugum sayisini girin :");
scanf("%d",&dugum);
printf("\nDugumler arasi baglantilari gosteren kenar sayisini girin :");
scanf("%d",&kenarsayisi);
dugum1=(int*)calloc(kenarsayisi,sizeof(int));
dugum2=(int*)calloc(kenarsayisi,sizeof(int));
printf("\nSirayla hangi iki dugum arasinin bagli oldugunu girin\n");
for(i=0;i<kenarsayisi;i++){
printf("\n%d. adim icin degerleri girin : \n",i+1);
scanf("%d%d",&dugum1[i],&dugum2[i]);
}
tutac=(int*)calloc((dugum),sizeof(int));
i=0;
cmp=0;
while(i<kenarsayisi){
u=dugum1[i];
v=dugum2[i];
if(tutac[u]+tutac[v]==0){
cmp++;
tutac[u]=cmp;
tutac[v]=cmp;
}
else{
if(tutac[u]!=tutac[v]){
if(tutac[u]==0){
tutac[u]=tutac[v];
}
else{
if(tutac[v]==0){
tutac[v]=tutac[u];
}
else{
DiziDuzelt(tutac[v],tutac[u],tutac,dugum);
} //else
} //else
}
} //else
i++;
} //while
sayac=(int*)calloc((dugum),sizeof(int));
icsayac=(int*)calloc((dugum),sizeof(int));
for(i=0;i<dugum;i++){//sayac ve icsayac dizisini dolduruyoruz
if(tutac[i]==0){ //sıfır sayısı tek düğümleri gösterecektir
sayac[0]++;
}
else{
sayac[tutac[i]]=1;
}
icsayac[tutac[i]]++;//kaç düğüm içeriyorsa onu dizide tutuyoruz
}
printf("\n");//görsel düzenleme
toplambilesen=ToplamBilesenBul(dugum,sayac,icsayac);//toplam bileşeni bulmak için fonksiyon kullanımı
printf("\n%d tane bagli bilesen bulunmaktadir!!",toplambilesen);//toplam bileşeni yazdırıyoruz
printf("\nBilesenlerin dugumleri asagidaki gibidir\n");
printf("\nTek dugumlu bilesenler en son gosterilecektir!!\n");
index=CokDugumleriYazdir(dugum,icsayac,tutac);//birden fazla düğüm içeren ağaçları yazdırmak için fonksiyona yolluyoruz
TekDugumleriYazdir(dugum,icsayac,tutac,index);//tek düğümleri yazdırmak için fonksiyona gönderiyoruz
printf("\n");//görsel düzenleme
system("PAUSE");
return 0;
}
Örnek
Graflar ve Programın Çalışması:
Hiç yorum yok:
Yorum Gönder