Curs 7 - Grafuri, Arbori și Algoritmi de Sortare în C

Acest curs introduce structurile de date avansate Grafuri și Arbori, precum și algoritmi esențiali de sortare.

1. Grafuri

Un graf este o colecție de noduri (vârfuri) conectate prin muchii. Grafurile pot fi orientate sau neorientate.

a) Reprezentarea unui Graf cu Matrice de Adiacență

#include <stdio.h>
#define N 5

int graf[N][N] = {
    {0, 1, 1, 0, 0},
    {1, 0, 0, 1, 0},
    {1, 0, 0, 1, 1},
    {0, 1, 1, 0, 1},
    {0, 0, 1, 1, 0}
};

void afiseaza_graf() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", graf[i][j]);
        }
        printf("\n");
    }
}

int main() {
    afiseaza_graf();
    return 0;
}

b) Parcurgerea unui Graf cu BFS (Breadth-First Search)

#include <stdio.h>
#include <stdlib.h>
#define N 5

int graf[N][N] = {
    {0, 1, 1, 0, 0},
    {1, 0, 0, 1, 0},
    {1, 0, 0, 1, 1},
    {0, 1, 1, 0, 1},
    {0, 0, 1, 1, 0}
};

int vizitat[N] = {0};

void BFS(int start) {
    int coada[N], frunte = 0, spate = 0;
    coada[spate++] = start;
    vizitat[start] = 1;
    
    while (frunte < spate) {
        int nod = coada[frunte++];
        printf("%d ", nod);
        for (int i = 0; i < N; i++) {
            if (graf[nod][i] && !vizitat[i]) {
                coada[spate++] = i;
                vizitat[i] = 1;
            }
        }
    }
}

int main() {
    printf("Parcurgere BFS: ");
    BFS(0);
    return 0;
}

2. Arbori

Un arbore este o structură de date ierarhică în care fiecare nod are un părinte și poate avea mai mulți copii.

a) Definirea unui Arbore Binare și Inserarea Nodurilor

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

struct Nod {
    int valoare;
    struct Nod *stanga, *dreapta;
};

struct Nod* creare_nod(int valoare) {
    struct Nod *nod = (struct Nod*)malloc(sizeof(struct Nod));
    nod->valoare = valoare;
    nod->stanga = nod->dreapta = NULL;
    return nod;
}

void preordine(struct Nod* radacina) {
    if (radacina != NULL) {
        printf("%d ", radacina->valoare);
        preordine(radacina->stanga);
        preordine(radacina->dreapta);
    }
}

int main() {
    struct Nod* radacina = creare_nod(10);
    radacina->stanga = creare_nod(5);
    radacina->dreapta = creare_nod(15);
    
    printf("Parcurgere Preordine: ");
    preordine(radacina);
    return 0;
}

3. Algoritmi de Sortare

Sortarea este un proces esențial pentru organizarea datelor. Vom explora câțiva algoritmi de bază.

a) Bubble Sort

#include <stdio.h>

void bubbleSort(int v[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (v[j] > v[j + 1]) {
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
            }
        }
    }
}

int main() {
    int v[] = {5, 1, 4, 2, 8};
    int n = sizeof(v) / sizeof(v[0]);
    bubbleSort(v, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }
    return 0;
}

b) Quick Sort

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int v[], int low, int high) {
    int pivot = v[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (v[j] < pivot) {
            i++;
            swap(&v[i], &v[j]);
        }
    }
    swap(&v[i + 1], &v[high]);
    return i + 1;
}

void quickSort(int v[], int low, int high) {
    if (low < high) {
        int pi = partition(v, low, high);
        quickSort(v, low, pi - 1);
        quickSort(v, pi + 1, high);
    }
}

int main() {
    int v[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(v) / sizeof(v[0]);
    quickSort(v, 0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }
    return 0;
}

Resurse suplimentare:

• Grafuri - Tutorialspoint
• Sortări - GeeksForGeeks