{"id":607,"date":"2024-10-10T13:43:38","date_gmt":"2024-10-10T08:13:38","guid":{"rendered":"https:\/\/codexplained.in\/?p=607"},"modified":"2025-11-24T15:56:03","modified_gmt":"2025-11-24T10:26:03","slug":"find-connected-components-in-graph","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=607","title":{"rendered":"Find Connected Components in Graph"},"content":{"rendered":"\n

Understanding Connected Components<\/h3>\n\n\n\n

In graph theory, a connected component is a subset of vertices such that there is a path between any two vertices in this subset. In simpler terms, it means that you can travel between any two nodes in that subset without leaving it.<\/p>\n\n\n\n

Approach<\/h3>\n\n\n\n
    \n
  1. Graph Representation<\/strong>: We will represent the graph using an adjacency list.<\/li>\n\n\n\n
  2. DFS\/BFS Traversal<\/strong>: We can use Depth First Search (DFS) or Breadth First Search (BFS) to explore the graph and find connected components.<\/li>\n\n\n\n
  3. Visited Array<\/strong>: We need to keep track of visited nodes to avoid counting them multiple times.<\/li>\n<\/ol>\n\n\n\n

    Implementation Steps<\/h3>\n\n\n\n
      \n
    1. Read the number of vertices and edges.<\/li>\n\n\n\n
    2. Construct the adjacency list.<\/li>\n\n\n\n
    3. Initialize a visited array.<\/li>\n\n\n\n
    4. Traverse each vertex. If it’s not visited, perform a DFS\/BFS starting from that vertex and mark all reachable vertices.<\/li>\n\n\n\n
    5. Count each time you start a new traversal as a new connected component.<\/li>\n<\/ol>\n\n\n\n

      C Code<\/h3>\n\n\n
      \n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_VERTICES 100\n\n\/\/ Structure to represent a node in the adjacency list\nstruct Node {\n    int vertex;\n    struct Node* next;\n};\n\n\/\/ Graph structure\nstruct Graph {\n    int numVertices;\n    struct Node** adjLists;\n};\n\n\/\/ Function to create a graph\nstruct Graph* createGraph(int vertices) {\n    struct Graph* graph = malloc(sizeof(struct Graph));\n    graph->numVertices = vertices;\n    graph->adjLists = malloc(vertices * sizeof(struct Node*));\n\n    for (int i = 0; i < vertices; i++) {\n        graph->adjLists[i] = NULL;\n    }\n    return graph;\n}\n\n\/\/ Function to add an edge to the graph\nvoid addEdge(struct Graph* graph, int src, int dest) {\n    \/\/ Add edge from src to dest\n    struct Node* newNode = malloc(sizeof(struct Node));\n    newNode->vertex = dest;\n    newNode->next = graph->adjLists[src];\n    graph->adjLists[src] = newNode;\n\n    \/\/ Since the graph is undirected, add an edge from dest to src\n    newNode = malloc(sizeof(struct Node));\n    newNode->vertex = src;\n    newNode->next = graph->adjLists[dest];\n    graph->adjLists[dest] = newNode;\n}\n\n\/\/ Depth First Search function\nvoid DFS(struct Graph* graph, int vertex, int* visited) {\n    visited[vertex] = 1; \/\/ Mark the vertex as visited\n    printf("%d ", vertex);\n\n    struct Node* temp = graph->adjLists[vertex];\n    while (temp) {\n        int connectedVertex = temp->vertex;\n        if (!visited[connectedVertex]) {\n            DFS(graph, connectedVertex, visited);\n        }\n        temp = temp->next;\n    }\n}\n\n\/\/ Function to find and print connected components\nvoid findConnectedComponents(struct Graph* graph) {\n    int* visited = malloc(graph->numVertices * sizeof(int));\n    for (int i = 0; i < graph->numVertices; i++) {\n        visited[i] = 0; \/\/ Initialize all vertices as not visited\n    }\n\n    printf("Connected components:\\n");\n    for (int i = 0; i < graph->numVertices; i++) {\n        if (!visited[i]) {\n            printf("Component: ");\n            DFS(graph, i, visited);\n            printf("\\n");\n        }\n    }\n\n    free(visited);\n}\n\n\/\/ Main function\nint main() {\n    int vertices, edges, src, dest;\n\n    printf("Enter number of vertices: ");\n    scanf("%d", &vertices);\n    printf("Enter number of edges: ");\n    scanf("%d", &edges);\n\n    struct Graph* graph = createGraph(vertices);\n\n    printf("Enter edges (src dest): \\n");\n    for (int i = 0; i < edges; i++) {\n        scanf("%d %d", &src, &dest);\n        addEdge(graph, src, dest);\n    }\n\n    findConnectedComponents(graph);\n\n    \/\/ Free allocated memory\n    for (int i = 0; i < vertices; i++) {\n        struct Node* temp = graph->adjLists[i];\n        while (temp) {\n            struct Node* toFree = temp;\n            temp = temp->next;\n            free(toFree);\n        }\n    }\n    free(graph->adjLists);\n    free(graph);\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
      Explanation of the Code<\/h3>\n\n\n\n
        \n
      1. Graph Structure<\/strong>: We define a Graph<\/code> structure that contains the number of vertices and an array of adjacency lists.<\/li>\n\n\n\n
      2. Creating the Graph<\/strong>: The createGraph<\/code> function initializes the graph.<\/li>\n\n\n\n
      3. Adding Edges<\/strong>: The addEdge<\/code> function adds edges in both directions since the graph is undirected.<\/li>\n\n\n\n
      4. DFS Implementation<\/strong>: The DFS<\/code> function traverses the graph and marks vertices as visited while printing them.<\/li>\n\n\n\n
      5. Finding Connected Components<\/strong>: The findConnectedComponents<\/code> function loops through all vertices. If a vertex isn’t visited, it calls DFS<\/code> to explore and print the component.<\/li>\n\n\n\n
      6. Memory Management<\/strong>: After processing, we free the allocated memory to avoid leaks.<\/li>\n<\/ol>\n\n\n\n
        Sample Input and Output<\/h3>\n\n\n\n
        Assuming the input is as follows:<\/p>\n\n\n\n
        Enter number of vertices: 5
        Enter number of edges: 4
        Enter edges (src dest): 
        0 1
        0 2
        3 4
        <\/code><\/pre>\n\n\n\n
        The output will be:<\/p>\n\n\n\n
        Connected components:
        Component: 0 2 1 
        Component: 3 4 
        <\/code><\/pre>\n\n\n\n
        Conclusion<\/h3>\n\n\n\n
        This program successfully finds and displays connected components in a graph using depth-first search. It can be adapted to different graph sizes and structures by changing the input. If you have any questions or need further modifications, feel free to ask!<\/p>\n\n\n\n
        <\/p>\n