Çizge Algoritmaları
Çizge algoritmaları, graf teorisi temelinde çizgeler üzerinde çalışan algoritmalardır. Çizgeler, düğümler (noktalar) ve bu düğümleri birbirine bağlayan kenarlardan (çizgilerden) oluşur.
Çizge algoritmaları, çizgelerin özelliklerini ve ilişkilerini analiz ederek, çeşitli problemleri çözerler. Aşağıda, yaygın olarak kullanılan çizge algoritmalarından bazıları verilmiştir:
- Depth-First Search (DFS): Derinlik öncelikli arama algoritması olarak da bilinir. DFS, verilen bir çizgedeki düğümleri ziyaret etmek için kullanılır. Algoritma, bir düğümün komşularını ziyaret eder ve ardından o komşunun komşularını ziyaret etmeye devam eder. DFS, ağaç yapısını kontrol etmek veya bir yol aramak için kullanılabilir.
- Breadth-First Search (BFS): Genişlik öncelikli arama algoritması olarak da bilinir. BFS, DFS gibi verilen bir çizgedeki düğümleri ziyaret etmek için kullanılır, ancak BFS'de komşular sırayla ziyaret edilir. Bu, çizgedeki tüm en kısa yolları bulmak için kullanılabilir.
- Dijkstra's Algorithm: Dijkstra algoritması, bir çizgedeki düğümler arasındaki en kısa yolu bulmak için kullanılır. Algoritma, bir düğümün komşularına göre minimum mesafeyi bulur ve bu mesafeleri kullanarak tüm düğümlerin minimum mesafelerini hesaplar.
- Bellman-Ford Algoritması: Bellman-Ford algoritması, Dijkstra algoritması gibi en kısa yol bulmak için kullanılır, ancak negatif ağırlıklı kenarlar içeren çizgelerde de çalışır.
- Prim Algoritması: Prim algoritması, bir çizgedeki minimum ağacı bulmak için kullanılır. Algoritma, bir düğümü seçer ve diğer düğümlere olan en kısa mesafeleri kullanarak ağacı genişletir.
- Kruskal's Algorithm: Kruskal algoritması, bir çizgedeki minimum ağacı bulmak için kullanılır. Algoritma, tüm kenarları ağırlıklarına göre sıralar ve ardından minimum ağırlıklı kenarları ağaca ekler.
- Topological Sorting: Topolojik sıralama, bir çizgenin düğümlerini sıralamak için kullanılır. Algoritma, bir düğümün çıkış derecesi sıfır olan düğümlerle başlar ve ardından diğer düğümlere göre sıralar.
Bu çizge algoritmaları, farklı problemleri çözmek için kullanılabilir ve çizge teorisinde temel olarak kabul edilirler.
Depth-First Search (DFS)
Depth-First Search (DFS) graf gezinme algoritmasıdır. Bu algoritma, bir düğümün tüm alt düğümlerini ziyaret etmeden önce derinlemesine gitmeyi tercih eder. Yani, başlangıç düğümünden komsu düğümlere gitmek yerine, başlangıç düğümüne bağlı tüm düğümlere derinlemesine iner. DFS algoritması, öncelikle labirent gibi bir yapıdaki yol bulma problemlerinde kullanılır.
DFS algoritması, başlangıç düğümünü ziyaret eder, sonra başlangıç düğümünün herhangi bir komsu düğümüne gider ve o düğüme iner. Eğer o düğümde daha önce ziyaret edilmemiş bir düğüm varsa, o düğüme inmeye devam eder. Eğer tüm alt düğümleri ziyaret edildiyse, yani daha derine inmek mümkün değilse, o düğümün bir üst düğümüne geri döner. Bu işlemi tüm düğümleri ziyaret edene kadar devam eder.
Görselleştirilmiş bir örnek şu şekildedir:
Bu örnekte, DFS algoritması 1 numaralı düğümden başlar. 1 numaralı düğümün komşusu olan 2 numaralı düğüme gider ve onu ziyaret eder. 2 numaralı düğümün komşusu olan 3 numaralı düğüme gider ve onu ziyaret eder. 3 numaralı düğümün komşusu olan 4 numaralı düğüme gider ve onu ziyaret eder. 4 numaralı düğümün komşusu olan 5 numaralı düğüme gider ve onu ziyaret eder. 5 numaralı düğümün komşusu olan 6 numaralı düğüme gider ve onu ziyaret eder. Artık daha derine inmek mümkün olmadığı için geri döner ve sonraki komşu düğümüne gider. Bu şekilde tüm düğümler ziyaret edilene kadar devam eder.
Breadth-First Search (BFS)
Breadth-First Search (BFS), bir çizgenin gezilmesi için kullanılan bir algoritmadır. Bu algoritma, çizgede verilen bir başlangıç düğümünden başlayarak, bu düğüme doğrudan bağlı olan düğümleri keşfetmeye başlar. Sonra, bu düğümlerden her birine doğrudan bağlı olan düğümleri keşfeder ve böylece ilerler. Yani, önce derinlik sırasında keşfetmek yerine, seviye seviye keşfeder.
BFS, genişlik önceliği sırasıyla çalışır. BFS algoritmasının temel amacı, çizgedeki tüm düğümlere en kısa yolculuk mesafesini hesaplamaktır. BFS algoritmasının zaman karmaşıklığı O(V+E) 'dir, burada V, düğümlerin sayısını ve E, kenarların sayısını ifade eder.
Bir örnek vermek gerekirse, aşağıdaki grafiği ele alalım:
1
/ \
2 3
/ \ \
4 5 6
Başlangıç düğümü olarak 1 seçildiğinde, BFS aşağıdaki adımları takip eder:
- Başlangıç düğümü 1 işaretlenir ve kuyruğa eklenir.
- Kuyruktan 1 çıkarılır ve işlenir.
- 1'in doğrudan bağlantısı olan 2 ve 3 işaretlenir ve kuyruğa eklenir.
- Kuyruktan 2 çıkarılır ve işlenir.
- 2'nin doğrudan bağlantısı olan 4 ve 5 işaretlenir ve kuyruğa eklenir.
- Kuyruktan 3 çıkarılır ve işlenir.
- 3'ün doğrudan bağlantısı olan 6 işaretlenir ve kuyruğa eklenir.
- Kuyruktan 4 çıkarılır ve işlenir.
- Kuyruktan 5 çıkarılır ve işlenir.
- Kuyruktan 6 çıkarılır ve işlenir.
BFS algoritmasının sonuç olarak ürettiği gezinme sırası şöyle olacaktır: 1, 2, 3, 4, 5, 6.
BFS algoritmasının görselleştirilmesi için aşağıdaki örneği inceleyebilirsiniz:
Dijkstra Algoritması
Dijkstra algoritması, bir ağırlıklı çizgedeki bir kaynak düğümden diğer tüm düğümlere en kısa yolu bulmak için kullanılan bir algoritmadır. Bu algoritma, adını Hollandalı bilgisayar bilimcisi Edsger W. Dijkstra'dan almaktadır.
Dijkstra algoritması, genellikle BFS (breadth-first search) kullanarak gerçekleştirilir. BFS, Dijkstra'nın algoritması için en uygun veri yapısıdır, çünkü BFS, tüm düğümleri her düzeyde tek tek kontrol eder ve algoritmanın doğruluğunu sağlar.
Algoritmanın temel işleyişi şöyledir:
- Başlangıç düğümüne en kısa mesafe sıfır atanır ve tüm diğer düğümler sonsuz mesafeye atanır.
- Başlangıç düğümünden başlayarak, ziyaret edilmemiş en yakın düğüm seçilir.
- Seçilen düğüme doğru bir yolda ziyaret edilmemiş tüm düğümler için, başlangıç düğümünden seçilen düğüme kadar olan mesafe ile seçilen düğüm ile hedef düğüm arasındaki mesafe toplanır.
- Hedef düğüme varıldığında, en kısa mesafe belirlenir ve bu mesafe, hedef düğümün mesafesi olarak atanır.
- Tüm düğümler ziyaret edilene kadar işlem tekrarlanır.
Dijkstra algoritması, minimum mesafeyi bulur ve aynı zamanda en kısa yolun nasıl bulunacağını da gösterir. Algoritma, ağırlıklı bir çizge içindeki iki düğüm arasındaki en kısa yolun bulunmasına yardımcı olur.
Dijkstra Algoritması'nın çalışma prensibini gösteren bir görselleştirme aşağıdaki şekildedir:
Bu animasyonda, mavi düğümler ziyaret edilmiş düğümleri, sarı düğümler işlemde olan düğümleri, yeşil düğümler ise sonuca ulaşmak için seçilen yolu göstermektedir.
Bellman-Ford Algoritması
Bellman-Ford Algoritması, tek kaynak en kısa yol problemi için kullanılan bir çizge algoritmasıdır. Bu algoritma, grafikteki tüm düğümlere (veya belirli bir düğüm kümesine) en kısa yolu bulur.
Algoritmanın çalışma mantığı, her düğümün başlangıçta sonsuz olarak belirlenen bir mesafeye sahip olduğu ve ardından düğümler arasındaki kenarların mesafelerinin hesaplandığı bir dizi döngü kullanarak en kısa yolun hesaplanmasıdır. Bu işlem, tüm düğümler için en kısa yolu bulana kadar tekrarlanır.
Bu video Bellman-Ford algoritmasının nasıl çalıştığını açıklayan bir animasyon içermektedir: https://www.youtube.com/watch?v=obWXjtg0L64
Prim's Algoritması
Prim algoritması, bir ağırlıklı çizgede minimum ağırlıklı ağaç oluşturmak için kullanılan bir algoritmadır.
Adım adım çalışma mantığı şu şekildedir:
- Başlangıç düğümü seçilir ve ağaç olarak işaretlenir.
- Tüm kenarlar ağırlıklarına göre bir öncelik kuyruğuna eklenir.
- Kuyruktan en düşük ağırlıklı kenar alınır. Bu kenarın bir ucunda ağaçta bir düğüm varsa ve diğer ucunda ağaçta olmayan bir düğüm varsa, bu düğüm ağaçta işaretlenir ve kenar ağaç kenarı olarak eklenir.
- Adım 3'ü toplam düğüm sayısına kadar tekrarlanır.
#include <stdio.h>
#include <limits.h>
#define V 5
int minKey(int key[], int mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == 0 && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
int printMST(int parent[], int graph[V][V]) {
printf("Kenar\tAğırlık\n");
for (int i = 1; i < V; i++)
printf("%d - %d\t%d \n", parent[i], i, graph[i][parent[i]]);
}
void primMST(int graph[V][V]) {
int parent[V];
int key[V];
int mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = 0;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = 1;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}
int main() {
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
primMST(graph);
return 0;
}
Bu kod, 5 düğümlü bir ağırlıklı çizgenin kenarlarını temsil eden bir 2 boyutlu diziyi (graph) kullanarak, Prim algoritmasını kullanarak minimum kesintili ağacı (minimum spanning tree) hesaplar ve sonucu ekrana yazdırır.
Kruskal Algoritması
Kruskal algoritması, en küçük ağırlıklı kenardan başlayarak ağacın oluşmasını sağlayan bir ağaç oluşturma algoritmasıdır. Algoritmanın adı, onu geliştiren Joseph Kruskal'den gelir.
Kruskal algoritmasının aşamaları şöyledir:
- Tüm kenarları ağırlıklarına göre küçükten büyüğe sırala.
- Her düğümü kendi ayrık kümelerine yerleştir.
- Kenarları ağırlık sırasına göre al ve başlangıç ve bitiş düğümleri aynı ayrık kümede olmayana kadar ekle.
- Ayrık kümeleri birleştir.
Bu adımlar, ağaçtaki her bir düğümün bir ayrık kümede olduğu ve her yeni eklenen kenarın farklı ayrık kümelerdeki düğümleri birleştirdiği bir ağaç oluşturur. Algoritma, tüm kenarları ağırlıklarına göre sıralayarak en küçük ağırlıklı kenarı seçer ve ayrık kümeleri birleştirir. Bu işlem, en küçük ağırlıklı ikinci kenarın seçilmesi ve birleştirilmesiyle devam eder ve bu şekilde en küçük ağırlıklı son kenar eklenene kadar devam eder. Sonuçta, ağaç oluşur ve minimum ağırlığa sahip olur.
#include <stdio.h>
#include <stdlib.h>
#define MAX_EDGES 1000
typedef struct {
int u, v, w;
} edge;
edge edges[MAX_EDGES];
int cmp(const void* a, const void* b) {
edge* x = (edge*)a;
edge* y = (edge*)b;
return x->w - y->w;
}
int find(int* parent, int i) {
if (parent[i] == -1) {
return i;
}
return find(parent, parent[i]);
}
void Union(int* parent, int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
void KruskalMST(int V, int E) {
int* parent = (int*)malloc(sizeof(int) * V);
for (int i = 0; i < V; ++i) {
parent[i] = -1;
}
qsort(edges, E, sizeof(edge), cmp);
edge* result = (edge*)malloc(sizeof(edge) * (V - 1));
int i = 0;
int e = 0;
while (e < V - 1 && i < E) {
edge next_edge = edges[i++];
int x = find(parent, next_edge.u);
int y = find(parent, next_edge.v);
if (x != y) {
result[e++] = next_edge;
Union(parent, x, y);
}
}
printf("Minimum Spanning Tree:\n");
for (i = 0; i < e; ++i) {
printf("%d -- %d == %d\n", result[i].u, result[i].v, result[i].w);
}
free(parent);
free(result);
}
int main() {
int V = 4;
int E = 5;
edges[0].u = 0;
edges[0].v = 1;
edges[0].w = 10;
edges[1].u = 0;
edges[1].v = 2;
edges[1].w = 6;
edges[2].u = 0;
edges[2].v = 3;
edges[2].w
Topolojik Sıralama
Topolojik Sıralama, bir çizgenin düğümlerini belli bir sıraya göre sıralamak için kullanılan bir algoritmadır. Bu sıralama, çizgedeki herhangi bir düğümün, ondan önceki düğümlerle bağlantısı olmamasını garanti eder. Bu, özellikle çizgede yönlendirilmiş döngülerin olmaması durumunda önemlidir.
Topolojik Sıralama, öncelikle çizgede bir başlangıç düğümü belirler ve bu düğümün çıkışları üzerinde ilerler. Her bir çıkışa ait hedef düğüme, kaynak düğümün bağlantısının kesilmesiyle ilerlenir. Bu şekilde, çizgedeki tüm düğümler sıralanır.
Topolojik Sıralama ayrıca, bir çizgenin döngü içerip içermediğini de kontrol edebilir. Bu durumda, çizgedeki döngüyü saptamak ve gerekli değişiklikleri yapmak için farklı bir algoritma kullanılmalıdır.
Topolojik Sıralama'nın kullanım alanları arasında programlama dillerindeki bağımlılık yönetimi, yapay zeka, veri analizi ve ağ tasarımı gibi alanlar yer almaktadır.
#include <stdio.h>
#define MAX 100
int adj[MAX][MAX],indeg[MAX],n;
void create_graph()
{
int i,max_edges,origin,destin;
printf("\nEnter number of vertices : ");
scanf("%d",&n);
max_edges = n*(n-1);
for(i=1;i<=max_edges;i++)
{
printf("\nEnter edge %d( -1 -1 to quit ) : ",i);
scanf("%d %d",&origin,&destin);
if((origin == -1) && (destin == -1))
break;
if( origin >= n || destin >= n || origin<0 || destin<0)
{
printf("\nInvalid edge!\n");
i--;
}
else
{
adj[origin][destin] = 1;
indeg[destin]++;
}
}
}
void topological_sort()
{
int i,k,top=-1,s[MAX],stack_empty();
for(i=0;i<n;i++)
if(indeg[i] == 0)
s[++top] = i;
while(top != -1)
{
k = s[top--];
printf("%d ",k);
for(i=0;i<n;i++)
{
if(adj[k][i] == 1)
{
adj[k][i] = 0;
indeg[i]--;
if(indeg[i] == 0)
s[++top]=i;
}
}
}
}
int stack_empty()
{
if(top == -1)
return 1;
else
return 0;
}
int main()
{
create_graph();
printf("\nTopological Order: ");
topological_sort();
printf("\n");
return 0;
}