সি-তে গ্রাফ ইমপ্লিমেন্টেশন এবং অ্যালগরিদম ইন্টারমিডিয়েট সি কনসেপ্টস পার্ট ৫

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

    typedef struct {
        int numVertices;
        int** adjMatrix; // dynamically allocated 2D array এর Pointer
    } GraphMatrix;

    // adjacency matrix দ্বারা represented একটি graph তৈরি করার Function
    GraphMatrix* createGraphMatrix(int vertices) {
        GraphMatrix* graph = (GraphMatrix*)malloc(sizeof(GraphMatrix));
        if (!graph) return NULL;
        graph->numVertices = vertices;

        // row allocate করুন (pointer এর array)
        graph->adjMatrix = (int**)malloc(vertices * sizeof(int*));
        if (!graph->adjMatrix) { free(graph); return NULL; }

        // প্রতিটি row এর জন্য column allocate করুন এবং 0 তে initialize করুন
        for (int i = 0; i < vertices; i++) {
            graph->adjMatrix[i] = (int*)calloc(vertices, sizeof(int)); // calloc 0 তে initialize করে
            if (!graph->adjMatrix[i]) {
                // ব্যর্থ হলে allocated memory cleanup করুন
                while (--i >= 0) free(graph->adjMatrix[i]);
                free(graph->adjMatrix);
                free(graph);
                return NULL;
            }
        }
        return graph;
    }

    // একটি edge যোগ করার Function (undirected, unweighted)
    void addEdgeMatrix(GraphMatrix* graph, int src, int dest) {
        if (src >= 0 && src < graph->numVertices && dest >= 0 && dest < graph->numVertices) {
            graph->adjMatrix[src][dest] = 1;
            graph->adjMatrix[dest][src] = 1; // undirected graph এর জন্য
        } else {
            fprintf(stderr, "Invalid vertex index for edge (%d, %d)\n", src, dest);
        }
    }

     // graph memory free করার Function
    void freeGraphMatrix(GraphMatrix* graph) {
        if (!graph) return;
        for (int i = 0; i < graph->numVertices; i++) {
            free(graph->adjMatrix[i]); // column free করুন
        }
        free(graph->adjMatrix); // row free করুন
        free(graph); // graph structure free করুন
    }

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

    // adjacency list এর জন্য Node structure
    typedef struct AdjListNode {
        int dest;                // Destination vertex index
        // weighted graph এর জন্য, add: int weight;
        struct AdjListNode* next; // next adjacent vertex এর Pointer
    } AdjListNode;

    // graph itself represent করার Structure
    typedef struct {
        int numVertices;
        AdjListNode** adjLists; // AdjListNode এর pointer এর একটি array (list এর head)
        // প্রয়োজনে bool is_directed; add করুন
    } GraphList;

    // একটি নতুন adjacency list node তৈরি করার Function
    AdjListNode* newAdjListNode(int dest) {
        AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
         if (!newNode) { perror("Node alloc failed"); return NULL; }
        newNode->dest = dest;
        newNode->next = NULL;
        // weighted graph ব্যবহার করলে weight initialize করুন
        return newNode;
    }

    // V vertices সহ একটি graph তৈরি করার Function
    GraphList* createGraphList(int vertices) {
        GraphList* graph = (GraphList*)malloc(sizeof(GraphList));
        if (!graph) { perror("Graph alloc failed"); return NULL; }
        graph->numVertices = vertices;

        // adjacency list এর একটি array তৈরি করুন (pointer)
        graph->adjLists = (AdjListNode**)malloc(vertices * sizeof(AdjListNode*));
        if (!graph->adjLists) { perror("AdjList array alloc failed"); free(graph); return NULL; }


        // প্রতিটি adjacency list empty (NULL) হিসাবে initialize করুন
        for (int i = 0; i < vertices; ++i) {
            graph->adjLists[i] = NULL;
        }

        return graph;
    }

    // একটি undirected graph এ একটি edge যোগ করার Function
    void addEdgeList(GraphList* graph, int src, int dest) {
         if (src < 0 || src >= graph->numVertices || dest < 0 || dest >= graph->numVertices) {
             fprintf(stderr, "Invalid vertex index for edge (%d, %d)\n", src, dest);
             return;
         }
        // src থেকে dest পর্যন্ত একটি edge যোগ করুন। New node list এর front এ যোগ করা হয়।
        AdjListNode* newNodeDest = newAdjListNode(dest);
         if (!newNodeDest) return; // Allocation check
        newNodeDest->next = graph->adjLists[src]; // new node কে current head point করুন
        graph->adjLists[src] = newNodeDest;      // head update করুন

        // graph undirected হওয়ায়, dest থেকে src পর্যন্ত একটি edge ও যোগ করুন
        AdjListNode* newNodeSrc = newAdjListNode(src);
         if (!newNodeSrc) return; // Allocation check (tricky if first alloc succeeded!)
                                 // আরও robust error handling strategy বিবেচনা করুন
        newNodeSrc->next = graph->adjLists[dest];
        graph->adjLists[dest] = newNodeSrc;

        // directed graph এর জন্য, শুধুমাত্র প্রথম অংশ (src to dest) যোগ করুন
    }

    // graph memory free করার Function
    void freeGraphList(GraphList* graph) {
        if (!graph) return;
        for (int i = 0; i < graph->numVertices; ++i) {
            AdjListNode* current = graph->adjLists[i];
            AdjListNode* nextNode;
            while (current != NULL) {
                nextNode = current->next;
                free(current);
                current = nextNode;
            }
        }
        free(graph->adjLists); // pointer এর array free করুন
        free(graph);          // graph structure free করুন
    }

    // graph print করার Helper (debugging এর জন্য)
    void printGraphList(GraphList* graph) {
        printf("Graph Adjacency Lists:\n");
        for (int v = 0; v < graph->numVertices; ++v) {
            AdjListNode* temp = graph->adjLists[v];
            printf("Vertex %d: ", v);
            while (temp) {
                printf("-> %d ", temp->dest);
                temp = temp->next;
            }
            printf("-> NULL\n");
        }
    }

    #include <stdbool.h> // For bool type

    // Recursive DFS helper function
    void DFSUtil(GraphList* graph, int vertex, bool visited[]) {
        // current node কে visited mark করুন এবং এটিকে print করুন
        visited[vertex] = true;
        printf("%d ", vertex);

        // সমস্ত adjacent vertices এর জন্য Recur করুন
        AdjListNode* temp = graph->adjLists[vertex];
        while (temp != NULL) {
            int adjacentVertex = temp->dest;
            if (!visited[adjacentVertex]) {
                DFSUtil(graph, adjacentVertex, visited); // Recursive call
            }
            temp = temp->next;
        }
    }

    // Main DFS function - disconnected graph handle করে
    void DFS(GraphList* graph, int startVertex) {
        if (!graph || startVertex < 0 || startVertex >= graph->numVertices) {
             fprintf(stderr, "Invalid input for DFS\n");
             return;
         }
        printf("DFS starting from vertex %d: ", startVertex);

        // visited array allocate এবং initialize করুন
        bool* visited = (bool*)calloc(graph->numVertices, sizeof(bool)); // calloc false তে initialize করে
        if (!visited) { perror("Visited array alloc failed"); return; }


        // starting vertex এর জন্য recursive helper function call করুন
        DFSUtil(graph, startVertex, visited);

        // ঐচ্ছিক: graph disconnected হতে পারে, সমস্ত components visited হয় কিনা তা নিশ্চিত করতে
        // সমস্ত vertices এর উপর iterate করুন।
        // printf("\nChecking other components (if any):\n");
        // for (int i = 0; i < graph->numVertices; i++) {
        //     if (!visited[i]) {
        //         printf("Component starting at %d: ", i);
        //         DFSUtil(graph, i, visited);
        //         printf("\n");
        //     }
        // }

        printf("\n");
        free(visited); // visited array cleanup করুন
    }

    #include <stdbool.h>

    // --- BFS এর জন্য Minimal Queue Implementation (int vertex indices store করে) ---
    // Available থাকলে previous post থেকে আপনার actual Queue code দিয়ে replace করুন
    typedef struct IntQueueNode {
        int data;
        struct IntQueueNode* next;
    } IntQueueNode;

    typedef struct {
        IntQueueNode *front, *rear;
    } IntQueue;

    IntQueue* createIntQueue() { /* Implementation needed */ }
    void enqueueInt(IntQueue* q, int item) { /* Implementation needed */ }
    int dequeueInt(IntQueue* q) { /* Implementation needed - return -1 or error on empty */ }
    bool isIntQueueEmpty(IntQueue* q) { /* Implementation needed */ }
    void freeIntQueue(IntQueue* q) { /* Implementation needed */ }
    // --- End Minimal Queue ---

    // --- Placeholder Queue Implementation ---
    IntQueue* createIntQueue() {
        IntQueue* q = (IntQueue*)malloc(sizeof(IntQueue));
         if (!q) return NULL;
        q->front = q->rear = NULL;
        return q;
    }
     bool isIntQueueEmpty(IntQueue* q) {
        return q->front == NULL;
    }
     void enqueueInt(IntQueue* q, int item) {
        IntQueueNode* temp = (IntQueueNode*)malloc(sizeof(IntQueueNode));
        if (!temp) return;
        temp->data = item;
        temp->next = NULL;
        if (q->rear == NULL) { q->front = q->rear = temp; return; }
        q->rear->next = temp;
        q->rear = temp;
    }
     int dequeueInt(IntQueue* q) {
        if (isIntQueueEmpty(q)) return -1; // Error indicator
        IntQueueNode* temp = q->front;
        int item = temp->data;
        q->front = q->front->next;
        if (q->front == NULL) q->rear = NULL;
        free(temp);
        return item;
    }
    void freeIntQueue(IntQueue* q) {
        while (!isIntQueueEmpty(q)) { dequeueInt(q); }
        free(q);
    }
     // --- End Placeholder Queue Implementation ---


    // Main BFS function
    void BFS(GraphList* graph, int startVertex) {
         if (!graph || startVertex < 0 || startVertex >= graph->numVertices) {
             fprintf(stderr, "Invalid input for BFS\n");
             return;
         }
        printf("BFS starting from vertex %d: ", startVertex);

        // visited array allocate এবং initialize করুন
        bool* visited = (bool*)calloc(graph->numVertices, sizeof(bool));
        if (!visited) { perror("Visited array alloc failed"); return; }


        // BFS এর জন্য একটি queue তৈরি করুন
        IntQueue* queue = createIntQueue();
        if (!queue) { free(visited); perror("Queue creation failed"); return; }

        // start node কে visited mark করুন এবং এটিকে enqueue করুন
        visited[startVertex] = true;
        enqueueInt(queue, startVertex);

        while (!isIntQueueEmpty(queue)) {
            // একটি vertex dequeue করুন এবং এটিকে print করুন
            int currentVertex = dequeueInt(queue);
            if (currentVertex == -1) break; // logic correct হলে এটি হওয়া উচিত নয়
            printf("%d ", currentVertex);

            // dequeued vertex এর সমস্ত adjacent vertices পান
            AdjListNode* temp = graph->adjLists[currentVertex];
            while (temp != NULL) {
                int adjVertex = temp->dest;
                // একটি adjacent visited না হলে, এটিকে visited mark করুন এবং এটিকে enqueue করুন
                if (!visited[adjVertex]) {
                    visited[adjVertex] = true;
                    enqueueInt(queue, adjVertex);
                }
                temp = temp->next;
            }
        }

        printf("\n");
        freeIntQueue(queue); // queue cleanup করুন
        free(visited);      // visited array cleanup করুন

        // BFS inherently startVertex এর connected component explore করে।
        // disconnected graph explore করতে হলে, unvisited node থেকে শুরু করে BFS multiple time call করুন।
    }

// (graph structure, create/add/free function, DFS, BFS,
// এবং প্রয়োজনীয় Queue function উপরে অন্তর্ভুক্ত করুন)

int main() {
    int V = 6; // vertices এর সংখ্যা
    GraphList* graph = createGraphList(V);
    if (!graph) return 1;

    printf("Creating an undirected graph with %d vertices.\n", V);
    addEdgeList(graph, 0, 1);
    addEdgeList(graph, 0, 2);
    addEdgeList(graph, 1, 3);
    addEdgeList(graph, 1, 4);
    addEdgeList(graph, 2, 4);
    addEdgeList(graph, 3, 4);
    addEdgeList(graph, 3, 5);
    addEdgeList(graph, 4, 5);

    // adjacency list representation print করুন
    printGraphList(graph);
    printf("\n");

    // vertex 0 থেকে শুরু করে DFS perform করুন
    DFS(graph, 0);

    // vertex 0 থেকে শুরু করে BFS perform করুন
    BFS(graph, 0);

    // vertex 3 থেকে শুরু করে DFS perform করুন
    DFS(graph, 3);

    // vertex 3 থেকে শুরু করে BFS perform করুন
    BFS(graph, 3);


    printf("\nFreeing the graph...\n");
    freeGraphList(graph);
    graph = NULL;
    printf("Graph freed.\n");

    return 0;
}