Graf Temelleri Graph Fundamentals

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    int** matris;
    int   dugumSayisi;
    bool  yonlu;
} MatrisGraf;

/* Graf oluştur */
MatrisGraf* matrisGrafOlustur(int V, bool yonlu) {
    MatrisGraf* g = malloc(sizeof(MatrisGraf));
    g->dugumSayisi = V;
    g->yonlu = yonlu;
    g->matris = malloc(V * sizeof(int*));
    for (int i = 0; i < V; i++) {
        g->matris[i] = calloc(V, sizeof(int));
    }
    return g;
}

/* Kenar ekle */
void matrisKenarEkle(MatrisGraf* g, int src, int dst, int agirlik) {
    g->matris[src][dst] = agirlik;
    if (!g->yonlu)
        g->matris[dst][src] = agirlik;  // yönsüz → simetrik
}

/* Kenar var mı? */
bool matrisKenarVar(MatrisGraf* g, int src, int dst) {
    return g->matris[src][dst] != 0;
}

/* Düğümün komşularını listele */
void matrisKomsular(MatrisGraf* g, int v) {
    printf("Düğüm %d komşuları: ", v);
    for (int i = 0; i < g->dugumSayisi; i++)
        if (g->matris[v][i] != 0)
            printf("%d(%d) ", i, g->matris[v][i]);
    printf("\n");
}

/* Matris yazdır */
void matrisYazdir(MatrisGraf* g) {
    printf("    ");
    for (int j = 0; j < g->dugumSayisi; j++)
        printf("%3d", j);
    printf("\n");
    for (int i = 0; i < g->dugumSayisi; i++) {
        printf("[%d] ", i);
        for (int j = 0; j < g->dugumSayisi; j++)
            printf("%3d", g->matris[i][j]);
        printf("\n");
    }
}

/* Komşuluk listesi düğümü */
typedef struct KomsulukNode {
    int hedef;           // komşu düğüm ID
    int agirlik;         // kenar ağırlığı (ağırlıksızsa 1)
    struct KomsulukNode* next;
} KomsulukNode;

/* Graf yapısı */
typedef struct {
    KomsulukNode** listeler;  // her düğüm için bağlı liste başı
    int  dugumSayisi;
    int  kenarSayisi;
    bool yonlu;
} ListeGraf;

/* Graf oluştur */
ListeGraf* listeGrafOlustur(int V, bool yonlu) {
    ListeGraf* g = malloc(sizeof(ListeGraf));
    g->dugumSayisi = V;
    g->kenarSayisi = 0;
    g->yonlu = yonlu;
    g->listeler = calloc(V, sizeof(KomsulukNode*));
    return g;
}

/* Yardımcı — listeye düğüm ekle */
static KomsulukNode* yeniNode(int hedef, int agirlik) {
    KomsulukNode* n = malloc(sizeof(KomsulukNode));
    n->hedef   = hedef;
    n->agirlik = agirlik;
    n->next    = NULL;
    return n;
}

/* Kenar ekle */
void listeKenarEkle(ListeGraf* g, int src, int dst, int agirlik) {
    // src → dst
    KomsulukNode* n = yeniNode(dst, agirlik);
    n->next = g->listeler[src];
    g->listeler[src] = n;

    if (!g->yonlu) {
        // dst → src (yönsüz → çift yönlü)
        n = yeniNode(src, agirlik);
        n->next = g->listeler[dst];
        g->listeler[dst] = n;
    }
    g->kenarSayisi++;
}

/* Komşuları listele */
void listeKomsular(ListeGraf* g, int v) {
    printf("[%d] → ", v);
    KomsulukNode* curr = g->listeler[v];
    while (curr) {
        printf("%d(%d) ", curr->hedef, curr->agirlik);
        curr = curr->next;
    }
    printf("∅\n");
}

/* Tüm grafı yazdır */
void listeGrafYazdir(ListeGraf* g) {
    printf("Graf: %d düğüm, %d kenar (%s)\n",
           g->dugumSayisi, g->kenarSayisi,
           g->yonlu ? "yönlü" : "yönsüz");
    for (int i = 0; i < g->dugumSayisi; i++)
        listeKomsular(g, i);
}

/* Kenar var mı? — O(deg(src)) */
bool listeKenarVar(ListeGraf* g, int src, int dst) {
    KomsulukNode* curr = g->listeler[src];
    while (curr) {
        if (curr->hedef == dst) return true;
        curr = curr->next;
    }
    return false;
}

/* Düğüm derecesi */
int listeDerece(ListeGraf* g, int v) {
    int deg = 0;
    KomsulukNode* curr = g->listeler[v];
    while (curr) { deg++; curr = curr->next; }
    return deg;
}

int main() {
    // ── Yönsüz graf ──
    ListeGraf* g = listeGrafOlustur(4, false);
    listeKenarEkle(g, 0, 1, 1);
    listeKenarEkle(g, 0, 2, 1);
    listeKenarEkle(g, 0, 3, 1);
    listeKenarEkle(g, 1, 2, 1);
    listeKenarEkle(g, 2, 3, 1);
    listeGrafYazdir(g);

    printf("\nKenar (0,2): %s\n",
           listeKenarVar(g,0,2) ? "var ✓" : "yok");
    printf("Kenar (1,3): %s\n",
           listeKenarVar(g,1,3) ? "var" : "yok ✗");
    printf("deg(0)=%d, deg(1)=%d\n",
           listeDerece(g,0), listeDerece(g,1));

    // ── Ağırlıklı yönlü graf ──
    printf("\n── Ağırlıklı Yönlü Graf ──\n");
    ListeGraf* dg = listeGrafOlustur(4, true);
    listeKenarEkle(dg, 0, 1, 250);  // Ankara→İstanbul
    listeKenarEkle(dg, 0, 2, 450);  // Ankara→Eskişehir
    listeKenarEkle(dg, 2, 1, 335);  // Eskişehir→İstanbul
    listeKenarEkle(dg, 2, 3, 390);  // Eskişehir→Konya
    listeGrafYazdir(dg);

    return 0;
}

Graf: 4 düğüm, 5 kenar (yönsüz)
[0] → 3(1) 2(1) 1(1) ∅
[1] → 2(1) 0(1) ∅
[2] → 3(1) 1(1) 0(1) ∅
[3] → 2(1) 0(1) ∅

Kenar (0,2): var ✓
Kenar (1,3): yok ✗
deg(0)=3, deg(1)=2

── Ağırlıklı Yönlü Graf ──
Graf: 4 düğüm, 4 kenar (yönlü)
[0] → 2(450) 1(250) ∅          ← Ankara: Eskişehir(450km), İstanbul(250km)
[1] → ∅                         ← İstanbul: giden kenar yok (sink)
[2] → 3(390) 1(335) ∅          ← Eskişehir: Konya(390), İstanbul(335)
[3] → ∅                         ← Konya: giden kenar yok