Graph Data Structure
Table of Contents
- Introduction to Graphs
- Graph Terminology
- Graph Representation
- Traversing Graphs: Depth-First and Breadth-First Search
Introduction to Graphs
A graph is a data structure that consists of vertices (also called nodes) and edges, where the edges represent the relationships between the vertices. Graphs can be used to model a wide range of complex systems, such as:
- Social networks
- Transportation systems
- Computer networks
- Web pages and hyperlinks
In other development environments, particularly in back-end systems, databases, or algorithm-heavy applications, graph data structures may be more common. Languages like Python, Java, and C++ frequently implement graphs for tasks like network analysis, route optimization, or natural language processing, among others. Graph databases like Neo4j are also popular for handling complex graph data on the back-end.
Here are some key terms to understand when working with graphs:
- Vertex (Node): A basic unit of a graph, representing an entity or an object.
- Edge: A connection between two vertices, representing a relationship.
- Undirected Graph: A graph in which the edges have no direction, meaning the relationship between connected vertices is bidirectional.
- Directed Graph: A graph in which the edges have a direction, indicating the relationship is unidirectional.
- Weighted Graph: A graph in which the edges have a weight, representing the cost or strength of the relationship.
- Adjacency List: A representation of a graph that uses a list of vertices, where each vertex stores a list of its adjacent vertices.
- Adjacency Matrix: A representation of a graph that uses a two-dimensional matrix to store the relationships between vertices.
There are two common ways to represent graphs in computer memory:
Adjacency List: This is a space-efficient method that is suitable for sparse graphs (few edges relative to the number of vertices). It involves creating a list of vertices and storing their adjacent vertices in a linked list or an array.
Adjacency Matrix: This method is suitable for dense graphs (many edges relative to the number of vertices). It involves creating a two-dimensional matrix, where the cell at position (i, j) indicates the presence of an edge between vertices i and j.
In this section, we'll implement an undirected graph using the adjacency list representation. Here's the basic structure of our Graph class:
Now let's add some methods for adding vertices and edges:
Traversing Graphs: Depth-First and Breadth-First Search
There are two main ways to traverse a graph: depth-first search (DFS) and breadth-first search (BFS). In this section, we'll implement both methods in our Graph class.
Depth-First Search (DFS)
DFS is a graph traversal algorithm that starts at a source vertex and visits vertices as deep as possible before backtracking. Here's the implementation:
Breadth-First Search (BFS)
BFS is another graph traversal algorithm that visits all the vertices at the same level before moving on to the next level. Here's the implementation:
Here's an example of how to use the Graph class and its traversal methods:
Thanks for reading. If you enjoyed this post, I invite you to explore more of my site. I write about web development, programming, and other fun stuff.