Adjacency List Representation in DSA C - Build from Scratch

Adjacency List Representation

📖 Scenario: You are working on a simple social network app. Each person can have friends. You want to store who is friends with whom using a graph.

🎯 Goal: Build an adjacency list representation of a graph using arrays of linked lists in C. You will create the graph, add edges (friend connections), and print the adjacency list.

📋 What You'll Learn

Create a graph with 4 vertices numbered 0 to 3

Add edges to represent friendships: 0-1, 0-2, 1-2, 2-3

Use adjacency lists with linked lists for each vertex

Print the adjacency list showing each vertex and its connected vertices

💡 Why This Matters

🌍 Real World

Graphs are used to model networks like social connections, maps, and communication links.

💼 Career

Understanding adjacency lists is key for software engineers working with network data, pathfinding, and graph algorithms.

1

Create the graph data structure

Create a struct called Node with an int vertex and a Node* called next. Then create a struct called Graph with an int numVertices and a Node** adjLists.

DSA C

# Define the Node and Graph structs
// Your code here

Hint

Use typedef struct to define the structs. The adjacency list is an array of pointers to Node.

2

Initialize the graph with 4 vertices

Write a function Graph* createGraph(int vertices) that allocates memory for a Graph, sets numVertices to vertices, and allocates memory for adjLists array with vertices elements initialized to NULL.

DSA C

Graph* createGraph(int vertices) {
    // Your code here
}

Hint

Use malloc to allocate memory. Initialize each adjacency list head to NULL.

3

Add edges to the graph

Write a function void addEdge(Graph* graph, int src, int dest) that creates a new Node for dest and adds it at the start of src's adjacency list. Also add a new Node for src at the start of dest's adjacency list to make the graph undirected.

DSA C

void addEdge(Graph* graph, int src, int dest) {
    // Your code here
}

Hint

Create new nodes for both directions and insert them at the start of the linked lists.

4

Print the adjacency list

Write a function void printGraph(Graph* graph) that prints each vertex and all vertices connected to it by traversing the adjacency lists. Then in main, create a graph with 4 vertices, add edges 0-1, 0-2, 1-2, 2-3, and call printGraph.

DSA C

void printGraph(Graph* graph) {
    // Your code here
}

int main() {
    // Your code here
    return 0;
}

Hint

Traverse each adjacency list and print the connected vertices. Then add the edges and call printGraph in main.