example1.c

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

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

typedef struct Graph
{
    int vertices;
    int *visited;
    Node **adjacencyList;
} Graph;

typedef struct Stack
{
    int top;
    int capacity;
    int *array;
} Stack;

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

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

    return newNode;
}

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

    graph->vertices = vertices;

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

    for (int i = 0; i < vertices; i++)
    {
        graph->adjacencyList[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->adjacencyList[source];
    graph->adjacencyList[source] = newNode;

    newNode = createNode(source);

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

/* Creeaza stack */
Stack *createStack(int capacity)
{
    Stack *stack = malloc(sizeof(Stack));

    stack->capacity = capacity;
    stack->top = -1;
    stack->array = malloc(capacity * sizeof(int));

    return stack;
}

/* Push in stack */
void push(Stack *stack, int value)
{
    stack->top++;
    stack->array[stack->top] = value;
}

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

    printf("%d ", vertex);

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

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

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

        temp = temp->next;
    }
}

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

int main()
{
    int numberOfVertices;
    int numberOfEdges;

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

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

    Graph *graph = createGraph(numberOfVertices);

    printf("Introdu muchiile:\n");

    for (int i = 0; i < numberOfEdges; i++)
    {
        int source;
        int destination;

        scanf("%d %d", &source, &destination);

        addEdge(graph, source, destination);
    }

    printf("\nParcurgere DFS:\n");

    DFS(graph, 0);

    resetVisited(graph);

    return 0;
}