C Graphs

C graphs

Created By: chatGPT

In C, graphs can be represented using various structures such as adjacency lists and adjacency matrices. An adjacency list is often more memory-efficient for sparse graphs, while an adjacency matrix can make certain operations faster for dense graphs.

# Include necessary libraries
#include <stdio.h>
#include <stdlib.h>

// Structure to represent a graph as an adjacency list
struct Graph {
    int V; // Number of vertices
    struct Node** array; // Pointer to an array of adjacency lists
};

// Structure to represent a node in the adjacency list
struct Node {
    int dest;
    struct Node* next;
};

// Function to create a new adjacency list node
struct Node* newNode(int dest) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->dest = dest;
    new_node->next = NULL;
    return new_node;
}

// Function to create a graph with V vertices
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->array = (struct Node**)malloc(V * sizeof(struct Node*));

    for (int i = 0; i < V; ++i) {
        graph->array[i] = NULL;
    }
    return graph;
}

You can also implement a Depth First Search (DFS) and a Breadth First Search (BFS) to traverse these graphs. The implementation of DFS will involve using recursive function calls, while BFS can be implemented using a queue.

// Function to perform DFS
void DFS(struct Graph* graph, int vertex, int* visited) {
    visited[vertex] = 1; // Mark the node as visited
    printf("Visited %d\n", vertex);

    struct Node* temp = graph->array[vertex];
    while (temp) {
        int connectedVertex = temp->dest;
        if (!visited[connectedVertex]) {
            DFS(graph, connectedVertex, visited);
        }
        temp = temp->next;
    }
}

// Function to perform BFS
void BFS(struct Graph* graph, int startVertex) {
    int visited[graph->V];
    for (int i = 0; i < graph->V; i++)
        visited[i] = 0; // Initialize all vertices as not visited

    struct Queue* queue = createQueue(); // Assuming Queue is implemented

    visited[startVertex] = 1;
    enqueue(queue, startVertex);

    while (!isEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("Visited %d\n", currentVertex);

        struct Node* temp = graph->array[currentVertex];
        while (temp) {
            int connectedVertex = temp->dest;
            if (!visited[connectedVertex]) {
                visited[connectedVertex] = 1;
                enqueue(queue, connectedVertex);
            }
            temp = temp->next;
        }
    }
}

When working with graphs, it’s crucial to remember to free the memory allocated for the nodes after usage to prevent memory leaks. Implementing a traversal algorithm effectively is the key to many applications, such as shortest path finding, cycle detection, and more.

// Function to free the Graph memory
void freeGraph(struct Graph* graph) {
    for (int i = 0; i < graph->V; i++) {
        struct Node* temp = graph->array[i];
        while (temp) {
            struct Node* toFree = temp;
            temp = temp->next;
            free(toFree);
        }
    }
    free(graph->array);
    free(graph);
}