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 small social network where people can be friends with multiple others, including mutual friendships and groups. Trees are great for simple hierarchies like family trees, but they cannot show all these complex connections.

🎯 Goal: You will create a simple graph using an adjacency list to represent friendships between people. This will show how graphs can model relationships that trees cannot, such as cycles and multiple connections.

📋 What You'll Learn

Create a graph using an adjacency list with exact people and connections

Add a variable to count the number of people in the graph

Use a loop to print each person and their friends

Print the total number of people in the graph

💡 Why This Matters

🌍 Real World

Social networks, maps, and many real-world systems have complex connections that trees cannot show. Graphs help model these.

💼 Career

Understanding graphs is essential for software engineers working on networking, recommendation systems, and data analysis.

1

Create the graph with people and their friends

Create a variable called graph as an unordered_map<string, vector<string>> with these exact entries: "Alice" connected to "Bob" and "Charlie", "Bob" connected to "Alice" and "Diana", "Charlie" connected to "Alice", and "Diana" connected to "Bob".

DSA C++

# Create the graph variable with the exact connections
# Your code here

Hint

Use unordered_map<string, vector<string>> to create the graph. Each key is a person, and the vector lists their friends.

2

Add a variable to count the number of people

Create an int variable called num_people and set it to the size of the graph.

DSA C++

#include 
#include 
#include 
#include 

using namespace std;

int main() {
    unordered_map> graph = {
        {"Alice", {"Bob", "Charlie"}},
        {"Bob", {"Alice", "Diana"}},
        {"Charlie", {"Alice"}},
        {"Diana", {"Bob"}}
    };

    // Create num_people variable
    // Your code here

    return 0;
}

Hint

Use graph.size() to get the number of keys (people) in the graph.

3

Print each person and their friends

Use a for loop with variables person and friends to iterate over graph. Inside the loop, print the person followed by their friends separated by commas.

DSA C++

#include 
#include 
#include 
#include 

using namespace std;

int main() {
    unordered_map> graph = {
        {"Alice", {"Bob", "Charlie"}},
        {"Bob", {"Alice", "Diana"}},
        {"Charlie", {"Alice"}},
        {"Diana", {"Bob"}}
    };

    int num_people = graph.size();

    // Use for loop to print each person and their friends
    // Your code here

    return 0;
}

Hint

Use a range-based for loop with structured bindings to get person and friends. Print the person, then loop over friends to print them separated by commas.

4

Print the total number of people in the graph

Write a cout statement to print "Total people: " followed by the value of num_people.

DSA C++

#include 
#include 
#include 
#include 

using namespace std;

int main() {
    unordered_map> graph = {
        {"Alice", {"Bob", "Charlie"}},
        {"Bob", {"Alice", "Diana"}},
        {"Charlie", {"Alice"}},
        {"Diana", {"Bob"}}
    };

    int num_people = graph.size();

    for (const auto& [person, friends] : graph) {
        cout << person << ": ";
        for (size_t i = 0; i < friends.size(); ++i) {
            cout << friends[i];
            if (i != friends.size() - 1) {
                cout << ", ";
            }
        }
        cout << endl;
    }

    // Print total number of people
    // Your code here

    return 0;
}

Hint

Use cout << "Total people: " << num_people << endl; to print the total count.

Practice

1. Why do we need graphs when trees already exist as data structures?

easy

A. Because graphs can represent connections between nodes in any pattern, including cycles and multiple links.

B. Because trees are faster to traverse than graphs.

C. Because trees can only store numbers, but graphs can store any data.

D. Because graphs use less memory than trees.

Solution

1. Step 1: Understand tree limitations

   Trees are hierarchical and cannot have cycles or multiple parents for a node.

2. Step 2: Understand graph capabilities

   Graphs allow cycles and multiple connections between nodes, modeling complex relationships.

3. Final Answer:

   Because graphs can represent connections between nodes in any pattern, including cycles and multiple links. -> Option A

4. Quick Check:

   Graphs model cycles and complex links = B [OK]

Hint: Graphs allow cycles; trees do not. Remember this difference [OK]

Common Mistakes:

