C++ ile Graph Algoritmaları

Graph algoritmaları, bilgisayar bilimi ve mühendislik alanında önemli bir yer tutar. Birçok gerçek dünya problemini çözmek için kullanılır. C++ programlama dili, verimliliği ve güçlü veri yapıları ile bu algoritmaları uygulamak için oldukça uygundur. Bu yazıda, C++ ile bazı temel graph algoritmalarını inceleyeceğiz.

Öncelikle, graph yapısını temsil etmenin birkaç yolu vardır. En yaygın yöntemler arasında adjacency matrix ve adjacency list yer alır. Adjacency matrix, graph'daki her bir düğüm için bir matris oluşturur ve kenarların varlığına göre matrisin elemanlarını doldurur. Ancak, büyük graph'lar için bellek kullanımı açısından verimsiz olabilir. Diğer taraftan, adjacency list, her düğüm için bir liste oluşturarak sadece mevcut kenarları saklar. Bu, bellek verimliliği sağlar ve genellikle daha hızlıdır.

Graph algoritmalarına örnek olarak, Dijkstra'nın en kısa yol algoritması ve Depth First Search (DFS) algoritmasını ele alalım. Dijkstra algoritması, bir graph'daki kaynak düğümden diğer tüm düğümlere en kısa yolu bulmak için kullanılır. C++ ile Dijkstra algoritması uygulamak için, öncelikle bir priority queue yapısı kullanarak, en kısa yolları bulmak için düğümleri sıralayabiliriz. Aşağıda basit bir Dijkstra algoritması örneği bulunmaktadır:

[code]
#include
#include
#include
#include

using namespace std;

void dijkstra(int source, vector& graph) {
priority_queue pq;
vector distance(graph.size(), INT_MAX);

pq.push({0, source});
distance[source] = 0;

while (!pq.empty()) {
int u = pq.top().second;
pq.pop();

for (auto& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;

if (distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
pq.push({distance[v], v});
}
}
}

for (int i = 0; i < distance.size(); i++) {
cout