Graph Representation: Adjacency Matrix and List in C

What You’ll Learn 📚

• Understanding graphs and their importance
• Key terminology explained simply
• How to represent graphs using adjacency matrices
• How to represent graphs using adjacency lists
• Common questions and troubleshooting tips

Introduction to Graphs

Graphs are a fundamental part of computer science and are used to represent networks of connected nodes. Think of a graph as a collection of points (nodes) connected by lines (edges). They’re everywhere: from social networks to transportation systems, and even in the relationships between web pages.

Key Terminology

• Node (or Vertex): A point in the graph.
• Edge: A line connecting two nodes.
• Adjacency: A relationship between two nodes that are directly connected by an edge.

Graph Representation: Adjacency Matrix

An adjacency matrix is a 2D array used to represent a graph. Each cell in the matrix indicates whether a pair of nodes is connected by an edge.

#include <stdio.h>
#define V 4

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

int main() {
    int adjMatrix[V][V] = {
        {0, 1, 0, 1},
        {1, 0, 1, 0},
        {0, 1, 0, 1},
        {1, 0, 1, 0}
    };

    printf("Adjacency Matrix:\n");
    printMatrix(adjMatrix);
    return 0;
}

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Lightbulb Moment: An adjacency matrix is great for dense graphs where most nodes are connected. It's easy to check if two nodes are connected by simply accessing matrix[i][j].

Graph Representation: Adjacency List

An adjacency list is an array of lists. The array size is equal to the number of nodes. Each list contains the nodes that are adjacent to the corresponding node.

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

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

struct Graph {
    int numVertices;
    struct Node** adjLists;
};

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

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;
}

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

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

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

int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);

    printGraph(graph);

    return 0;
}

 Vertex 0
: 2 -> 1 -> 
 Vertex 1
: 2 -> 0 -> 
 Vertex 2
: 3 -> 1 -> 0 -> 
 Vertex 3
: 2 -> 

Lightbulb Moment: Adjacency lists are efficient for sparse graphs where not all nodes are connected. They save space compared to adjacency matrices.

Common Questions 🤔

1. What is the difference between an adjacency matrix and an adjacency list?
2. When should I use an adjacency matrix over an adjacency list?
3. How do I check if two nodes are connected in an adjacency list?
4. What are the memory implications of using an adjacency matrix?
5. Can I use these representations for directed graphs?

Answers

1. Difference: An adjacency matrix is a 2D array, while an adjacency list is an array of lists. The matrix is better for dense graphs, and the list is better for sparse graphs.
2. Use Matrix: When you need fast access to check if two nodes are connected, especially in dense graphs.
3. Check Connection: Traverse the list for the source node and see if the destination node is present.
4. Memory Implications: Adjacency matrices use more memory for large, sparse graphs because they store every possible connection.
5. Directed Graphs: Yes, both representations can be used for directed graphs by adjusting how edges are stored.

Troubleshooting Common Issues 🛠️

• Segmentation Faults: Ensure all memory allocations are successful and check array bounds.
• Incorrect Outputs: Double-check your edge additions and ensure your print functions correctly traverse the data structures.

Remember, practice makes perfect! Try modifying the examples to add more nodes and edges. Experiment with both representations to see which works best for different types of graphs.

Practice Exercises 🏋️

• Create a graph with 5 nodes and represent it using both an adjacency matrix and an adjacency list.
• Modify the adjacency list example to handle directed graphs.
• Implement a function to remove an edge from both representations.

Great job making it through the tutorial! Keep practicing, and soon these concepts will become second nature. Happy coding! 🚀