Breadth First Search ve Depth First Search Algoritmaları
30 Aralık 2011
27.069 kez okundu
2 yorum
(2 oy,5 üzerinden : 4,00 )
Loading...
(2 oy,5 üzerinden : 4,00 )Loading...
Breadth first search ve depth first search algoritmaları graph larda gezinme ve arama algoritmalarıdır.
Bu graphlarda ilişkiler iki şekilde tutulabilir. İki boyutlu array ve linked listler ile
Matrix şeklinde ilişkiler
Link List şeklinde ilişkiler
Breadth First Search (Sığ Öncelikli Arama)
BFS (breadth first search) algoritmasının çalışma mantığı şu şekildedir. Verilen bir node dan başlayarak ilgili node un tüm komşuları gezilir. Daha sonra gezilen komşuların komşuları gezilerek verilen graph gezilmiş olur.
Algoritma
- Fonksiyona gönderilen node kuyruğa atılır.
- Kuyruk boşalıncaya kadar döngü sürdürülür.
- Sıradaki node kuyruktan çıkarılır.
- Çıkarılan node daha önce gezilmemiş ise, gezildi işareti konur ve gezilmemiş komşuları kuyruğa konur.
Pseudo kodunu şöyle yazabiliriz.
public void bfs() { //BFS uses Queue data structure Queue q=new LinkedList(); q.add(this.rootNode); printNode(this.rootNode); rootNode.visited=true; while(!q.isEmpty()) { Node n=(Node)q.remove(); Node child=null; while((child=getUnvisitedChildNode(n))!=null) { child.visited=true; printNode(child); q.add(child); } } //Clear visited property of nodes clearNodes(); } |
Alttaki şekil de verilen bir graph ın gezilirken nasıl renklendirildiğini görebilirsiniz
Ayrıca buradaki animasyonu izleyebilirsiniz.
Şekil 1
Örneğin şekil 1 için bfs algoritmasıda c kodunu yazmak istersek şu şekilde bir kod yazabiliriz.
#include <stdio.h> #include <math.h> #include <stdlib.h> #include <time.h> struct vertex { char item; char color; int distance; struct vertex * parent; struct members *connection; }; struct members { char letter; struct members * next; }; ////////////////Queue Yapısı Başlangıcı ///////////////////// typedef struct vertex Item; struct node { Item item; struct node *next; }; static struct node*front; static struct node*rear; int maxN; void queueInıt(int maxN) { front=NULL; rear=NULL; } struct node* neww(struct node*rear,Item item) { struct node *temp=(struct node*)malloc(sizeof(struct node)); temp->next=rear; temp->item=item; return temp; } int isFull() { return 0; } int isEmpty() { return front==NULL; } Item get() { if(!isEmpty()) { Item item=front->item; struct node* temp=front->next; free(front); front=temp; if(front==NULL) rear=NULL; return item; } else { //puts("Error: queue is empty"); } } void put(Item item) { if(front==NULL) front=(rear=neww(rear,item)); else { (rear->next=neww(rear->next,item)); rear=rear->next; } } ////////////////Queue Yapısı Sonu ///////////////////// int findIndex(struct vertex *ver ,char member) { int i; for(i=0;iletter)].color=='W') { arr[findIndex(arr,mem->letter)].color='G'; printf("%C -> color = Gray\n",arr[findIndex(arr,mem->letter)].item); arr[findIndex(arr,mem->letter)].distance=ver.distance+1; arr[findIndex(arr,mem->letter)].parent=&ver; put(arr[findIndex(arr,mem->letter)]); printf("%C puts in queue\n",arr[findIndex(arr,mem->letter)].item); } mem=mem->next; } ver.color='B'; printf("%C -> color = Black\n",ver.item); } } int main() { queueInıt(1);//Queue initialize ediliyor struct vertex * arr = (struct vertex*)malloc(sizeof(struct vertex)*6); arr[0].item='A'; arr[1].item='B'; arr[2].item='C'; arr[3].item='D'; arr[4].item='E'; arr[5].item='F'; //Bağlantılar atanıyor arr[0].connection= (struct members*)malloc(sizeof(struct members)); arr[0].connection->letter='D'; arr[0].connection->next=NULL; arr[1].connection= (struct members*)malloc(sizeof(struct members)); arr[1].connection->letter='C'; arr[1].connection->next=(struct members*)malloc(sizeof(struct members)); arr[1].connection->next->letter='E'; arr[1].connection->next->next=NULL; arr[2].connection=NULL; arr[3].connection= (struct members*)malloc(sizeof(struct members)); arr[3].connection->letter='B'; arr[3].connection->next=(struct members*)malloc(sizeof(struct members)); arr[3].connection->next->letter='F'; arr[3].connection->next->next=NULL; arr[4].connection= (struct members*)malloc(sizeof(struct members)); arr[4].connection->letter='D'; arr[4].connection->next=(struct members*)malloc(sizeof(struct members)); arr[4].connection->next->letter='C'; arr[4].connection->next->next=(struct members*)malloc(sizeof(struct members)); arr[4].connection->next->next->letter='F'; arr[4].connection->next->next->next=NULL; arr[5].connection=NULL; bfs(arr,0); return 0; } |
Depth First Search (Derin Öncelikli Arama)
DFS (depth first search) algoritmasının çalışma mantığı şu şekildedir. Verilen graph daki tüm node lar gezilecek şekilde, sırayla ziyaret edilen bir nodun komşularına gidilir, gezilmemiş bir komşusu varsa ona gidilir, ve daha sonra sıradaki kendi komşusundan önce komşusunun komşusuna gidilir. Böylece sürekli derine inilir. Daha sonra gezilmemiş node kalmayınca bir geri noda gelinir ve sıradaki komşu ve komşunun komşusu…. şeklinde devam eder. Bu algoritmada tüm graph gezilir(graphlarda bağlantısız node lar olsa da)
Algoritma
- İlk olarak birinic node stack a konur.
- Stack boşalıncaya kadar döngü devam eder.
- Stack dan node alınır.
- Eğer alınan node gezilmemiş ise, komşularına bakılır, komşularından gezilmemiş olan varsa alınır ve stack a atılır.
- Eğer gezilmemiş bir komşu kalmadıysa stackdan yeni node alınır.
Pseudo kodunu şöyle yazabiliriz.
public void dfs() { //DFS uses Stack data structure Stack s=new Stack(); s.push(this.rootNode); rootNode.visited=true; printNode(rootNode); while(!s.isEmpty()) { Node n=(Node)s.peek(); Node child=getUnvisitedChildNode(n); if(child!=null) { child.visited=true; printNode(child); s.push(child); } else { s.pop(); } } //Clear visited property of nodes clearNodes(); } |
Ayrıca buradaki animasyonu izleyebilirsiniz
Şimdi şekil 1 için dfs algoritmasının c kodunu yazalım
#include <stdio.h> #include <math.h> #include <stdlib.h> #include <time.h> int times;//depth first search için global zaman değişkeni struct vertex//node bilgilerini tutan struct { char item; char color; int discovery; int finish; struct vertex * parent; struct members *connection; }; struct members//node lar arası ilişkiyi tutan linked list yapıdaki struct { char letter; struct members * next; }; ////////////////Queue Yapısı Başlangıcı ///////////////////// typedef struct vertex Item; struct node { Item item; struct node *next; }; static struct node*front; static struct node*rear; int maxN; void queueInıt(int maxN) { front=NULL; rear=NULL; } struct node* neww(struct node*rear,Item item) { struct node *temp=(struct node*)malloc(sizeof(struct node)); temp->next=rear; temp->item=item; return temp; } int isFull() { return 0; } int isEmpty() { return front==NULL; } Item get() { if(!isEmpty()) { Item item=front->item; struct node* temp=front->next; free(front); front=temp; if(front==NULL) rear=NULL; return item; } else { //puts("Error: queue is empty"); } } void put(Item item) { if(front==NULL) front=(rear=neww(rear,item)); else { (rear->next=neww(rear->next,item)); rear=rear->next; } } ////////////////Queue Yapısı Sonu ///////////////////// //depth first search için ilişkiler listesinden gelen bir elemanın ana arrayda kaçıncı sırada olduğunu bulur int findIndex(struct vertex *ver ,char member) { int i; for(i=0;iletter)].color=='W')//sırası gelen node beyaz ise bu nodu baz alarak visit fonksiyonunu tekrar çağırıyoruz { arr[findIndex(arr,mem->letter)].parent=&ver; int index =findIndex(arr,mem->letter); dfs_visit(arr[index],arr); } mem=mem->next;//sıradaki ilişki } ver.color='B';//ilgili nodun bütün komşulukları depth olarak gezildikten sonra rengini siyah yapıyoruz printf("%C -> color = Black\n",ver.item); times = times + 1; ver.finish=times;//finish time olara noda yazıyoruz printf("%C -> finish time = %d\n",ver.item,ver.finish); } //Bütün nodları çağırır void dfs(struct vertex *& arr) { int i; times=0; //Bütün nodların rengini beyaz parentini null yapıyoruz for(i=0;iletter='D'; arr[0].connection->next=NULL; arr[1].connection= (struct members*)malloc(sizeof(struct members)); arr[1].connection->letter='C'; arr[1].connection->next=(struct members*)malloc(sizeof(struct members)); arr[1].connection->next->letter='E'; arr[1].connection->next->next=NULL; arr[2].connection=NULL; arr[3].connection= (struct members*)malloc(sizeof(struct members)); arr[3].connection->letter='B'; arr[3].connection->next=(struct members*)malloc(sizeof(struct members)); arr[3].connection->next->letter='F'; arr[3].connection->next->next=NULL; arr[4].connection= (struct members*)malloc(sizeof(struct members)); arr[4].connection->letter='D'; arr[4].connection->next=(struct members*)malloc(sizeof(struct members)); arr[4].connection->next->letter='C'; arr[4].connection->next->next=(struct members*)malloc(sizeof(struct members)); arr[4].connection->next->next->letter='F'; arr[4].connection->next->next->next=NULL; arr[5].connection=NULL; dfs(arr);//gezinme fonksiyonumuz çağrılıyor return 0; } |
Bunlara da Göz Atmak İsteyebilirsiniz.
Rica: Sitemizin Google'da daha üst sıralarda çıkması için lütfen alttaki Google+ veya Begen butonuna tıklayınız , ya da yazılarımızı Facebookta Paylaş butonu ile paylaşabilirsiniz.
Yazılarımızı okuyan okurlarımızın yorumlarını bizimle paylaşmaları, bizi daha çok yazı yazmaya teşvik edecektir. Lütfen yorumlarınızı, görüşlerinizi, eleştirilerinizi bizden esirgemeyin.
<<< Önceki: C# ile Local Mysql Veritabanı Bağlantısı
Sonraki: ProjeKent 2012 Proje Yarışma Başvuruları Başladı >>>
Çok güzel bir yazı olmuş. Elinize sağlık
Emeğinize sağlık hocam. Güzel bir anlatım olmuş. Allah razı olsun.
Yorum Bırakın!
En Son Yazılanlar
Codeigniter Dersleri
Kategoriler
Teknoloji Haberleri
Android Dersleri
Arşiv
İstatistikler
Sitemizin QR Kodu
Yeniliklerden İlk Sizin Haberiniz Olsun
KodMerkezi.Net Facebookta
En Çok Okunanlar
En Son Aranan Kelimeler
En Çok Oy Alanlar
Etiket Bulutu
İlginizi Çekecek Siteler