Understanding Connected Components
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.
Approach
- Graph Representation: We will represent the graph using an adjacency list.
- DFS/BFS Traversal: We can use Depth First Search (DFS) or Breadth First Search (BFS) to explore the graph and find connected components.
- Visited Array: We need to keep track of visited nodes to avoid counting them multiple times.
Implementation Steps
- Read the number of vertices and edges.
- Construct the adjacency list.
- Initialize a visited array.
- Traverse each vertex. If it’s not visited, perform a DFS/BFS starting from that vertex and mark all reachable vertices.
- Count each time you start a new traversal as a new connected component.
C Code
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// Structure to represent a node in the adjacency list
struct Node {
int vertex;
struct Node* next;
};
// Graph structure
struct Graph {
int numVertices;
struct Node** adjLists;
};
// Function to create a graph
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct Node*));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
}
return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct Node* newNode = malloc(sizeof(struct Node));
newNode->vertex = dest;
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Since the graph is undirected, add an edge from dest to src
newNode = malloc(sizeof(struct Node));
newNode->vertex = src;
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// Depth First Search function
void DFS(struct Graph* graph, int vertex, int* visited) {
visited[vertex] = 1; // Mark the vertex as visited
printf("%d ", vertex);
struct Node* temp = graph->adjLists[vertex];
while (temp) {
int connectedVertex = temp->vertex;
if (!visited[connectedVertex]) {
DFS(graph, connectedVertex, visited);
}
temp = temp->next;
}
}
// Function to find and print connected components
void findConnectedComponents(struct Graph* graph) {
int* visited = malloc(graph->numVertices * sizeof(int));
for (int i = 0; i < graph->numVertices; i++) {
visited[i] = 0; // Initialize all vertices as not visited
}
printf("Connected components:\n");
for (int i = 0; i < graph->numVertices; i++) {
if (!visited[i]) {
printf("Component: ");
DFS(graph, i, visited);
printf("\n");
}
}
free(visited);
}
// Main function
int main() {
int vertices, edges, src, dest;
printf("Enter number of vertices: ");
scanf("%d", &vertices);
printf("Enter number of edges: ");
scanf("%d", &edges);
struct Graph* graph = createGraph(vertices);
printf("Enter edges (src dest): \n");
for (int i = 0; i < edges; i++) {
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
findConnectedComponents(graph);
// Free allocated memory
for (int i = 0; i < vertices; i++) {
struct Node* temp = graph->adjLists[i];
while (temp) {
struct Node* toFree = temp;
temp = temp->next;
free(toFree);
}
}
free(graph->adjLists);
free(graph);
return 0;
}
Explanation of the Code
- Graph Structure: We define a
Graphstructure that contains the number of vertices and an array of adjacency lists. - Creating the Graph: The
createGraphfunction initializes the graph. - Adding Edges: The
addEdgefunction adds edges in both directions since the graph is undirected. - DFS Implementation: The
DFSfunction traverses the graph and marks vertices as visited while printing them. - Finding Connected Components: The
findConnectedComponentsfunction loops through all vertices. If a vertex isn’t visited, it callsDFSto explore and print the component. - Memory Management: After processing, we free the allocated memory to avoid leaks.
Sample Input and Output
Assuming the input is as follows:
Enter number of vertices: 5
Enter number of edges: 4
Enter edges (src dest):
0 1
0 2
3 4
The output will be:
Connected components:
Component: 0 2 1
Component: 3 4
Conclusion
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!
