C Programming data structures Graph Representations Adjacency Matrix List Step by step Implementation and Top 10 Questions and Answers
 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION.    Last Update: April 01, 2025      30 mins read      Difficulty-Level: beginner

C Programming: Data Structures - Graph Representations: Adjacency Matrix vs Adjacency List

Graphs are one of the most fundamental data structures used in computer science to model a wide range of applications. These applications include network routing, social networks, transportation logistics, and more. A graph can be thought of as a collection of points (vertices or nodes) connected by lines (edges). Efficiently representing and manipulating graphs is crucial for solving these problems optimally.

In C programming, there are two primary ways to represent a graph:

  1. Adjacency Matrix
  2. Adjacency List

Both have their own benefits and drawbacks depending on the specific requirements of the program. Understanding their differences will help you choose the right representation for your needs.

1. Adjacency Matrix

Definition: An adjacency matrix is a two-dimensional array where the rows and columns represent the vertices of the graph. The value at matrix[i][j] indicates whether there is an edge between vertex i and vertex j.

Structure: If a graph has V vertices, then the adjacency matrix is a V x V matrix. For undirected graphs, if there's an edge between vertices i and j, then matrix[i][j] = matrix[j][i] = 1 (or some other non-zero value indicating weight, if it’s a weighted graph). In directed graphs, matrix[i][j] = 1 indicates a directed edge from vertex i to vertex j.

Example Representation: Consider an undirected graph with 4 vertices (V1, V2, V3, V4) and edges between (V1, V2), (V2, V3), (V3, V4), and (V4, V1). Its adjacency matrix would look like:

    V1  V2  V3  V4
V1 |  0   1   0   1 |
V2 |  1   0   1   0 |
V3 |  0   1   0   1 |
V4 |  1   0   1   0 |

Advantages:

  • Simplicity: Adjacency matrices are straightforward to implement and use, making them intuitive and easy to understand.
  • Fast Edge Checking and Insertion/Deletion: It is very simple to check if an edge exists between any two vertices (matrix[i][j]). The time complexity for checking, adding, or removing an edge is O(1).
  • Edge Weight Retrieval: If the graph is weighted, the weights can be stored in the matrix directly, and retrieving the weight of an edge is also O(1).

Disadvantages:

  • High Memory Usage: An adjacency matrix consumes O(V²) memory, which can be highly inefficient for sparse graphs (graphs with a small number of edges compared to the potential maximum, i.e., V * (V - 1)).
  • Fixed Number of Vertices: The size of an adjacency matrix is fixed at the time of creation. Adding or removing vertices requires creating a new matrix, which is computationally expensive.
  • Inefficient Traversal: Traversing all adjacent vertices to a given vertex takes O(V) time in the worst case, even if only a few vertices are connected to it.

Implementation in C - Adjacency Matrix

#include <stdio.h>
#include <stdbool.h>

#define V 4     // Number of vertices in the graph

// Function to add edges to the graph
void add_edge(bool matrix[V][V], int u, int v, bool directed) {
    matrix[u][v] = true;
    if (!directed)
        matrix[v][u] = true;
}

// Function to print the adjacency matrix
void print_matrix(bool matrix[V][V]) {
    printf("Adjacency Matrix:\n");
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++)
            printf("%d ", matrix[i][j]);
        printf("\n");
    }
}

int main() {
    bool matrix[V][V] = {0};  // Initialize the matrix with zeros
    
    // Adding edges
    add_edge(matrix, 0, 1, false);  // Edge between V1 and V2
    add_edge(matrix, 1, 2, false);  // Edge between V2 and V3
    add_edge(matrix, 2, 3, false);  // Edge between V3 and V4
    add_edge(matrix, 3, 0, false);  // Edge between V4 and V1
    
    // Print adjacency matrix
    print_matrix(matrix);
    
    return 0;
}

2. Adjacency List

Definition: An adjacency list represents a graph as a collection of lists, where each list contains the adjacent vertices of a particular vertex.

Structure: For each vertex, maintain a linked list (can also use arrays or dynamic arrays) of vertices that are connected to it by an edge. If the graph is weighted, store pairs of adjacent vertices and corresponding weights.

Example Representation: Using the same undirected graph example. The adjacency list representation might look like:

Vertex 0: 1 3
Vertex 1: 0 2
Vertex 2: 1 3
Vertex 3: 2 0

