Why Graphs Exist and What Trees Cannot Model in DSA C - See It Work

Why Graphs Exist and What Trees Cannot Model

📖 Scenario: Imagine you are organizing a social network where people can be friends with many others, and friendships can go both ways. You want to represent these connections to find out who is connected to whom.Trees are like family trees where each person has only one parent, but social networks have many connections that trees cannot show well.

🎯 Goal: You will create a simple graph using an adjacency list to represent friendships between people. This will show why graphs are needed when trees cannot model multiple connections.

📋 What You'll Learn

Create an adjacency list to represent a graph of people and their friendships

Add a configuration variable for the number of people

Implement a function to add friendships (edges) between people

Print the adjacency list to show all connections

💡 Why This Matters

🌍 Real World

Social networks, transportation maps, and recommendation systems use graphs to model many-to-many relationships.

💼 Career

Understanding graphs is essential for software engineers working on network analysis, data science, and complex system modeling.

1

Create the adjacency list for the graph

Create an integer variable called num_people and set it to 4. Then create an array of integer pointers called adj_list with size num_people. Also create an integer array called adj_list_sizes with size num_people to track the number of friends each person has.

DSA C

int num_people = 4;
int* adj_list[4];
int adj_list_sizes[4];
// Your code here

Hint

Think of adj_list as a list where each person has a list of friends. adj_list_sizes keeps track of how many friends each person has.

2

Set the maximum number of friends per person

Create an integer variable called max_friends and set it to 3. This will be the maximum number of friends each person can have.

DSA C

int num_people = 4;
int* adj_list[4];
int adj_list_sizes[4] = {0, 0, 0, 0};
int max_friends = 3;
// Your code here

Hint

This variable helps us limit how many friends each person can have in the adjacency list.

3

Initialize adjacency lists and add friendships

For each person from 0 to num_people - 1, allocate memory for their friends list with size max_friends. Then add friendships by adding edges: person 0 is friends with 1 and 2, person 1 is friends with 2 and 3, and person 2 is friends with 3. Update adj_list_sizes accordingly.

DSA C

for (int i = 0; i < num_people; i++) {
    adj_list[i] = (int*)malloc(max_friends * sizeof(int));
}
// Add friendships below
// Your code here

Hint

Use a loop to allocate memory for each person's friends list. Then add friends by assigning values and increasing the size count.

4

Print the adjacency list to show friendships

Use a for loop with variable person from 0 to num_people - 1. Inside it, print Person person: then use another for loop with variable j from 0 to adj_list_sizes[person] - 1 to print each friend number separated by spaces. Print a newline after each person's friends.

DSA C

for (int person = 0; person < num_people; person++) {
    printf("Person %d: ", person);
    for (int j = 0; j < adj_list_sizes[person]; j++) {
        printf("%d ", adj_list[person][j]);
    }
    printf("\n");
}
// Your code here

Hint

Print each person and their friends using nested loops. Use spaces between friend numbers and a newline after each person.