Page 87 - Data Structures Interactive Book

This program models a transportation system and computes shortest travel times

from a source city to all others.

8.7 Limitations of Graphs

While graphs are powerful tools for modeling complex relationships, they are not

without limitations. Understanding these drawbacks is essential for applying graphs

effectively in real-world systems. Graphs can be memory-intensive, computationally
expensive, and sometimes difficult to manage when dealing with large-scale networks.

Moreover, certain graph problems are inherently complex, requiring advanced algorithms or

approximations rather than exact solutions.

8.7.1 Memory Usage

One of the most significant limitations of graphs is their memory consumption.

2
Representing a graph using an adjacency matrix requires ( )space, where is the number
of vertices. This becomes impractical for large graphs with millions of vertices, especially if

the graph is sparse (few edges compared to possible connections). Even adjacency lists, which

87