• Thinking trees can have cycles
• Confusing data types stored with structure capabilities
• Assuming graphs always use less memory

2. Which of the following is the correct way to declare an undirected graph using adjacency list in C++?

easy

A. int graph[n][n];

B. std::vector<int> graph[n];

C. std::map graph;

D. std::vector graph(n);

Solution

1. Step 1: Identify adjacency list declaration

   Adjacency list uses vector of vectors or array of vectors to store neighbors.

2. Step 2: Check options

   std::vector graph(n); uses vector of vectors with size n, suitable for adjacency list.

3. Final Answer:

   std::vector graph(n); -> Option D

4. Quick Check:

   Adjacency list = vector of vectors [OK]

Hint: Use vector of vectors for adjacency list in modern C++ [OK]

Common Mistakes:

• Using map which is not adjacency list
• Using 2D array which is adjacency matrix
• Using vector<int> graph[n]; which is legacy C++

3. Consider the following C++ code snippet for an undirected graph:

std::vector graph(3);
graph[0].push_back(1);
graph[1].push_back(0);
graph[1].push_back(2);
graph[2].push_back(1);

for (int i = 0; i < 3; i++) {
    std::cout << i << ": ";
    for (int neighbor : graph[i]) {
        std::cout << neighbor << " ";
    }
    std::cout << std::endl;
}

What is the output?

medium

A. 0: 1
1: 0
2: 1 2

B. 0: 1
1: 2
2: 1 0

C. 0: 1
1: 0 2
2: 1

D. 0: 0 1
1: 0 2
2: 1

Solution

1. Step 1: Trace graph construction

   graph[0] has 1, graph[1] has 0 and 2, graph[2] has 1.

2. Step 2: Trace output loop

   Print neighbors for each node: 0->1, 1->0 2, 2->1.

3. Final Answer:

   0: 1 1: 0 2 2: 1 -> Option C

4. Quick Check:

   Adjacency list print matches 0: 1 1: 0 2 2: 1 [OK]

Hint: Follow push_back calls to build adjacency list [OK]

Common Mistakes:

• Mixing order of neighbors
• Confusing adjacency list with matrix output
• Missing symmetric edges in undirected graph

4. The following code attempts to add an edge in an undirected graph but has a bug:

void addEdge(std::vector& graph, int u, int v) {
    graph[u].push_back(v);
}

What is the bug and how to fix it?

medium

A. It should clear graph[u] before adding; fix by calling clear() first.

B. It adds edge only one way; fix by adding graph[v].push_back(u);

C. It uses push_back incorrectly; fix by using insert instead.

D. It should use graph[u][v] = 1; fix by using adjacency matrix.

Solution

1. Step 1: Identify undirected graph edge addition

   Undirected edges must be added both ways: u->v and v->u.

2. Step 2: Find missing edge addition

   Code adds only u->v, missing v->u, so add graph[v].push_back(u); to fix.

3. Final Answer:

   It adds edge only one way; fix by adding graph[v].push_back(u); -> Option B

4. Quick Check:

   Undirected edge needs both directions = C [OK]

Hint: Add edges both ways for undirected graphs [OK]

Common Mistakes:

• Adding edge only one way
• Using wrong vector method
• Confusing adjacency list with matrix

5. Which of the following real-world problems cannot be modeled by a tree but can be modeled by a graph?

medium

A. A social network where people can be friends with multiple others, including mutual friendships.

B. A company's organizational chart with one CEO and clear hierarchy.

C. A family tree showing parent-child relationships.

D. A file directory structure on a computer.

Solution

1. Step 1: Analyze tree model examples

   Family trees, org charts, and file directories are hierarchical with no cycles.

2. Step 2: Analyze social network structure

   Social networks have cycles and multiple connections, not fitting tree structure.

3. Final Answer:

   A social network where people can be friends with multiple others, including mutual friendships. -> Option A

4. Quick Check:

   Cycles and multiple links need graphs = A [OK]

Hint: Cycles and multiple parents mean graph, not tree [OK]

Common Mistakes:

• Thinking family trees have cycles
• Confusing hierarchy with network connections
• Assuming all relationships are one-to-one