example2.c

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

/* Structura pentru nod */
typedef struct Node
{
    int data;
    struct Node *next;
} Node;

/* Structura pentru graf */
typedef struct Graph
{
    int vertices;
    int *visited;
    Node **adjacencyLists;
} Graph;

/* Creeaza nod */
Node *createNode(int value)
{
    Node *newNode = malloc(sizeof(Node));

    newNode->data = value;
    newNode->next = NULL;

    return newNode;
}

/* Creeaza graf */
Graph *createGraph(int vertices)
{
    Graph *graph = malloc(sizeof(Graph));

    graph->vertices = vertices;

    graph->adjacencyLists = malloc(vertices * sizeof(Node *));
    graph->visited = malloc(vertices * sizeof(int));

    for (int i = 0; i < vertices; i++)
    {
        graph->adjacencyLists[i] = NULL;
        graph->visited[i] = 0;
    }

    return graph;
}

/* Adauga muchie */
void addEdge(Graph *graph, int source, int destination)
{
    Node *newNode = createNode(destination);

    newNode->next = graph->adjacencyLists[source];
    graph->adjacencyLists[source] = newNode;

    newNode = createNode(source);

    newNode->next = graph->adjacencyLists[destination];
    graph->adjacencyLists[destination] = newNode;
}

/* Introdu muchii */
void insertEdges(Graph *graph, int numberOfEdges)
{
    int source;
    int destination;

    printf("Introdu muchiile:\n");

    for (int i = 0; i < numberOfEdges; i++)
    {
        scanf("%d %d", &source, &destination);

        addEdge(graph, source, destination);
    }
}

/* Verifica daca coada e goala */
int isEmpty(Node *queue)
{
    return queue == NULL;
}

/* Adauga in coada */
void enqueue(Node **queue, int value)
{
    Node *newNode = createNode(value);

    if (*queue == NULL)
    {
        *queue = newNode;
    }
    else
    {
        Node *temp = *queue;

        while (temp->next != NULL)
        {
            temp = temp->next;
        }

        temp->next = newNode;
    }
}

/* Scoate din coada */
int dequeue(Node **queue)
{
    Node *temp = *queue;

    int value = temp->data;

    *queue = (*queue)->next;

    free(temp);

    return value;
}

/* Reset visited */
void resetVisited(Graph *graph)
{
    for (int i = 0; i < graph->vertices; i++)
    {
        graph->visited[i] = 0;
    }
}

/* DFS */
void DFS(Graph *graph, int vertex)
{
    graph->visited[vertex] = 1;

    printf("%d ", vertex);

    Node *temp = graph->adjacencyLists[vertex];

    while (temp != NULL)
    {
        int connectedVertex = temp->data;

        if (graph->visited[connectedVertex] == 0)
        {
            DFS(graph, connectedVertex);
        }

        temp = temp->next;
    }
}

/* BFS */
void BFS(Graph *graph, int startVertex)
{
    Node *queue = NULL;

    graph->visited[startVertex] = 1;

    enqueue(&queue, startVertex);

    while (!isEmpty(queue))
    {
        int currentVertex = dequeue(&queue);

        printf("%d ", currentVertex);

        Node *temp = graph->adjacencyLists[currentVertex];

        while (temp != NULL)
        {
            int adjacentVertex = temp->data;

            if (graph->visited[adjacentVertex] == 0)
            {
                graph->visited[adjacentVertex] = 1;

                enqueue(&queue, adjacentVertex);
            }

            temp = temp->next;
        }
    }
}

int main()
{
    int numberOfVertices;
    int numberOfEdges;
    int startVertex;

    printf("Introdu numarul de noduri: ");
    scanf("%d", &numberOfVertices);

    printf("Introdu numarul de muchii: ");
    scanf("%d", &numberOfEdges);

    Graph *graph = createGraph(numberOfVertices);

    insertEdges(graph, numberOfEdges);

    printf("Start DFS: ");
    scanf("%d", &startVertex);

    printf("Parcurgere DFS:\n");

    DFS(graph, startVertex);

    resetVisited(graph);

    printf("\n");

    printf("Start BFS: ");
    scanf("%d", &startVertex);

    printf("Parcurgere BFS:\n");

    BFS(graph, startVertex);

    return 0;
}