liveBook · Manning

Directed graph

As explained in Algorithms Every Programmer Should Know

A directed graph is a graph whose edges have a specific orientation from a source vertex to a destination vertex.

A directed graph, or digraph, represents connections with arrows: each edge runs from a source vertex to a destination vertex. Unlike a mutual connection, an arrow does not imply a return path. section 1.4.5

A one-way follow

If A follows B, A’s adjacency list includes B. B’s list stays empty unless B follows someone too. A traversal from A must follow the arrow’s direction. section 1.4.5

Figure 1.13 Two structural variations of a graph. Left: An Undirected Graph maps mutual, bidirectional connections. Right: A Directed Graph restricts travel paths to be unidirectional, forcing algorithms to explore a path based on direction.

Compare mutual, bidirectional connections with one-way paths that constrain traversal. section 1.4.5

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains edge orientation, adjacency-list representation, and effects on BFS and DFS traversal.
Examples
Uses social-media follows to show that A can point to B without B pointing back.
What you can do after
Apply directed edges in an adjacency list and follow their orientation during graph traversal.
How it connects
Connects directed graphs with adjacency lists, undirected graphs, breadth-first search, and depth-first search.

Also explained in

Compare how 5 books explain directed graph →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.