Haziran 1006

Bipartite Graph

Bipartite graph veya bigraph olarak bilinen bu graf, kendi aralarında bağımsız (bağlantı olmayan) sadece karşısındaki kümedeki düğümlerle bağlantısı olan 2 düğüm kümesinden oluşur. Graflar genelde karşımıza bu şekilde çıkmazlar. Daha karmaşıklardır. Onları bu hale getirmek uğraştırır. Bir grafın bipartite olup olmadığını öğrenmek için başka bir yöntem vardır: Kendimize bir kök (başlangıç) noktası seçeriz ve bu düğümü Mavi boyarız. Bu düğümden çıkan her kenarında sonunda yer alan düğümleri Kırmızı boyarız. Kırmızı düğümlerden ıkan her kenarın sonundaki düğümü de Mavi boyarız. Tüm renklendirme işlemi bittiğinde her kenarın her iki tarafındaki düğümlerin renkleri farklı ise graf Bipartite graph özelliğini taşır. Ancak bir tane bile uçları aynı renkte kenar olması durumunda graf bipartite değildir. En çok kullanıldığı alan eşleme problemleridir (Matching Problems). Aynı zamanda şifreli şekilde gelen verilerin çözülmesinde de kullanılabilir. Tags: , , , | Categories: Algoritma
BFS, kök düğümden başlayarak tüm elemanları tarayan ve komşulukları ortaya çıkaran bir graf arama algoritmasıdır. Çalışması sırasında son düğüme oluşana dek, keşfedilmiş tüm düğümlere komşu henüz keşfedilmemiş düğümleri keşfetme mantığını yürütür. Diklemesine değil, yataylamasına büyümeyi hedefler. Düğümlerin keşfediliş sıralarına göre farklı ağaçlar oluşturulabilir.   Pseudocode: unmark all vertices choose some starting vertex x mark x list L = x tree T = x while L nonempty choose some vertex v from front of list visit v for each unmarked neighbor w     mark w     add it to end of list     add edge (v,w) to T Liste olarak kuyruk tutmalıyız. FIFO kuralı uygulanacak.   Kuyruk kullanmadan da yapılabilir. Aşağıda yer alan C++ kodunda kuyruk kullanılmamıştır. bool Discovered[num]; for (int k = 0; k < num; k++) Discovered[k] = false; Node BFStree[num]; int i = 0; BFStree[i].data = 0; Node *temp; Discovered[i] = true; while ( i < num ) { temp = &BFStree[i]; for( int k = 0 ; k < num ; k++ ) { if ( matris[i][k] == 1 && !Discovered[k] ) { Discovered[k] = true; Node *newNode = new Node(k); temp->next = newNode; temp = newNode; } } i++; BFStree[i].data = i; } Not: Yukarıdaki kodu çalıştırmak için Adjacency matris kullanılmıştır. “num” adındaki değişken ise grafta yer alan eleman sayısını göstermektedir.   Sonuç olarak Adjencency matrisi sol aşağıdaki gibi olan bir grafın bfs algoritması sonucu oluşan spanning ağacı sağ aşağıdaki gibidir. 0 1 1 0 0 0 0 0                               1 2 3 1 0 1 1 1 0 0 0     2 4 5 1 1 0 0 1 0 1 1     3 7 8 0 1 0 0 1 0 0 0                   4     0 1 1 1 0 1 0 0     5 6   0 0 0 0 1 0 0 0     6     0 0 1 0 0 0 0 1     7     0 0 1 0 0 0 1 0     8     Tags: , , , , | Categories: Algoritma | C++