Here, Vertex 0 has edges to Vertex 1 and Vertex 3, and so on.

Advantages:

  • Memory Efficiency: An adjacency list requires O(V + E) space, where V is the number of vertices and E is the number of edges. This is much more efficient for sparse graphs.
  • Dynamic Graph Manipulation: Vertices can be dynamically added or removed without affecting the performance significantly.
  • Efficient Traversal: Iterating over all edges for each vertex is faster, taking O(degree) time, where degree is the number of edges from that vertex.

Drawbacks:

  • Slower Edge Checking: Checking for the existence of an edge between two vertices can take O(degree_i) time, where degree_i is the degree of vertex i.
  • Complexity in Implementation: Implementing an adjacency list involves managing multiple linked lists or arrays, which can increase complexity.
  • Extra Space for Pointers/Index: For linked list implementations, additional space is required for pointers/indexes to connect each vertex's list.

Implementation in C - Adjacency List

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

// Number of vertices in the graph
#define V 4

// Node structure
typedef struct node {
    int dest;
    int weight;     // If the graph is weighted, this field holds the weight
    struct node* next;
} Node;

// Graph structure
typedef struct graph {
    Node* adjListArray[V];
} Graph;

// Function to create a newNode with given destination and weight
Node* create_node(int dest, int weight) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// Function to initialize graph with V vertices
Graph* init_graph(void) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    // Setting the head pointer of each adjacency list to NULL
    for (int i = 0; i < V; i++)
        graph->adjListArray[i] = NULL;
    return graph;
}

// Function to add edges to the graph
void add_edge(Graph* graph, int src, int dest, int weight, bool directed) {
    Node* newNode = create_node(dest, weight);
    newNode->next = graph->adjListArray[src];
    graph->adjListArray[src] = newNode;
    if (!directed) {
        newNode = create_node(src, weight);
        newNode->next = graph->adjListArray[dest];
        graph->adjListArray[dest] = newNode;
    }
}

// Function to print the adjacency list of the graph
void print_graph(Graph* graph) {
    for(int i = 0; i < V; i++) {
        printf("Adjacency list of vertex %d\n", i);
        Node* currentNode = graph->adjListArray[i];
        while(currentNode != NULL) {
            printf("Node: %d Weight: %d ->\t", currentNode->dest, currentNode->weight);
            currentNode = currentNode->next;
        }
        printf("NULL\n");   // Indicating end of list
    }
}

int main() {
    Graph* graph = init_graph();
    
    // Adding edges
    add_edge(graph, 0, 1, 1, false);  // Edge between V1 and V2 with weight 1
    add_edge(graph, 1, 2, 1, false);
    add_edge(graph, 2, 3, 1, false);
    add_edge(graph, 3, 0, 1, false);
    
    // Print adjacency list
    print_graph(graph);
    
    return 0;
}

Summary and Choosing a Representation

When deciding between an adjacency matrix and an adjacency list, consider the following:

  • Sparse vs Dense: If the graph is dense (with a large number of edges relative to vertices), an adjacency matrix is suitable due to its fast edge operations. For sparse graphs, use an adjacency list to save memory.
  • Number of Operations: If the graph requires frequent traversal of all neighbors, an adjacency list is better. However, if checks for edge existence are common, an adjacency matrix might be preferable.
  • Graph Modifiability: When the graph is likely to change frequently (vertices and edges), especially being sparse, an adjacency list offers better adaptability. For fixed-size dense graphs, an adjacency matrix may be simpler and more appropriate.

In conclusion, both representations have their place depending on the characteristics of the graph data, and understanding these differences helps in writing more efficient and effective code.

C Programming: Data Structures - Graph Representations: Adjacency Matrix vs Adjacency List

A Comprehensive Guide for Beginners

Understanding Graphs & Data Structure Representation

In computer science, a graph is a collection of nodes (also called vertices) and edges that represent relationships between pairs of nodes. Graphs are used to model network problems such as finding shortest paths for routing packets through a network or representing connections in social networks.

Graphs can be represented in different ways using data structures:

  1. Adjacency Matrix: This is a 2D array of VxV vertices where the entry at the i-th row and j-th column indicates whether there is an edge from vertex i to vertex j.
  2. Adjacency List: This uses an array of lists; each list is associated with a vertex and stores all its adjacent vertices.

Step-by-Step Guide to Implementing These Representations

To demonstrate this, let’s assume we are building a simple social network application where users (nodes) can have friendships (edges).

Frontend: User Interface For now, let's focus on a very basic console-based interface. We'll display options for adding/removing nodes/edges and displaying the graph.

#include <stdio.h>

// Function declaration
void addNode(int ***graphPtr, int *numNodes);
void addEdge(int **graph, int numNodes);
void removeNode(int ***graphPtr, int *numNodes);
void removeEdge(int **graph, int numNodes);
void printGraph(int **graph, int numNodes);

int main() {
    int numNodes = 0;
    int **graph = NULL;

    char choice;

    printf("Welcome to Social Network Graph Representation\n");
    
    while (1) {
        printf("\nChoose an option:\n");
        printf("1. Add Node (Adjacency List)\n");
        printf("2. Add Edge\n");
        printf("3. Remove Node\n");
        printf("4. Remove Edge\n");
        printf("5. Print Graph\n");
        printf("6. Exit\n");
        scanf(" %c", &choice);

        switch (choice) {
            case '1':
                addNode(&graph, &numNodes);
                break;
            case '2':
                addEdge(graph, numNodes);
                break;
            case '3':
                removeNode(&graph, &numNodes);
                break;
            case '4':
                removeEdge(graph, numNodes);
                break;
            case '5':
                printGraph(graph, numNodes);
                break;
            case '6':
                // Free allocated memory and exit
                printf("Exiting...\n");
                for (int i = 0; i < numNodes; i++) {
                    free(graph[i]);
                }
                free(graph);
                return 0;
            default:
                printf("Invalid choice. Please try again.\n");
                break;
        }
    }

    return 0;
}

Backend: Core Functionality Implementation

The core functionality of our application involves adding/removing nodes and edges using both adjacency matrix and adjacency list representation. However, in this example, I'll primarily focus on the adjacency list because adding and removing nodes is straightforward in an adjacency list representation compared to an adjacency matrix.

Adjacency List Representation

First, let's implement the adjacency list representation for our social network.

Adding Nodes Whenever we add a node, we should allocate more space for a new node in the array of pointers.

void addNode(int ***graphPtr, int *numNodes) {
    (*numNodes)++;
    *graphPtr = (int **)realloc(*graphPtr, (*numNodes) * sizeof(int *));
    (*graphPtr)[*numNodes-1] = NULL; // Initialize newly added node's list as NULL
    printf("Node added successfully. Total nodes: %d\n", *numNodes);
}

Adding Edges We'll add an edge between two nodes by inserting one node at the head of another node's adjacency list and vice versa for undirected graphs.

struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

struct AdjList {
    struct AdjListNode *head;
};

struct Graph {
    int V;
    struct AdjList* array;
};

struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode =
            (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

void createGraph(int V) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
 
    // Create an array of adjacency lists.  Size of array will be V
    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
 
     // Initialize each adjacency list as empty by making head as NULL
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;
 
    // Let's assume graph is passed back through a global variable or function argument 
    // and other manipulations are also done based on this.
}

void addEdge(struct Graph* graph, int src, int dest) {
    // Add an edge from src to dest.  A new node is added to the adjacency list of src.
    // The node is added at the beginning
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
 
    // Since graph is undirected, add an edge from dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

void removeNode(int ***graphPtr, int *numNodes) {
    if (*numNodes == 0) {
        printf("Graph is already empty.\n");
        return;
    }
    
    // Assume we always want to remove the last node
    --(*numNodes);
    for (struct AdjListNode *temp = (*graphPtr)[*numNodes]->head; temp != NULL; temp = temp->next) { 
        int v = temp->dest; 
        struct AdjListNode *prev = NULL;
        for (struct AdjListNode *current = (*graphPtr)[v]->head; current != NULL; current = current->next) { 
            if (current->dest == *numNodes+1) { 
                if (prev == NULL) (*graphPtr)[v]->head = current->next; 
                else prev->next = current->next; 
                free(current); 
                break; 
            } 
            prev = current; 
        } 
    }
    free((*graphPtr)[*numNodes]); // Free the node being removed
    (*graphPtr)[*numNodes] = NULL;

    printf("Node removed successfully. Total nodes: %d\n", *numNodes);
}

void removeEdge(struct Graph* graph, int src, int dest) {
    // Remove an edge from src to dest. 
    struct AdjListNode *prev = NULL;
    struct AdjListNode *current = graph->array[src].head; 
    while (current != NULL && current->dest != dest) { 
        prev = current; 
        current = current->next; 
    } 
    if (current == NULL) {
        printf("No such edge exists.\n");
        return;
    }
    if (prev == NULL) graph->array[src].head = current->next; 
    else prev->next = current->next; 
    free(current); 
 
    // Now do the opposite for dest -> src to make it undirected.
    prev = NULL;
    current = graph->array[dest].head; 
    while (current != NULL && current->dest != src) { 
        prev = current; 
        current = current->next; 
    } 
    if (prev == NULL) graph->array[dest].head = current->next; 
    else prev->next = current->next; 
    free(current); 

    printf("Edge removed successfully.\n");
}

void printGraph(struct Graph* graph) {
    printf("\nAdjacency List Representation of Graph:\n"); 
    int v;
    for (v = 0; v < graph->V; ++v) {
        printf("Adjacency list of vertex %d\n head ", v); 
        struct AdjListNode* pCrawl = graph->array[v].head; 
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

Adjacency Matrix Representation

Now, we'll implement a simple graph representation using the adjacency matrix. The functions for adding/removing nodes/edges will slightly differ.

Creating Graph and Adding Nodes Since we're using a 2D matrix, whenever we add a node, we need a new row and a new column. We'll use dynamic memory allocation for the same.

#include <stdlib.h>

void createGraphMatrix(int ***matPtr, int V) {
    int **mat = malloc(sizeof(int *) * V);
    for (int i=0;i<V;i++)
        mat[i]=malloc(sizeof(int) * V);
        
    // Initialize all values to zero indicating no edges initially
    for (int i=0;i<V;i++) 
        for (int j=0;j<V;j++) 
            mat[i][j] = 0;
            
    *matPtr = mat;
}

void addEdgeMatrix(int **mat, int V) {
    int src, dest;
    
    printf("Enter source and destination:\n");
    scanf("%d%d", &src, &dest);

    if (src>=1 && src<=V && dest>=1 && dest<=V){
        mat[src-1][dest-1] = 1;
        if (!isDirectedGraph(mat, V)) // If not directed then symmetrical edge
            mat[dest-1][src-1] = 1;
        printf("Edge added between vertices %d and %d.\n", src, dest);
    }
    else
        printf("Invalid input! Choose vertices between 1 and %d.\n", V);
}

void removeEdgeMatrix(int **mat, int V) {
    int src, dest;
    
    printf("Enter source and destination:\n");
    scanf("%d%d", &src, &dest);

    if (src>=1 && src<=V && dest>=1 && dest<=V){
        mat[src-1][dest-1] = 0;
        if (!isDirectedGraph(mat, V)) // If not directed then symmetrical edge removal
            mat[dest-1][src-1] = 0;
        printf("Edge removed between vertices %d and %d.\n", src, dest);
    }
    else
        printf("Invalid input! Choose vertices between 1 and %d.\n", V);
}

void addNodeMatrix(int ***matPtr, int *V) {
    ++(*V);
    *matPtr = realloc(*matPtr, *V * sizeof(int *));
    
    // Allocate new column for each previous row
    for (int i=0;i<*V-1;i++)
        (*matPtr)[i] = realloc((*matPtr)[i], *V * sizeof(int));
    
    // Create new row
    (*matPtr)[*V-1] = malloc(sizeof(int) * *V); 
    
    // Initialize the last row and last column as zero
    for (int i=0;i<*V;i++){
        (*matPtr)[*V-1][i] = 0;
        (*matPtr)[i][*V-1] = 0;
    }
}

void removeNodeMatrix(int ***matPtr, int *V) {
    if (*V == 0) {
        printf("Graph is already empty.\n");
        return;
    }
    
    // Assume we always want to remove the last node
    
    // Deallocate last row & shift all rows above it one location down
    free((*matPtr)[*V-1]);
    for (int i=*V-2; i>=0; i--) {
        for (int j=0; j<*V-1; j++)
            (*matPtr)[i+1][j] = (*matPtr)[i][j];
        (*matPtr)[i+1] = realloc((*matPtr)[i+1], (*V-1) * sizeof(int));
        free((*matPtr)[i]);
    }
   
   // Resize total graph matrix 
    *matPtr = realloc(*matPtr, (*V-1) * sizeof(int *));
    --(*V);
    
    // Shift columns to the left and then deallocate the last column
    
    printf("Node removed successfully. Total nodes: %d\n", *V);
}

int isDirectedGraph(int **mat, int V) {
    // Here you can add logic to check if graph is directed
    // For example, we can take it as input or just assume a graph is undirected.
    return 0;
}

void printGraphMatrix(int **mat, int V) {
    printf("\nAdjacency Matrix Representation of Graph:\n");
    for (int i=0;i<V;i++) {
        for (int j=0;j<V;j++)
            printf("%d ", mat[i][j]);
        printf("\n");
    }
}

Data Flow: Connecting Frontend with Backend

Let's connect our frontend with backend now:

In main function, we can extend to accommodate adjacency matrix representations.

int main() {
    int numNodes = 0;
    int **graph = NULL;
 
    int V = 5;
    createGraphMatrix(&graph, V);
    numNodes = V;

    char choice;

    printf("Welcome to Social Network Graph Representation\n");
    while (1) {
        printf("\nChoose an option:\n");
        printf("1. Add Node (Adjacency Matrix)\n");
        printf("2. Add Edge\n");
        printf("3. Remove Node\n");
        printf("4. Remove Edge\n");
        printf("5. Print Graph\n");
        printf("6. Create Custom Size Graph\n");
        printf("7. Exit\n");
        scanf(" %c", &choice);

        switch (choice) {
            case '1':
                addNodeMatrix(&graph, &numNodes);
                break;

            case '2':
                addEdgeMatrix(graph, numNodes);
                break;

            case '3':
                removeNodeMatrix(&graph, &numNodes);
                break;

            case '4':
                removeEdgeMatrix(graph, numNodes);
                break;

            case '5':
                printGraphMatrix(graph, numNodes);
                break;

            case '6':
                printf("Enter the number of vertices for new custom-size graph:");
                scanf("%d", &V);
                numNodes = V;
                createGraphMatrix(&graph, V);
                break;

            case '7':
                // Free allocated memory and exit
                printf("Exiting...\n");
                for (int i = 0; i < numNodes; i++) free(graph[i]);
                free(graph);
                return 0;

            default:
                printf("Invalid choice. Please try again.\n");
                break;
        }
    }

    return 0;
}

Running the Application: Step by Step Instructions

  1. Compile the Application: Start by saving the code into a file social_network.c. You can compile this c file using any c compiler like gcc.
gcc social_network.c -o social_network
  1. Run the Application: Now, run the compiled program by typing ./social_network in your terminal.
./social_network
  1. Use the Application: You'll be greeted with a menu for options. To add a node, type '1'. To create an edge between two nodes, type '2' and follow instructions. To delete a node/edge, types '3'/'4' respectively. Use '5' to print the current graph and '7' to exit.

Notes:

  • Dynamic Memory Allocation: In real-world applications, remember to handle dynamically allocated memories properly with checks for NULL. In our program, memory allocation failures aren't handled.
  • Error Checking: Always validate user inputs and provide appropriate feedback.
  • Custom Graph Creation: Our current program assumes a custom graph creation initially. For simplicity, it allows creating graph with initial fixed size (5 nodes). Later, you can extend the program to support custom-size graph creation anytime during the program.
  • Scalability: While adjacency matrix is good for dense graphs, adjacency lists perform better for sparse graphs (where less than V^2/2 edges exist; V is number of vertices).

This guide serves as a basic introduction to understanding and implementing graph data structures in C programming using both adjacency matrix and adjacency list representations. Feel free to extend and modify the provided code to experiment further!

Top 10 Questions and Answers on C Programming: Graph Representations (Adjacency Matrix and Adjacency List)

Understanding graph representations in C programming is fundamental for many algorithms in computer science, such as searching, sorting, and pathfinding. Two common ways to represent graphs are through adjacency matrices and adjacency lists. Here, we delve into the specifics of each representation method with some practical C programming examples.

1. What is a Graph in C Programming?

Answer: A graph is a collection of vertices (nodes) and edges connecting these vertices. In C Programming, graphs can be represented using various data structures, with two prominent ones being the adjacency matrix and adjacency list.

2. What is an Adjacency Matrix?

Answer: An adjacency matrix is a 2D array of size V x V where V is the number of vertices in the graph. Each cell at row i and column j is 1 if there exists an edge from vertex i to vertex j, otherwise 0. For weighted graphs, instead of 1, we can store the weight of the edge.

Example (Undirected Graph):

#include <stdio.h>

#define V 4 

void printGraph(int adj[V][V], int V) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", adj[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V] = { { 0, 1, 0, 1 },
                        { 1, 0, 1, 0 },
                        { 0, 1, 0, 1 },
                        { 1, 0, 1, 0 } };
    printGraph(graph, V);
    return 0;
}

In this example, an undirected graph with four vertices has edges between 0-1, 1-2, 2-3, and 3-0. The adjacency matrix clearly represents these connections.

3. What are the advantages and disadvantages of an adjacency matrix?

Answer:

Advantages:

  • Simplicity: The data structure is simple, making it easy to implement.
  • Constant time operations: Searching for an edge and adding/removing an edge takes constant time O(1).

Disadvantages:

  • Space Complexity: For graphs with a large number of nodes but sparse edges, adjacency matrices consume a lot of memory.
  • Inefficient for sparse graphs: Most of the cells are 0 for sparse graphs, leading to wastage of space.

4. What is an Adjacency List?

Answer: An adjacency list represents a graph as a set of vertices with adjacent nodes as linked lists. The ith node in the adjacency list represents the list of adjacent vertices for the ith vertex.

Example (Undirected Graph):

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

struct Node {
    int vertex;
    struct Node* next;
};

struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addEdge(struct Node* adjList[], int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;

    newNode = createNode(src);
    newNode->next = adjList[dest];
    adjList[dest] = newNode;
}

void printGraph(struct Node* adjList[], int vertices) {
    for (int v = 0; v < vertices; ++v) {
        struct Node* temp = adjList[v];
        printf("Vertex %d: ", v);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int vertices = 4;
    struct Node* adjList[vertices];

    for (int i = 0; i < vertices; i++)
        adjList[i] = NULL;

    addEdge(adjList, 0, 1);
    addEdge(adjList, 0, 3);
    addEdge(adjList, 1, 2);
    addEdge(adjList, 2, 3);

    printGraph(adjList, vertices);
    return 0;
}

This example illustrates an undirected graph with four vertices and edges between 0-1, 0-3, 1-2, and 2-3. The adjacency list efficiently captures the connections without using significant space for all non-existent edges.

5. What are the advantages and disadvantages of an adjacency list?

Answer:

Advantages:

  • Space Efficiency: Only requires space proportional to the number of vertices and edges, making it efficient for sparse graphs.
  • Dynamic memory allocation: Easier to manage and modify the graph during runtime.

Disadvantages:

  • Slower search time: Searching for an edge takes O(V) in the worst case.
  • Implementation Complexity: Slightly more complex to implement compared to an adjacency matrix.

6. How do you decide which graph representation to use in C Programming?

Answer: Choosing between an adjacency matrix and adjacency list depends on the specific requirements of your application:

  • Use an adjacency matrix if the graph is dense (many edges), or if you need frequent edge queries. Fast insertions and deletions are also preferable when a dense graph is expected.
  • Use an adjacency list if the graph is sparse (few edges) and if you need to frequently add or remove edges. Access to neighbors of a vertex is also faster when using adjacency lists.

7. How do you traverse a graph using Depth-First Search (DFS) with both representations in C Programming?

Answer: Depth-First Search (DFS) can be implemented using both adjacency matrices and adjacency lists. The implementation with adjacency lists is generally more space-efficient and faster for sparse graphs.

Using Adjacency Matrix:

#include <stdio.h>
#include <stdbool.h>

#define V 4

void DFS(int adj[V][V], int vertex, bool visited[]) {
    printf("%d ", vertex);
    visited[vertex] = true;
    
    for (int i = 0; i < V; ++i) {
        if (adj[vertex][i] == 1 && !visited[i])
            DFS(adj, i, visited);
    }
}

void traverseGraph(int adj[V][V], int start) {
    bool visited[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    DFS(adj, start, visited);
}

int main() {
    int graph[V][V] = { { 0, 1, 0, 1 },
                        { 1, 0, 1, 0 },
                        { 0, 1, 0, 1 },
                        { 1, 0, 1, 0 } };
    printf("DFS starting from vertex 0:\n");
    traverseGraph(graph, 0);
    
    return 0;
}

Using Adjacency List:

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

struct Node {
    int vertex;
    struct Node* next;
};

struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addEdge(struct Node* adjList[], int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;
}

void DFS(struct Node* adjList[], int vertex, bool visited[]) {
    printf("%d ", vertex);
    visited[vertex] = true;
    
    struct Node* temp = adjList[vertex];
    while (temp) {
        int connectedVertex = temp->vertex;
        if (!visited[connectedVertex]) {
            DFS(adjList, connectedVertex, visited);
        }
        temp = temp->next;
    }
}

void traverseGraph(struct Node* adjList[], int vertices, int start) {
    bool visited[vertices];
    for (int i = 0; i < vertices; i++)
        visited[i] = false;

    DFS(adjList, start, visited);
}

int main() {
    int vertices = 4;
    struct Node* adjList[vertices];

    for (int i = 0; i < vertices; i++)
        adjList[i] = NULL;

    addEdge(adjList, 0, 1);
    addEdge(adjList, 0, 3);
    addEdge(adjList, 1, 2);
    addEdge(adjList, 2, 3);

    printf("DFS starting from vertex 0:\n");
    traverseGraph(adjList, vertices, 0);

    return 0;
}

Both examples perform the same DFS traversal starting from vertex 0, illustrating the flexibility and effectiveness of both graph representations.

8. How do you traverse a graph using Breadth-First Search (BFS) with both representations in C Programming?

Answer: Breadth-First Search (BFS) can also be implemented using both adjacency matrices and adjacency lists.

Using Adjacency Matrix:

#include <stdio.h>
#include <stdbool.h>

#define V 4

void BFS(int adj[V][V], int start) {
    int queue[V];
    bool visited[V];
    int front = 0;
    int rear = 0;

    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    visited[start] = true;
    queue[rear++] = start;

    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

        for (int i = 0; i < V; i++) {
            if (adj[current][i] == 1 && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;
            }
        }
    }
}

int main() {
    int graph[V][V] = { { 0, 1, 0, 1 },
                        { 1, 0, 1, 0 },
                        { 0, 1, 0, 1 },
                        { 1, 0, 1, 0 } };
    printf("BFS starting from vertex 0:\n");
    BFS(graph, 0);
    return 0;
}

Using Adjacency List:

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

struct Node {
    int vertex;
    struct Node* next;
};

struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addEdge(struct Node* adjList[], int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;
}

void BFS(struct Node* adjList[], int start, int vertices) {
    int queue[vertices];
    bool visited[vertices];
    int front = 0;
    int rear = 0;

    for (int i = 0; i < vertices; i++) {
        visited[i] = false;
    }

    visited[start] = true;
    queue[rear++] = start;

    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

        struct Node* temp = adjList[current];
        while (temp != NULL) {
            int adjacentVertex = temp->vertex;
            if (!visited[adjacentVertex]) {
                visited[adjacentVertex] = true;
                queue[rear++] = adjacentVertex;
            }
            temp = temp->next;
        }
    }
}

int main() {
    int vertices = 4;
    struct Node* adjList[vertices];

    for (int i = 0; i < vertices; i++)
        adjList[i] = NULL;

    addEdge(adjList, 0, 1);
    addEdge(adjList, 0, 3);
    addEdge(adjList, 1, 2);
    addEdge(adjList, 2, 3);

    printf("BFS starting from vertex 0:\n");
    BFS(adjList, 0, vertices);

    return 0;
}

Both examples perform the same BFS traversal starting from vertex 0, again demonstrating the versatility of graph representations.

9. Can you provide examples of weighted graphs using both adjacency matrix and adjacency list in C Programming?

Answer: Weighted graphs assign a weight (or cost) to each edge connecting the vertices. Here’s how we represent weighted graphs using both adjacency matrices and adjacency lists.

Weighted Graph Using Adjacency Matrix:

#include <stdio.h>
#include <limits.h>

#define V 4
#define INF INT_MAX

void printGraph(int adj[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%7d ", adj[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V] = { {0,   4,  INF, INF},
                        {INF, 0,   8,   5},
                        {INF, INF, 0,   2},
                        {INF, INF, 7,   0} };
    printGraph(graph);
    return 0;
}

In this example, INF represents no direct edge between vertices, and the numbers represent the weights of the available edges.

Weighted Graph Using Adjacency List:

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

struct EdgeNode {
    int adjV;
    int weight;
    struct EdgeNode* next;
};

struct EdgeNode* createEdgeNode(int v, int w) {
    struct EdgeNode* newEdgeNode = (struct EdgeNode*)malloc(sizeof(struct EdgeNode));
    newEdgeNode->adjV = v;
    newEdgeNode->weight = w;
    newEdgeNode->next = NULL;
    return newEdgeNode;
}

void addWeightedEdge(struct EdgeNode* adjList[], int src, int dest, int w) {
    struct EdgeNode* newEdgeNode = createEdgeNode(dest, w);
    newEdgeNode->next = adjList[src];
    adjList[src] = newEdgeNode;

    newEdgeNode = createEdgeNode(src, w);
    newEdgeNode->next = adjList[dest];
    adjList[dest] = newEdgeNode;
}

void printWeightedGraph(struct EdgeNode* adjList[], int vertices) {
    for (int v = 0; v < vertices; ++v) {
        struct EdgeNode* temp = adjList[v];
        printf("Vertex %d: ", v);
        while (temp) {
            printf("%d(%d) -> ", temp->adjV, temp->weight);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int vertices = 4;
    struct EdgeNode* adjList[vertices];

    for (int i = 0; i < vertices; i++)
        adjList[i] = NULL;

    addWeightedEdge(adjList, 0, 1, 4);
    addWeightedEdge(adjList, 1, 2, 8);
    addWeightedEdge(adjList, 1, 3, 5);
    addWeightedEdge(adjList, 2, 3, 2);
    addWeightedEdge(adjList, 3, 2, 7);

    printWeightedGraph(adjList, vertices);
    return 0;
}

In this weighted graph, 4 is the weight of the edge from 0 to 1, 8 is the weight between 1 and 2, and so on. The adjacency list effectively captures these weighted connections.

10. How can you modify these implementations to handle directed graphs?

Answer: To handle directed graphs, modifications involve only making the edges one-directional. In an adjacency matrix, the cell at row i and column j represents a directed edge from i to j but not vice versa. In an adjacency list, we only add an edge from src to dest and not back.

Directed Graph Using Adjacency Matrix:

#include <stdio.h>
#include <limits.h>

#define V 4
#define INF INT_MAX

void printGraph(int adj[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%7d ", adj[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[V][V] = { {0,   4,  INF, INF},
                        {INF, 0,   8,   5},
                        {INF, INF, 0,   2},
                        {INF, INF, INF, 0} };
    printGraph(graph);
    return 0;
}

Directed Graph Using Adjacency List:

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

struct EdgeNode {
    int adjV;
    int weight;
    struct EdgeNode* next;
};

struct EdgeNode* createEdgeNode(int v, int w) {
    struct EdgeNode* newEdgeNode = (struct EdgeNode*)malloc(sizeof(struct EdgeNode));
    newEdgeNode->adjV = v;
    newEdgeNode->weight = w;
    newEdgeNode->next = NULL;
    return newEdgeNode;
}

void addDirectedEdge(struct EdgeNode* adjList[], int src, int dest, int w) {
    struct EdgeNode* newEdgeNode = createEdgeNode(dest, w);
    newEdgeNode->next = adjList[src];
    adjList[src] = newEdgeNode;
}

void printGraph(struct EdgeNode* adjList[], int vertices) {
    for (int v = 0; v < vertices; ++v) {
        struct EdgeNode* temp = adjList[v];
        printf("Vertex %d: ", v);
        while (temp) {
            printf("%d(%d) -> ", temp->adjV, temp->weight);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int vertices = 4;
    struct EdgeNode* adjList[vertices];

    for (int i = 0; i < vertices; i++)
        adjList[i] = NULL;

    addDirectedEdge(adjList, 0, 1, 4);
    addDirectedEdge(adjList, 1, 2, 8);
    addDirectedEdge(adjList, 1, 3, 5);
    addDirectedEdge(adjList, 3, 2, 2);
    addDirectedEdge(adjList, 2, 3, 7);

    printGraph(adjList, vertices);
    return 0;
}

In these examples, the edges are one-directional, representing directed graphs.

By understanding these representations and their implementations, you can efficiently handle and manipulate graphs in C programming, which is essential for solving a wide range of problems in computer science.