Why Graphs Exist and What Trees Cannot Model in DSA Typescript - Quick Recap

Recall & Review

beginner

What is a key limitation of trees that graphs overcome?

Trees cannot model relationships where nodes have multiple parents or cycles. Graphs allow multiple connections and cycles, representing more complex relationships.

beginner

Why do graphs exist as a data structure?

Graphs exist to represent complex relationships between objects where connections are not strictly hierarchical, such as social networks, road maps, or web links.

beginner

Can a tree have cycles? Why or why not?

No, a tree cannot have cycles because it is a hierarchical structure with a single path between any two nodes. Cycles would break this hierarchy.

beginner

Give an example of a real-life situation where a graph is needed instead of a tree.

A social network where people can be friends with multiple others, including mutual friendships, requires a graph because it has cycles and multiple connections.

beginner

What does it mean when we say graphs can model 'many-to-many' relationships?

It means nodes can connect to multiple other nodes in any direction, unlike trees where each child has only one parent.

Which data structure can represent cycles and multiple parents for nodes?

A Graph

B Tree

C Array

D Stack

Graphs can represent cycles and multiple parents, while trees cannot.

Why can't trees model social networks well?

A Because trees use too much memory

B Because trees are too slow

C Because trees do not allow cycles or multiple parents

D Because trees only store numbers

Social networks have cycles and multiple connections, which trees cannot represent.

What kind of relationship does a tree represent?

A Hierarchical with one parent per child

B Many-to-many

C Random connections

D Cyclic connections

Trees represent hierarchical relationships where each child has exactly one parent.

Which of these is an example where graphs are necessary?

A Company organizational chart

B Road maps with intersections

C File directory structure

D Binary search tree

Road maps have intersections and cycles, which require graphs to model.

What is a cycle in graph terms?

A A disconnected node

B A node with no children

C A node with multiple parents

D A path that starts and ends at the same node

A cycle is a path where you can start at a node and return to it by following edges.

Explain why trees cannot model many-to-many relationships and how graphs solve this problem.

Think about how connections between nodes differ in trees and graphs.

Describe a real-world example where using a graph is necessary instead of a tree and why.

Consider social networks, maps, or web links.