in-degree
The number of edges pointing into a vertex of a directed graph; out-degree counts the edges leaving it.
In more detail
A vertex with in-degree zero has no prerequisites, so Kahn's algorithm starts from those vertices. In an undirected graph, a vertex's degree is simply its number of neighbours.
Related terms
- Kahn's algorithm — A topological sort that repeatedly removes a vertex with no remaining incoming edges and lowers the in-degree of its neighbours.
- directed graph — A graph whose edges are one-way: an edge from A to B does not imply an edge from B to A.
- topological sort — An ordering of a directed graph's vertices in which every edge points from an earlier vertex to a later one.
Taught in
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers