Page 90 - Data Structures Handout_Neat

heuristics or approximations due to time and resource constraints.

• Implementation complexity: Advanced graph algorithms require careful

implementation and optimization, which can be error-prone.

8.8 Summary

In this chapter, we explored graphs as one of the most versatile and powerful data

structures in computer science. We began with the definition and characteristics of graphs,

highlighting how they differ from linear structures like arrays and hierarchical structures like
trees. We introduced essential terminology such as vertices, edges, degree, paths, and cycles,

and classified graphs into directed, undirected, weighted, and unweighted types.

We then examined graph representations, focusing on adjacency matrices and
adjacency lists. The adjacency matrix provides constant-time edge lookup but consumes

significant memory, while the adjacency list offers space efficiency and is better suited for

sparse graphs. We compared these representations in terms of performance and memory

usage, emphasizing their trade-offs.

Next, we studied graph traversal techniques, including Breadth-First Search (BFS) and
Depth-First Search (DFS). BFS explores vertices level by level and is particularly useful for

shortest paths in unweighted graphs, while DFS explores deeply along branches and is

valuable for cycle detection, connectivity analysis, and topological sorting. We provided both
recursive and iterative implementations, demonstrating their practical use.

We then moved to shortest path algorithms, covering Dijkstra’s algorithm for non-

negative weights, Bellman-Ford for handling negative weights and detecting cycles, and

Floyd-Warshall for computing all-pairs shortest paths. Each algorithm was explained step by

step, with code examples illustrating their implementation and use cases.
Following this, we explored Minimum Spanning Tree (MST) algorithms, including

Prim’s algorithm, which grows the MST by adding the smallest edge connecting new vertices,

and Kruskal’s algorithm, which builds the MST by sorting edges and using Union-Find to avoid
cycles. Both algorithms were demonstrated with detailed code examples.

We also discussed applications of graphs, showing how they model social networks,

computer networks, and transportation systems. Graph algorithms enable efficient routing,

90