Graph

Kategori: C , 05 Temmuz 2019 , JanFranco


Graph veri yapısında her obje, her element birbiri ile bağlı olabilir. LinkedList veri yapısı gibi elemanlar birbirine sırayla bağlı değildir. Sırayla da bağlayabiliriz ancak Graph kullanımının nedeni istediğimiz elemanı istediğimiz elemana bağlayabilmemizdir. Aşağıdaki şekilde bir Graph düşünelim:
Bu şekli ortaya koyabilmek için kodlamaya başlayalım. Öncelikle elemanlar için bir struct oluşturalım:


struct adjListNode{
    int dest;
    struct adjListNode *next;
};
Elemanların birbirine bağlanacağı listeler için bir struct oluşturalım:

struct adjList{
    struct adjListNode *head;
};
Bu listelerin tutulacağı graph için bir struct oluşturalım. Buradaki v liste sayısıdır:

struct Graph{
    int v;
    struct adjList *array;
};
Grahp veri yapısını initialize eden bir fonksiyon yazalım. Fonksiyon parametre olarak kaç liste olacağını alır. İlk olarak bellekten struct Graph kadar yer ayırttık ve oluşturduğumuz struct'ın v değerini parametre olarak gönderilen v değerine eşitledik. array pointer'ının da malloc ile ayırttığımız yeri göstermesini sağladık. Ayırttığımız yer listenin kaplayacağı alan * liste sayısıdır. Daha sonra tüm arraylerin head'lerini NULL yaptık:

struct Graph *createGraph(int v){
    struct Graph *graph = malloc(sizeof(struct Graph));
    graph->v = v;
    graph->array = malloc(sizeof(struct adjList) * v);

    int i;
    for(i=0; i<v; i++){
        graph->array[i].head = NULL;
    }

    return graph;
}
Listelere eleman ekleyen bir fonksiyon yazalım. Burada dikkat edilmesi gereken nokta, yapılan işin çift yönlü olduğudur. Örneğin 0'dan 1'e bir çizgi çektiğimizde 0->1 şeklinde düşünebiliriz. Ancak bu işlem aynı zamanda 1->0 özelliğini de taşır. Bunun sebebi burada implemente ettiğimiz Graph veri yapısı undirect özelliği taşır. Yani yönsüzdür. Graph veri yapısının yönlü versiyonu da mevcuttur. İlk olarak eleman için yer ayırtalım ve elemanın dest değerini yani bağlanacağı değeri parametre olarak verilen dest değerine eşitleyelim. Elemanın next değerinin de array[src].head değerini göstermesini sağlayalım. Daha sonra bunun tam tersini yapalım. Böylece 0->1'i gösterirken 1->0 gösterimini de sağlamış oluruz:

void addEdge(struct Graph *graph, int src, int dest){
    struct adjListNode *newNode = malloc(sizeof(struct adjListNode));
    newNode->dest = dest;
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = malloc(sizeof(struct adjListNode));
    newNode->dest = src;
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}
Listeleri ekrana bastıracak bir fonksiyon yazalım:

void printGraph(struct Graph* graph){
    int v;
    for(v=0; v<graph->v; v++){
        struct adjListNode *pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while(pCrawl){
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}
Yazdığımız fonksiyonları kullanalım:

int main() {
    struct Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}
Kodların tamamı:

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

struct adjListNode{
    int dest;
    struct adjListNode *next;
};

struct adjList{
    struct adjListNode *head;
};

struct Graph{
    int v;
    struct adjList *array;
};

struct Graph *createGraph(int v){
    struct Graph *graph = malloc(sizeof(struct Graph));
    graph->v = v;
    graph->array = malloc(sizeof(struct adjList) * v);

    int i;
    for(i=0; i<v; i++){
        graph->array[i].head = NULL;
    }

    return graph;
}

void addEdge(struct Graph *graph, int src, int dest){
    struct adjListNode *newNode = malloc(sizeof(struct adjListNode));
    newNode->dest = dest;
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    newNode = malloc(sizeof(struct adjListNode));
    newNode->dest = src;
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

void printGraph(struct Graph* graph){
    int v;
    for(v=0; v<graph->v; v++){
        struct adjListNode *pCrawl = graph->array[v].head;
        printf("\n Adjacency list of vertex %d\n head ", v);
        while(pCrawl){
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

int main() {
    struct Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}
Output:

Adjacency list of vertex 0
head -> 4-> 1

Adjacency list of vertex 1
head -> 4-> 3-> 2-> 0

Adjacency list of vertex 2
head -> 3-> 1

Adjacency list of vertex 3
head -> 4-> 2-> 1

Adjacency list of vertex 4
head -> 3-> 1-> 0


Sonraki Yazı: Binary Tree
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın