directed graph
A graph whose edges are one-way: an edge from A to B does not imply an edge from B to A.
In more detail
Dependencies, links between web pages and one-way streets are directed. In an adjacency list, a directed edge appears only in its source vertex's list. Cycle detection and topological sort are directed-graph problems.
Related terms
- undirected graph — A graph whose edges work both ways: an edge between A and B lets you go from either to the other.
- directed acyclic graph — A directed graph with no cycles, so following edges can never bring you back to where you started.
- in-degree — The number of edges pointing into a vertex of a directed graph; out-degree counts the edges leaving it.
Taught in
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers