Page 88 - Data Structures Handout_Neat

are more space-efficient, can consume considerable memory when storing large networks

with billions of edges.

Example: Memory Usage in Adjacency Matrix

This simple initialization of a large adjacency matrix can exceed memory limits,
demonstrating why adjacency lists are often preferred for sparse graphs.

8.7.2 Computational Complexity

Many graph problems are computationally expensive. For example:

• Shortest path algorithms like Dijkstra’s run in (( + )log⁡ ), which can be slow for
massive graphs.

3
• All-pairs shortest path using Floyd-Warshall runs in ( ), making it impractical for
large networks.
• Graph coloring and travelling salesman problem (TSP) are NP-hard, meaning no

efficient algorithm is known to solve them for large graphs.

This complexity limits the scalability of graph algorithms in real-world applications

such as social networks or transportation systems.

8.7.3 Handling Negative Weights and Cycles

Graphs with negative edge weights introduce additional challenges. Algorithms like

Dijkstra’s fail in such cases, requiring alternatives like Bellman-Ford. Negative cycles make

shortest path problems unsolvable, as paths can be reduced indefinitely by looping through

the cycle.
Example: Negative Cycle Detection

88