graph
A graph is a data structure that represents a set of objects together with the connections between them. The objects are called vertices or nodes, and each connection is an edge that joins a pair of vertices.
Edges may be directed, pointing from one vertex to another, or undirected, joining two vertices symmetrically. They may also carry weights that stand for distance, cost, or capacity. A graph with no cycles is acyclic, and a directed acyclic graph (DAG) is common enough to have its own name.
Here’s a quick diagram of a graph:
Two storage schemes dominate. An adjacency list keeps, for each vertex, a list of its neighbors, while an adjacency matrix records every possible edge in a grid.
Graphs model road networks, social connections, task dependencies, and the link structure of the web.
Many important algorithms, including breadth-first search and depth-first search, exist to explore the vertices and edges of this kind of data structure.
Related Resources
Tutorial
Build a Maze Solver in Python Using Graphs
In this step-by-step project, you'll build a maze solver in Python using graph algorithms from the NetworkX library. Along the way, you'll design a binary file format for the maze, represent it in an object-oriented way, and visualize the solution using scalable vector graphics (SVG).
For additional information on related topics, take a look at the following resources:
- Common Python Data Structures (Guide) (Tutorial)
- Linked Lists in Python: An Introduction (Tutorial)
- Recursion in Python: An Introduction (Tutorial)
- Dictionaries and Arrays: Selecting the Ideal Data Structure (Course)
- Stacks and Queues: Selecting the Ideal Data Structure (Course)
- Mazes in Python: Build, Visualize, Store, and Solve (Course)
- Records and Sets: Selecting the Ideal Data Structure (Course)
- Working With Linked Lists in Python (Course)
- Linked Lists in Python: An Introduction (Quiz)
- Recursion in Python (Course)
- Recursion in Python: An Introduction (Quiz)
