Page 71 - Data Structures Interactive Book

Chapter 8

8.1 Introduction to Graphs

Graphs are among the most versatile and powerful data structures in computer

science. Unlike linear structures such as arrays or hierarchical structures like trees, graphs

allow complex relationships where each element (called a vertex) can be connected to
multiple other elements through edges. This flexibility makes graphs suitable for modeling

real-world systems such as social networks, transportation routes, and communication

infrastructures. A graph can represent both simple and highly complex relationships, including

cycles, multiple paths, and weighted connections.

8.1.1 Definition and Characteristics

Formally, a graph is defined as a pair = ( , ), where is the set of vertices and is

the set of edges connecting pairs of vertices. Graphs can be sparse (few edges compared to

vertices) or dense (many edges). They are characterized by their ability to represent non-

linear relationships and cycles, unlike trees which are strictly acyclic.

8.1.2 Terminology

• Vertex (Node): A fundamental unit of the graph.

• Edge: A connection between two vertices.

• Degree: The number of edges connected to a vertex.

• Path: A sequence of vertices connected by edges.
• Cycle: A path that starts and ends at the same vertex.

8.1.3 Types of Graphs

• Directed Graphs: Edges have direction, representing one-way relationships.

• Undirected Graphs: Edges represent two-way relationships.

• Weighted Graphs: Edges have weights, representing cost or distance.
• Unweighted Graphs: Edges simply represent connections without weights.

71