Anasayfa » Algoritmalar, Veri Yapıları

Breadth First Search ve Depth First Search Algoritmaları

30 Aralık 2011 27.069 kez okundu 2 yorum
1 Star2 Stars3 Stars4 Stars5 Stars (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

  1. Fonksiyona gönderilen node kuyruğa atılır.
  2. Kuyruk boşalıncaya kadar döngü sürdürülür.
  3. Sıradaki node kuyruktan çıkarılır.
  4. Çı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-&gt;next=rear;
	temp-&gt;item=item;
	return temp;
}
int isFull()
{
	return 0;
}
int isEmpty()
{
	return front==NULL;
}
Item get()
{
	if(!isEmpty())
	{
		Item item=front-&gt;item;
		struct node* temp=front-&gt;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-&gt;next=neww(rear-&gt;next,item));
		rear=rear-&gt;next;
	}
}
////////////////Queue Yapısı Sonu /////////////////////
int findIndex(struct vertex *ver ,char member)
{
	int i;
	for(i=0;iletter)].color=='W')
			{
				arr[findIndex(arr,mem-&gt;letter)].color='G';
				printf("%C -&gt; color = Gray\n",arr[findIndex(arr,mem-&gt;letter)].item);
				arr[findIndex(arr,mem-&gt;letter)].distance=ver.distance+1;
				arr[findIndex(arr,mem-&gt;letter)].parent=&amp;ver;
				put(arr[findIndex(arr,mem-&gt;letter)]);
				printf("%C puts in queue\n",arr[findIndex(arr,mem-&gt;letter)].item);
			}
			mem=mem-&gt;next;
		}
		ver.color='B';
		printf("%C -&gt; 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-&gt;letter='D';
	arr[0].connection-&gt;next=NULL;
 
	arr[1].connection= (struct members*)malloc(sizeof(struct members));
	arr[1].connection-&gt;letter='C';
	arr[1].connection-&gt;next=(struct members*)malloc(sizeof(struct members));
	arr[1].connection-&gt;next-&gt;letter='E';
	arr[1].connection-&gt;next-&gt;next=NULL;
 
	arr[2].connection=NULL;
 
	arr[3].connection= (struct members*)malloc(sizeof(struct members));
	arr[3].connection-&gt;letter='B';
	arr[3].connection-&gt;next=(struct members*)malloc(sizeof(struct members));
	arr[3].connection-&gt;next-&gt;letter='F';
	arr[3].connection-&gt;next-&gt;next=NULL;
 
	arr[4].connection= (struct members*)malloc(sizeof(struct members));
	arr[4].connection-&gt;letter='D';
	arr[4].connection-&gt;next=(struct members*)malloc(sizeof(struct members));
	arr[4].connection-&gt;next-&gt;letter='C';
	arr[4].connection-&gt;next-&gt;next=(struct members*)malloc(sizeof(struct members));
	arr[4].connection-&gt;next-&gt;next-&gt;letter='F';
	arr[4].connection-&gt;next-&gt;next-&gt;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

  1. İlk olarak birinic node stack a konur.
  2. Stack boşalıncaya kadar döngü devam eder.
  3. Stack dan node alınır.
  4. 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.
  5. 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-&gt;next=rear;
	temp-&gt;item=item;
	return temp;
}
int isFull()
{
	return 0;
}
int isEmpty()
{
	return front==NULL;
}
Item get()
{
	if(!isEmpty())
	{
		Item item=front-&gt;item;
		struct node* temp=front-&gt;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-&gt;next=neww(rear-&gt;next,item));
		rear=rear-&gt;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-&gt;letter)].parent=&amp;ver;
			int index =findIndex(arr,mem-&gt;letter);
			dfs_visit(arr[index],arr);
		}
		mem=mem-&gt;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 -&gt; color = Black\n",ver.item);
	times = times + 1;
	ver.finish=times;//finish time olara noda yazıyoruz
	printf("%C -&gt; finish time = %d\n",ver.item,ver.finish);
}
//Bütün nodları çağırır
void dfs(struct vertex *&amp; arr)
{
	int i;
	times=0;
	//Bütün nodların rengini beyaz parentini null yapıyoruz
	for(i=0;iletter='D';
	arr[0].connection-&gt;next=NULL;
 
	arr[1].connection= (struct members*)malloc(sizeof(struct members));
	arr[1].connection-&gt;letter='C';
	arr[1].connection-&gt;next=(struct members*)malloc(sizeof(struct members));
	arr[1].connection-&gt;next-&gt;letter='E';
	arr[1].connection-&gt;next-&gt;next=NULL;
 
	arr[2].connection=NULL;
 
	arr[3].connection= (struct members*)malloc(sizeof(struct members));
	arr[3].connection-&gt;letter='B';
	arr[3].connection-&gt;next=(struct members*)malloc(sizeof(struct members));
	arr[3].connection-&gt;next-&gt;letter='F';
	arr[3].connection-&gt;next-&gt;next=NULL;
 
	arr[4].connection= (struct members*)malloc(sizeof(struct members));
	arr[4].connection-&gt;letter='D';
	arr[4].connection-&gt;next=(struct members*)malloc(sizeof(struct members));
	arr[4].connection-&gt;next-&gt;letter='C';
	arr[4].connection-&gt;next-&gt;next=(struct members*)malloc(sizeof(struct members));
	arr[4].connection-&gt;next-&gt;next-&gt;letter='F';
	arr[4].connection-&gt;next-&gt;next-&gt;next=NULL;
 
	arr[5].connection=NULL;
 
	dfs(arr);//gezinme fonksiyonumuz çağrılıyor
	return 0;
}

<<< Önceki:

Sonraki: >>>


Facebookta Paylaş

2 yorum »

  • Furkan dedi ki:

    Çok güzel bir yazı olmuş. Elinize sağlık

  • Ahmet Selim dedi ki:

    Emeğinize sağlık hocam. Güzel bir anlatım olmuş. Allah razı olsun.

Yorum Bırakın!

Yorum yaz, yada kendi sitende trackback (Geri besleme) olarak ekle. Ayrıca RSS ile bu konuya üye olabilirsin. .

Nazik olun. Temiz tutun. Konu dışına çıkmayın. Spam yaratmayın.

Bu tagları kullanabilirsiniz:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Bloğumuz gavatarı desteklemektedir. Kendi gavatarınızı edinmek için lütfen Gravatar a üye olun.